[编程之美] 2.2 不要被阶乘吓倒

http://www.xuebuyuan.com/2067143.html

问题1：给定一个整数N，那么N的阶乘N! 末尾有多少个0？

这里的思路：考虑哪些数相乘能得到10。将结果表示成N! = K * pow(10, M)，然后对N! 进行因式分解，只有2 * 5会得到10，那么N! 的末尾的0的个数就是因式分解后2和5的幂的最小值。由于整数中出现2的倍数的频率比出现5的频率低，因此，结果就可以直接等于5的幂。

解法一直接处理1到N所有的数，对于每个数，求出它的5的幂。

解法二就要细说了：

将结果表示为[N/5] + [N/pow(5, 2)] + [N/pow(5, 3)] +...，也就是说，5的倍数贡献一个5，pow(5, 2)的倍数再贡献一个5，pow(5, 3)的倍数再贡献一个5。

http://blog.csdn.net/insistgogo/article/details/7685091

1. int FindZeroNum(int N)//每次迭代，就求出多少个5^M贡献5  
2. {  
3.     int nCount = 0;  
4.     while(N)  
5.     {  
6.         N = N / 5; //1-N能奉献多少个5  
7.         nCount += N;  
8.     }  
9.     return nCount;  
10. } 

够得到1到N中有多少个5的倍数，然后再N /= 5，也就是N / 25，即pow(5, 2)的倍数贡献的5的个数。

问题2：求N! 的二进制表示中最低位1的位置。

要求阶乘的二进制表示中最低位1的位置，其实就是求N! 的二进制表示中末尾有多少个0，也即N! 含有质因数2的个数。

对上面一句话的理解：如果N!含有n个2的乘积，那么，N!必定可以通过右移n-1位使得最后一位不为1，因此，就是寻找N!含有质因数2的个数。

由问题一有：[N/2] + [N/pow(2, 2)] + [N/pow(2, 3)] + ...。

对上面一句的理解：N/2得到的是1到N中2的倍数的个数（也就是2，4，6，8等等），N/pow(2, 2)得到的就是1到N中4的倍数的个数（也就是4，8，12，16等等），后面的依次类推。
N!中含有质因数2的个数等于：[N/2]+[N/4]+[N/8]+…

1. int FindLowestOne(int nNum)  
2. {  
3.     assert(nNum > 0);  
4.     int nCount = 0;  
5.     int N = nNum;  
6.     while(N)  
7.     {  
8.         N = N >> 1;  
9.         nCount += N;  
10.     }  
11.     return nCount + 1;  
12. }  

方法二：

以下为规律的推导：N!中含有2的质因数的个数等于[N/2]+[N/4]+[N/8]+…

对于11011即：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的个数)

1. int FindOneNum(int nNum)  
2. {  
3.     int nCount = 0;  
4.     while(nNum)  
5.     {  
6.         nCount++;  
7.         nNum = nNum & (nNum - 1);  
8.     }  
9.     return nCount;  
10. }  
11. /*nNum中最低1的位置*/  
12. int FindLowestOne(int nNum)  
13. {  
14.     assert(nNum > 0);  
15.     return nNum - FindOneNum(nNum) + 1;  
16. } 

给定整数n，判断它是否为2的方幂。

n > 0 && (n & (n - 1)) == 0