2.2　不要被阶乘吓倒

阶乘（Factorial）是个很有意思的函数，但是不少人都比较怕它，我们来看看两个与阶乘相关的问题：

1．给定一个整数N，那么N的阶乘N！末尾有多少个0呢？例如：N＝10，N！＝3628800，N！的末尾有两个0。

2．求N！的二进制表示中最低位1的位置。

分析与解法

有些人碰到这样的题目会想：是不是要完整计算出N！的值？如果溢出怎么办？事实上，如果我们从“哪些数相乘能得到10”这个角度来考虑，问题就变得简单了。

首先考虑，如果N！＝K×10^M，且K不能被10整除，那么N！末尾有M个0。再考虑对N！进行质因数分解，N！=（2^x）×（3^y）×（5^z）…，由于10＝2×5，所以M只跟X和Z相关，每一对2和5相乘可以得到一个10，于是M＝min（X，Z）。不难看出X大于等于Z，因为能被2整除的数出现的频率比能被5整除的数高得多，所以把公式简化为M＝Z。

根据上面的分析，只要计算出Z的值，就可以得到N！末尾0的个数。

【问题1的解法一】

要计算Z，最直接的方法，就是计算i（i＝1，2，…，N）的因式分解中5的指数，然后求和：

代码清单2-6

【问题1的解法二】

公式：Z＝[N/5]＋[N/5²]＋[N/5³]＋…（不用担心这会是一个无穷的运算，因为总存在一个K，使得5^K＞N，[N/5^K]＝0。）

公式中，[N/5]表示不大于N的数中5的倍数贡献一个5，[N/5²]表示不大于N的数中5²的倍数再贡献一个5，……代码如下：

问题2要求的是N！的二进制表示中最低位1的位置。给定一个整数N，求N！二进制表示的最低位1在第几位？例如：给定N＝3，N！＝6，那么N！的二进制表示（1010）的最低位1在第二位。

为了得到更好的解法，首先要对题目进行一下转化。

首先来看一下一个二进制数除以2的计算过程和结果是怎样的。

把一个二进制数除以2，实际过程如下：

判断最后一个二进制位是否为0，若为0，则将此二进制数右移一位，即为商值（为什么）；反之，若为1，则说明这个二进制数是奇数，无法被2整除（这又是为什么）。

所以，这个问题实际上等同于求N！含有质因数2的个数。即答案等于N！含有质因数2的个数加1。

【问题2的解法一】

由于N！中含有质因数2的个数，等于N/2＋N/4＋N/8＋N/16＋…^①，

根据上述分析，得到具体算法，如下所示：

代码清单2-7

【问题2的解法二】

N！含有质因数2的个数，还等于N减去N的二进制表示中1的数目。我们还可以通过这个规律来求解。

下面对这个规律进行举例说明，假设N＝11011，那么N！中含有质因数2的个数为N/2＋N/4＋N/8＋N/16＋…

即：　　1101＋110＋11＋1

　　　　＝（1000＋100＋1）

　　　　＋（100＋10）

　　　　＋（10＋1）

　　　　＋1

　　　　＝（1000＋100＋10＋1）＋（100＋10＋1）＋1

　　　　＝1111＋111＋1

　　　　＝（10000－1）＋（1000－1）＋（10－1）＋（1－1）

　　　　＝11011－N二进制表示中1的个数

小结

任意一个长度为m的二进制数N可以表示为N＝b[1]＋b[2]2＋b[3]2²＋…＋b[m]*2^（m－1），其中b[i]表示此二进制数第i位上的数字（1或0）。所以，若最低位b[1]为1，则说明N为奇数；反之为偶数，将其除以2，即等于将整个二进制数向低位移一位。

相关题目

给定整数n，判断它是否为2的方幂（解答提示：n＞0&&（（n&（n－1））==0））。