Population count (popcount / Hamming weight)

Population count — popcount, Hamming weight, or "count the set bits" — is the number of 1-bits in an integer. The most-studied single operation in bit-manipulation, with a clean ladder of methods of increasing cleverness (count-set-bits-so, bit-twiddling-hacks).

The method ladder

• Naive — test all 32/64 bits (loop iterations = word size).
• Kernighan — v &= v - 1 clears the lowest set bit; loop runs once per set bit, so it's fast on sparse words.
• Parallel / SWAR — add bits in place using the mask sequence (0x55…, 0x33…, 0x0f…) then a multiply-and-shift; constant-time, branch-free (the bit-twiddling-hacks "12 ops" version).
• Lookup table — sum precomputed counts of byte/nibble chunks; memory-for-compute.
• Hardware — the CPU POPCNT instruction via __builtin_popcount / C++20 std::popcount; the recommended modern answer, and the case-in-point for branchless-programming's "hardware wins now."

"The hardware wins now" is an x86 sentence. The ladder above ends at one instruction because that is what x86 provides. On AArch64 it does not end there: CNT counts set bits per byte lane and a horizontal ADDV is still needed to add the lanes together, and per cortex-a76-optimization-guide that reduction costs latency 6 at one every two cycles against CNT's 2 and 2 — the finishing step is dearer than the counting. Set against uops-info's measured VPOPCNTQ zmm (3 cycles, one per cycle, 512 bits), the two architectures are not doing the same amount of work per instruction, and a portable claim about popcount's cost has to say which one it means.

The counts behind the ladder, from hamming-weight-wikipedia: the parallel/SWAR popcount64 is 17 arithmetic operations, against 24 for the naive per-bit approach and Wegner's sparse method at 3 ops plus 1 branch per set bit (the Kernighan style — cheap only when few bits are set). The SWAR version's named constants are m1 = 0x5555… (2-bit lanes), m2 = 0x3333… (4-bit), m4 = 0x0f0f… (8-bit), and h01 = 0x0101010101010101, whose one multiply sums the byte lanes in place of a final shift-and-add (hamming-weight-wikipedia, swar).

Where it matters

Hamming weight / Hamming distance underpin error-correcting codes, bitset cardinality, bitboard game engines (chess), similarity hashing (SimHash), and bitmap-index databases — so popcount is one bit trick that stayed performance-critical enough to earn its own instruction. hamming-weight-wikipedia adds RSA cryptography to the list: a public exponent with low Hamming weight needs fewer modular multiplications.

What it costs when you actually count

The ladder above counts operations; a production profile counts nanoseconds, and valyu-billion-scale-vector-index is the spoke's first source that does (2026, T3 — the company's own measurements of its own closed system).

• ~5 ns for a 512-bit Hamming distance on Intel x86 with AVX-512 and VPOPCNTDQ: one ZMM register, one XOR, one popcount, one horizontal sum.
• 0.32 GH/s per core single-threaded; 7.25 GH/s across 44 SMT threads. That is a 22× scale-up on 44 threads, which they attribute to AVX-512's shared 512-bit execution units and turbo throttling. Wide popcount does not parallelize by adding threads — they queue for the same unit.
• 61.1 GH/s on one NVIDIA L4, about 488 billion 64-bit popcounts per second, at 93% of compute throughput on the GPU's MIO unit, where the CUDA popcll intrinsic shares issue cycles with branches and shared-memory ops. Not memory-bound. Bound on the pipe that issues popcount.

The last one is the interesting shape. This spoke's standing story is that the hardware absorbed the trick and the problem went away. Here the hardware instruction is the bottleneck: a real workload got fast enough that the popcount pipe became the wall, and the vendor's next move is to leave that pipe entirely for int1 BMMA tensor cores. An instruction can be both the answer and the ceiling.

It earned an instruction on every ISA

Popcount is the rare bit trick that hardware adopted across the board (hamming-weight-wikipedia): AMD shipped POPCNT (SSE4a) in Barcelona in 2007; Intel followed in the Core i7 (Nehalem, SSE4.2) in November 2008. ARM exposes it as VCNT in Advanced SIMD/NEON, and RISC-V as CPOP in the Bit-Manipulation (B) extension. On the language side, __builtin_popcount has been in GCC since 3.4 (2004) and std::popcount landed in C++20 — so the modern answer is "call the intrinsic and let it lower to the instruction."

Related

hamming-distance · valyu-billion-scale-vector-index · bit-manipulation · count-set-bits-so · bit-twiddling-hacks · branchless-programming · swar · hamming-weight-wikipedia