1. 阶乘($n!$)后面有多少个零
如果用1连续乘到$n$,再判断有多少个0,可以明显看到的是乘积很快溢出了。优化一点的方法,每乘多一个数都判断有多少个0,再将乘积后面的0删除,即便是这样,乘积也很就溢出。所以这两种方法在n比较大时,无法使用,我们必须要有一种算法避免溢出。
由于$n!$中含有质因子2的个数肯定比含有质因子5的个数要多,由因式分解可以得到:
$$n!=c2^a5^b=c2^{a-b}10^b$$则$n!$后面有b个零,与$n!$含有质因子5的个数相等,那么我们求出$n!$含有多少个质因子5就可以了,代码如下:uint32_t CountZone(uint32_t n){ uint32_t count = 0; while (n) { n /= 5; count += n; } return count;}
2.判断一个数是否是2的n次幂:
0 == n&(n-1)
3. 判断一个数有多少个1
由第2点可以看到运算一次n&(n-1)
就会少一个1,那么一个数有多少个1就会运算多少次n&(n-1)
,代码如下:
uint32_t CountOne(uint32_t n){ uint32_t count = 0; while (n) { count++; n &= n-1; } return count;}