Population count — "popcount" — counts the number of 1 bits in a word. It sounds trivial, but it appears everywhere: SSE4.2's POPCNT instruction, Hamming weight in cryptography, Bloom filter sizing, binarized neural network inference, and CRC weight calculations. A naive software loop takes N iterations; hardware does it in log(N) gate delays with a tree of compressors.

The naive approach: chain N half-adders, each adding one bit to a running sum. For 64 bits, that's a 64-deep chain — completely unusable at gigahertz. The sum grows only to 7 bits (since log2(64) = 6 plus a bit), but the depth is what kills you.

The compressor tree trick: a full adder is a "3:2 compressor" — it takes three 1-bit inputs and produces a 2-bit sum (their arithmetic total, which is 0 to 3). So group 64 input bits into groups of three, compress each group to a 2-bit number, and repeat. Each layer cuts the bit count by a factor of 3/2. Starting from 64 bits, you reach a small final sum in about log(64) / log(1.5) ≈ 10 full-adder delays — but with careful scheduling using half-adders and Wallace-tree structure, you get down to ~6 full-adder delays. That's a fixed, small number regardless of word width doubling.

Real-world example — Intel's POPCNT: introduced in Nehalem (2008), it computes 64-bit popcount in a single cycle with 3-cycle latency. Internally it's a compressor tree feeding a small carry-propagate adder for the final sum. AMD's Zen 3 does it in one cycle with only 1-cycle latency. Contrast with a software SWAR ("SIMD within a register") algorithm: ~12 instructions of shifts, masks, and multiplies. The hardware unit is roughly 10× faster and uses less energy per bit counted.

The LUT alternative for FPGAs: if you don't have full adders as primitives but you have 6-input LUTs, split the word into 6-bit chunks, use one LUT per chunk to output the 3-bit sum (0–6), then feed those sums into a small adder tree. A 64-bit popcount costs ~11 LUTs plus a 4-level adder tree — surprisingly compact.

Rule of thumb: a well-designed popcount for N bits fits in N full adders plus a final log2(N)-bit carry-propagate adder, at a depth of roughly 1.44 · log2(N) full-adder delays. For 64 bits, that's ~9 FA delays worst case, ~6 with Wallace scheduling.

Why it matters: in a binarized neural net, every neuron's dot product becomes an XOR followed by a popcount. Hardware that does 512-bit popcounts per cycle turns matrix multiplies into essentially free operations — this is why bit-serial ML accelerators exist.