Bit Counting (Population Count / popcount)

Population Count (popcount)

The population count of a number is the count of bits that are set to 1 in its binary representation. Also called Hamming weight or sideways sum.

Brian Kernighan's Algorithm

The most elegant software approach clears one set bit per iteration:

function popcount(n) {
  let count = 0;
  while (n) {
    n &= (n - 1);  // Clear lowest set bit
    count++;
  }
  return count;
}

How it works: n & (n - 1) clears the lowest set bit. Each iteration removes exactly one 1-bit, so the loop runs exactly popcount(n) times.

Example: popcount(42)

42 = 00101010  (3 set bits)

Iteration 1: 00101010 & 00101001 = 00101000  (bit 1 cleared)
Iteration 2: 00101000 & 00100111 = 00100000  (bit 3 cleared)
Iteration 3: 00100000 & 00011111 = 00000000  (bit 5 cleared)

Result: 3

Lookup Table Method

For maximum throughput, precompute a 256-entry table for 8-bit values and process one byte at a time:

const TABLE = new Uint8Array(256);
for (let i = 1; i < 256; i++) {
  TABLE[i] = TABLE[i >> 1] + (i & 1);
}

function popcount32(n) {
  return TABLE[n & 0xFF] +
         TABLE[(n >> 8) & 0xFF] +
         TABLE[(n >> 16) & 0xFF] +
         TABLE[(n >> 24) & 0xFF];
}

Hardware Support

Modern CPUs have dedicated popcount instructions (POPCNT on x86, CNT on ARM). In C/C++, use __builtin_popcount() to access them. JavaScript's Math.clz32() provides count-leading-zeros, but no built-in popcount.

Hamming Distance

The Hamming distance between two values is popcount(a ^ b) — the number of bit positions where they differ.