Counting the ones in a binary number: from loops to SWAR

Counting set bits sounds like homework. It turns up in bitmap cardinality, Hamming distance, bloom filter estimates and bitboards, and bitboards are what sent me here this week: represent a Gomoku or Reversi board as a 64-bit integer and win detection becomes a handful of bit operations.

The cheapest version to write

Clear the lowest set bit and count the iterations. The loop runs exactly once per set bit, which is Brian Kernighan’s trick:

function popcount(n) {
  let count = 0;
  while (n) {
    n &= n - 1;
    count += 1;
  }
  return count;
}

n - 1 turns the lowest set bit into a zero and every zero to its right into ones, so ANDing back removes exactly that bit. For a sparse bitmap, this is close to optimal.

Go parallel when it is dense

When about half the bits are set, looping per set bit degenerates into looping per bit. SWAR (SIMD within a register) splits 32 bits into 16 two-bit fields, then 8 four-bit fields, and so on. After four steps each four-bit field holds its own count:

function popcount32(x) {
  x = x - ((x >>> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
  x = (x + (x >>> 4)) & 0x0f0f0f0f;
  return (x * 0x01010101) >>> 24;
}

The comparison:

Approach	Cost
Test each bit	Always 32 rounds
Clear the lowest bit	Iterations equal set bits
Byte lookup table	4 lookups plus adds
SWAR	About 12 operations, branchless

Check the built-in first

Most modern languages have one: u32::count_ones() in Rust, std::popcount in C++20, Integer.bitCount in Java, and the i32.popcnt instruction in WebAssembly. They compile to the CPU POPCNT instruction and beat both versions above on one line. Writing SWAR by hand is worth it for knowing what the built-in does and for environments that lack it, such as old JavaScript engines or constrained Wasm targets.

Two traps I have hit

• JavaScript shifts are modulo 32. 1 << 32 is 1, not zero. Bitmaps wider than 32 bits need BigInt or a combination of Math.imul.
• >> differs from >>>. Arithmetic right shift on a negative number fills with ones; logical shift fills with zeros. SWAR needs >>>, or the sign bits poison the count.

Look for a built-in instruction first, then consider SWAR. The value of knowing the trick is knowing when not to write it.