计数位设置

在密码学和其他应用中经常需要比特串的人口数，并且该问题已被广泛研究。

天真的方式需要每位迭代一次：

unsigned value = 1234;
unsigned bits = 0;  // accumulates the total number of bits set in `n`

for (bits = 0; value; value >>= 1)
  bits += value & 1;

一个很好的技巧（基于删除最右边的设置位 ）是：

unsigned bits = 0;  // accumulates the total number of bits set in `n`

for (; value; ++bits)
  value &= value - 1;

它经历了与设置位一样多的迭代，因此当 value 预期具有很少的非零位时，这是好的。

该方法最初是由 Peter Wegner 提出的（在 CACM 3/322 - 1960 中），因为它出现在 *C 编程语言中，*由 Brian W. Kernighan 和 Dennis M. Ritchie 提出。

这需要 12 次算术运算，其中一次是多次运算：

unsigned popcount(std::uint64_t x)
{
  const std::uint64_t m1  = 0x5555555555555555;  // binary: 0101...
  const std::uint64_t m2  = 0x3333333333333333;  // binary: 00110011..
  const std::uint64_t m4  = 0x0f0f0f0f0f0f0f0f;  // binary: 0000111100001111

  x -= (x >> 1) & m1;             // put count of each 2 bits into those 2 bits
  x = (x & m2) + ((x >> 2) & m2); // put count of each 4 bits into those 4 bits 
  x = (x + (x >> 4)) & m4;        // put count of each 8 bits into those 8 bits 
  return (x * h01) >> 56;  // left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

这种实现具有最好的最坏情况行为（ 有关详细信息，请参阅汉明重量 ）。

许多 CPU 都有特定的指令（如 x86 的 popcnt），编译器可以提供特定的（ 非标准 ）内置函数。例如，使用 g ++有：

int __builtin_popcount (unsigned x);