Count the number of set bits in a 32-bit integer (Stack Overflow)
The canonical community Q&A for popcount — “how many 1-bits are in a 32-bit integer?” One of Stack Overflow’s most-viewed low-level questions, and the practical companion to bit-twiddling-hacks‘s theory.
The page itself did not fetch (Stack Overflow blocks automated fetch from this environment); this summary is written from established knowledge of the canonical answers. Treat method names as reliable and any benchmark specifics as indicative.
The methods it surfaces (the popcount ladder)
- Naive loop — shift and test each bit (32 iterations).
- Brian Kernighan’s
v &= v - 1— clears the lowest set bit each step, so it loops once per set bit; cheap when few bits are set. - Parallel / SWAR — the constant-time bit-twiddling formula (mask-and-add by 1s, 2s, 4s… the
0x55555555 / 0x33333333 / 0x0f0f0f0fsequence, then a multiply-and-shift); the bit-twiddling-hacks “12 operations” version. No data-dependent branches. - Lookup table — precomputed counts for byte/nibble chunks; a memory-for-compute trade.
- Hardware / intrinsic —
__builtin_popcount/std::popcount(C++20) compiling to the CPU POPCNT instruction; on modern hardware this is the recommended answer and beats the hand-rolled tricks (branchless-programming‘s recurring lesson).
Why it’s here
It grounds the abstract population-count concept in the question working programmers actually ask, and it’s the clearest case of the spoke’s central tension: a beloved bit trick (SWAR popcount) that is now usually superseded by a single hardware instruction. Cites bit-twiddling-hacks and Hacker’s Delight as the canonical references.
Tier
T3 — high-quality community Q&A (authoritative by reputation, but crowd-sourced and unversioned); body unfetched, summary from known content. A T1/T2 upgrade is the bit-twiddling-hacks reference or a Hacker’s Delight citation for the formal methods.
Related
population-count · bit-twiddling-hacks · bit-manipulation · branchless-programming