引子:编程之美给出了求N!的二进制最低位1的位置的二种思路,但是呢?但是呢?不信你仔细听我道来。
1、编程之美一书给出的解决思路
问题的目标是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、编程实现
(1)书中提到的解决方案一:
1 int factLastBinaryOne(int N)
2 {
3 int count = ;
4 while (N)
5 {
6 count+=N/;
7 N=N/;
8 }
9 return count+;
}
(2)书中提到的解决方案二:http://blog.csdn.net/hackbuteer1/article/details/6690015
贴上计算数的二进制表示1的个数的计算方法:
1 int BitCount(int value)
2 {
3 int count = ;
4 while (value)
5 {
6 value = value&(value - );
7 count ++;
8 }
9 return count;
}
则其计算方法是N - BitCount(N!)+1 。
3、我们看看测试用例以及测试结果
1 int main()
{
int sum = ;
printf("N=%-6d,%4d\n",sum,factLastBinaryOne(sum));
printf("N=%-6d,%4d\n",sum,sum+-BitCount());
return ;
}
看看运行结果:
注意答案不一样哦,但估计是我错了,请各位园友帮我指正一下,共同学习,共同进步。