不要被阶层吓倒
提出两个问题：
1，给定一个正整数N，那么N的阶层末尾有多少个0呢？
2，求N的阶层的二进制表示中最低位1的位置。
有人拿到这样的题目会想：是不是要计算出N！的值呢？如果溢出了怎么办？
实际上有必要计算出N！吗？
事实上，没有必要。换个角度想，如果考虑哪些数相乘得到10，问题是不是就变得简单了？
对N进行质因数分解，N！=(2^x)*(3^y)*(5*z)*......，由于2*5=10，所以结果只与2和5的个数有关，每一对2和5相乘都能得到一个0，于是min(x,z)就是要求的结果。不难发现x大于等于z，因为能被2整除的数出现的概率要比能被5整除的数高得多，所以求出5的个数即可。
解法一：
int CountZero1(int n)
{
int ret=0;
int i,j;
for(i=1;i<=n;i++)
{
j=i;
while(j%5==0)
{
ret++;
j=j/5;
}
}
return ret;
}
解法二：关键是求z的值，可以看一下这个公式：
Z=[N/5]+[N/5^2]+[N/5^3]......
公式中，[N/5]表示表示不大于N的数中5的倍数贡献1个，[N/5^2]表示不大于N的数中5^2的倍数再贡献一个.....
int CountZero2(int n)
{
int ret=0;
while(n)
{
ret+=n/5;
n/=5;
}
return ret;
}
问题2要求的是：N的阶层的二进制表示中最低位1的位置。例如：给一个数3，阶层为6，二进制表示为1010，那么1的最低位在第2位
其实如果最后一位是0，那么进行右移操作，直到最后一位是1结束，也就是求质因子2的个数，然后再加1即可
即有：[N/2]+[N/4]+[N/8]......
int CountLowestOne(int n)
{
int ret=1;
while(n)
{
n>>=1;
ret+=n;
}
return ret;
}
不要被阶层吓倒,布布扣,bubuko.com
不要被阶层吓倒
原文：http://blog.csdn.net/cstopcoder/article/details/21646877
