阶乘相关问题：

给定一个整数N，那么N的阶乘N！末尾有多少个0呢？例如：N=10，N！=3628800，N！的末尾有两个0。
N！的二进制表示中最低位1的位置。

引理：

N！中含有质因数2的个数，等于[N/2]+[N/4]+[N/8]+[N/16]+···

对于问题一：

角度一：从“哪些数相乘能得到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）

因为能被2整除的数出现的频率比能被5整除的数高得多，所以X大于等于Z，所以把公式简化为M = Z。

所以只要计算出Z的值，就可以得到N！末尾0的个数

ret = 0;
for(i = 1; i<=N; i++)
{
    j = i;
    while(j % 5 == 0)
    {
        ret++;
        j/=5;
    }
}

角度二：思路类似角度一，找“5”的数

公式： Z=[N/5]+[N/5^2]+[N/5^3]+···（不用担心这会是一个无穷的运算，因为总存在一个K，使得5^k > N, [N/5^k]=0）

公式中，[N/5]表示不大于N的数中5的倍数贡献一个5，[N/5^2]表示不大于N的数中5*5的倍数再贡献一个5···

ret = 0;
while(N)
{
    ret += N/5;
    N /= 5;
}

对于问题二：

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

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

解法一：

N！中含有质因数2的个数，等于[N/2]+[N/4]+[N/8]+[N/16]+···

[N/k]等于1，2，3，···，N中能被k整除的数的个数

int lowestOne(int N)
{
    int Ret = 0;
    while(N)
    {
        N >>= 1;
        Ret += N;
    }
    return Ret;
}

解法二：

N！含有质因数2的个数，还等于N减去N的二进制表示中1的数目。

证明：

N！中含有质因数2的个数为：[N/2]+[N/4]+[N/8]+[N/16]+···

假设N = 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的个数)