bit-manipulation-wiki

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

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.

Related

bit-manipulation · count-set-bits-so · bit-twiddling-hacks · branchless-programming