= Byte-table population count
{title2=$\operatorname{popcount}(x)=\sum_j T[(x\gg8j)\mathbin{\&}255]$}
Store the <Hamming weight> of each possible <byte> in a 256-entry table. Extract each byte of a word by a <logical right shift> and a <bit mask>, then sum its table entries. The byte positions partition the word's bits, proving the formula. A 32-bit word needs four lookups, which can be unrolled. Logical extraction does not depend on the <endianness> of a stored word. The speed advantage depends on table-access costs as well as instruction counts.
Back to article page
