計數位設定

在密碼學和其他應用中經常需要位元串的人口數，並且該問題已被廣泛研究。

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

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);