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 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.

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

bit-manipulation · count-set-bits-so · bit-twiddling-hacks · branchless-programming · swar · hamming-weight-wikipedia