计算整数中的设置位数

Question

可能重复:
计算32位整数中设置位数的最佳算法？

嗨,

我在接受采访时遇到了这个问题.我想以优化的方式找到给定数字中的设置位数.

示例:

如果给定的数字是7,那么输出应该是3(因为7的二进制是111,我们有三个1)

如果给定的数字8然后输出应该是1(因为8的二进制是1000,我们有一个1)

我们需要以优化的方式找到一些.有什么建议？

Answer 1

Warren有一整章关于计数位,包括一个关于Conting 1位的章节.

该问题可以以分而治之的方式解决,即求和32位被求解为总计2个16位数,依此类推.这意味着我们只需将两个n位字段中的1的数量一起添加到一个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.

Answer 2

从概念上讲，这是有效的：

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
}