Counting Set Bits

The Idea

Subtracting 1 from a number flips its lowest 1 to 0 and turns every 0 below it into 1. AND the two values together and that tail is wiped out — one set bit gone, the rest untouched.

Repeat until nothing is left. The loop runs once per 1, not once per bit.

Real-World Example

Bloom filters and database bitmap indexes report "how many rows matched?" by popcounting a bitmap. The count must be cheap because it runs over megabytes of bitmap per query — walking all 64 lanes of every word would be wasted work on sparse data.

The Code

def popcount(x):
    count = 0
    while x:
        x &= x - 1          # wipes the lowest set bit, nothing else
        count += 1
    return count            # one pass per 1, not per bit

print(popcount(44))         # 3   -> 0b101100 has three 1s
print(popcount(255))        # 8
print(bin(44), bin(43))     # 0b101100 0b101011 -> the tail flipped
print(bin(44 & 43))         # 0b101000 -> lowest 1 cleared