整数的二进制表示中的零的数量
可能重复：
计算32位整数中设定位数的最佳算法？
给定一个32位整数N，设计一个算法来找出N的二进制位表示中零的个数。
我能想到的最简单的算法是检查零点的二进制表示，用C语言来表示：
int num_of_zero(int num)
{
if(0 == num) return 1; /*For the input 0 it should output 1 */
int Count = 0;
while(num>0){
if(0 == (num&1)) Count++;
num >>= 1;
}
return Count;
}
如果有一些算法需要在固定的时间进行计算，那么我正在游荡。
对于输入0，它应该返回1 而不是32 。
对于5 ，输出应该是1.因为二进制表示是101 。
对于7 ，输出应该是0。
准确地说，我正在寻找一种更好的算法来计算32位整数的二进制解释中的（非前导）零的数量。希望现在这个问题已经很清楚了。
编辑：正如Alex Martelli指出的那样，delroth正在修改我的代码，使其更具可读性并使用迭代。
这样做的简单方法是遍历数字的二进制表示的每一位，测试每个位的值，并计算其中有多少为零。 循环会比递归更清晰。
尽管如此，还有很多优化的方法。 你可以在这个问题的答案中找到一些更好的答案，“计算32位整数中设定位数的最佳算法”（显然，零位数是从总数中减去设定位数）的位）。
网上有一个很棒的资源叫做Bit Twiddling Hacks，它包含了各种各样的C技巧。 您可能对Counting位设置部分特别感兴趣。
快速和愚蠢的方式 - 在重复问题中有更多异国情调的实现，但是我在过去使用了类似的东西，没有太多不良影响。
我们在这里使用一个半字节表来减少循环的运行次数 - 如果你正在做这些计算的一小部分，建立一个更大的阵列可能更有效率，比如在字节级别上，切割循环运行一半。
/* How many bits are set in every possible nibble. */
static size_t BIT_TABLE[] = {
0, 1, 1, 2, /* 0, 1, 2, 3 */
1, 2, 2, 3, /* 4, 5, 6, 7 */
1, 2, 2, 3, /* 8, 9, A, B */
2, 3, 3, 4 /* C, D, E, F */
};
size_t num_of_bits(int num) {
/* Little reworking could probably shrink the stack space in use here. */
size_t ret = 0, i;
register int work = num;
/* Iterate every nibble, rotating the integer in place. */
for(i = 0; i < (sizeof(num) * 2); i++) {
/* Pointer math to get a member of the static array. */
ret += *(BIT_TABLE + (work & 0xF));
work >>= 4;
}
return ret;
}
上一篇: Number of Zeros in the binary representation of an Integer
下一篇: counting number of ones in binary representation of a number