计数整数中的设定位数
可能重复：
计算32位整数中设定位数的最佳算法？
嗨，
我在采访中遇到了这个问题。 我想以优化的方式找到给定数字中的设置位数。
示例：
如果给定的数字是7，那么输出应该是3（因为7的二进制数是111，我们有三个1）
如果给定的数字8然后输出应该是1（因为8的二进制是1000我们有一个1）
我们需要通过优化的方式找到一些数字。 有什么建议么？
沃伦有关于计数位的全部内容，其中包括一个关于Conting 1位的内容。
这个问题可以用分而治之的方式来解决，也就是总和32比特求和，求和2 16比特数等等。 这意味着我们只需将两个n位字段中的数字一起添加到一个2n字段中。
Example:
10110010
01|10|00|01
0011|0001
00000100
这个代码看起来像这样：
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
我们只使用（（x >> 1）＆0x55555555）而不是（x＆0xAAAAAAAA）>> 1，因为我们想避免在寄存器中生成两个大的常量。 如果你看看它，你可以看到最后一个也是无用的，其他的也可以省略，如果不存在这个总和将继续存在的危险。 所以如果我们简化代码，我们最终会得到这个结果：
int pop(unsigned x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0f0f0f0f;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003f;
}
那将是21条指令，在一台普通的RISC机器上免费分支。 根据平均设置多少位，它可能比kerrigan循环更快或更慢 - 尽管也可能取决于所使用的CPU。
从概念上说，
int numones(int input) {
int num = 0;
do {
num += input % 2;
input = input / 2;
} while (input > 0);
return num;
}
更优化的方式（来自上面的评论者链接）：
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}
如果您使用GCC，请使用内建函数int __builtin_popcount (unsigned int x) 。 在某些机器上，这会减少到单个指令。
上一篇: Count the number of set bits in an integer
下一篇: Number of Zeros in the binary representation of an Integer