计算整数中1的个数的最有效方法是什么？

Question

可能重复：
Best algorithm to count the number of set bits in a 32-bit integer?

给出一个32位无符号整数，我们希望计算其二进制表示非零位的数量。什么是最快的方法呢？

我们要做这个N〜10^10次。

注意：由于当前cpu的架构，使用大型查找表通常不是一个好主意。本地计算速度比使用需要查看外部存储器的巨大阵列要快得多

Answer 1

实际上有几个选项，我认为本地方式对于这种方式太慢了。

您可以使用查找表获取8位值，并对来自无符号整型值的所有四个字节并行执行，然后求和结果。这其中也可以有很好的平衡性（无论是多核心，还是甚至有些SSE3/4都可以提供帮助）。

你也可以去和Brian Kernighan的解决方案：

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 
} 

而且最后可能的方法，我在什么地方找到前段时间（在64位机器上，因为模运算将是非常快有）：

unsigned int v;  // count the number of bits set in v 
unsigned int c;  // c accumulates the total bits set in v 

c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; 
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; 
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;