求N!的二进制表示中最低位1的位置。(编程之美)

时间:2022-08-25 02:15:34

要求的是N!的二进制表示中最低位1的位置。给定一个整数N,求N!二进制表示的最低位1在第几位?例如:给定N = 3,N!= 6,那么N!的二进制表示(1 010)的最低位1在第二位。

        为了得到更好的解法,首先要对题目进行一下转化。

首先来看一下一个二进制数除以2的计算过程和结果是怎样的。

       把一个二进制数除以2,实际过程如下:

       判断最后一个二进制位是否为0,若为0,则将此二进制数右移一位,即为商值(为什么);反之,若为1,则说明这个二进制数是奇数,无法被2整除(这又是为什么)。

      所以,这个问题实际上等同于求N!含有质因数2的个数+1。即答案等于N!含有质因数2的个数加1。 实际上N!都为偶数,因为质因数里面都有一个2,除了1以外,因为1的阶乘是1,是个奇数,其他数的阶乘都是偶数。。

【问题2的解法一】

由于N! 中含有质因数2的个数,等于 N/2 + N/4 + N/8 + N/16 + …[1],

根据上述分析,得到具体算法,如下所示:

 

int lowestOne(int num)
{
int res=0;
while(num)
{
num
>>=1;
res
+=num;
}
return res+1;//m为n!中质因数2的个数,所以最后结果要加 1
}