Counting the ones
Counting how many bits are set in an integer, the population count, appears in hashing, error correction, and graph algorithms. The naive loop checks each bit one at a time, but several faster tricks exist.
Smarter approaches
- Clear the lowest set bit: the expression n combined with n minus one using bitwise and removes the rightmost one bit. Looping with this runs only as many times as there are set bits, not the full width.
- Lookup tables: precompute the count for every possible byte, then sum the table values for each byte of a word. This trades a little memory for a handful of lookups.
- Parallel bit counting: add bits in groups using masks and shifts, halving the groups each round, so the whole word is counted in a fixed number of steps.
- Many processors offer a hardware instruction that does this directly in one cycle.
A related trick
Testing whether a number is a power of two is one bitwise operation: a positive number is a power of two exactly when clearing its lowest set bit yields zero, meaning it had a single bit set.
Key idea
Population count can avoid scanning every bit: clearing the lowest set bit loops once per one bit, lookup tables and parallel masking count in fixed steps, and hardware instructions do it in one cycle.