2.2 不要被阶乘吓到

1,问题一:
N的阶乘N!末尾有多少个0呢?

解答:问题可转化为N!的质因数分解中5的个数.

int ZeroNum(int n)
{
    int ret;
    //注:第一次循环表示5^1的倍数,每个贡献一个5
    //第二次表示5^2的倍数,也会额外多贡献一个5
    //...一次类推
    while (n)
    {
        n /= 5;
        ret += n;
    }
	return ret;
}

2,问题2:
求N!的二进制表示中的最低位1的位置.

解答:问题转化为求质因数分解中1的个数.

方法1同上:

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

方法2(结合方法1其实很好理解)
N!中含有的质因数2的个数,就等于N减去N的二进制表示中1的数目.

3,拓展
给定整数n,判断它是否为2的方幂.
问题转化:判断二进制表示中1的个数是否==1.

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