the question (how many 1-bits?)
how many 1-bits does 44 have?
44 = 0 0 1 0 1 1 0 0
the obvious way: check every position.
(44 >> 0) & 1 → 0
(44 >> 1) & 1 → 0
(44 >> 2) & 1 → 1
(44 >> 3) & 1 → 1
(44 >> 4) & 1 → 0
(44 >> 5) & 1 → 1
(44 >> 6) & 1 → 0
(44 >> 7) & 1 → 0
three. but you checked all eight positions to get there. for a 64-bit number, that's 64 shifts and 64 ANDs — even if only two bits are set.
there's a different loop:
x = 44 0 0 1 0 1 1 0 0
x = x & (x - 1) 0 0 1 0 1 0 0 0 = 40
x = x & (x - 1) 0 0 1 0 0 0 0 0 = 32
x = x & (x - 1) 0 0 0 0 0 0 0 0 = 0
three rounds. it hits zero after exactly three steps — one per 1-bit. it never checks a zero.
look at what disappears each round. 44 → 40: the 1 at position 2 vanished. 40 → 32: position 3. 32 → 0: position 5. always the lowest remaining 1-bit. always exactly one. always leaving everything above it untouched.
why? what is x & (x - 1) actually doing at each step? to see it, you have to watch the subtraction.
what subtraction does to bits
subtract 1 from 44 and line them up.
44 = 0 0 1 0 1 1 0 0
43 = 0 0 1 0 1 0 1 1
positions 0 and 1 were 00, now they're 11. position 2 — the lowest set bit — was 1, now it's 0. positions 3 through 7: identical.
this is borrowing in binary. when you subtract 1, the machine starts at the bottom and scans right to left looking for a bit to borrow from. it passes through the trailing zeros — nothing to take, so each zero flips to one on the way through. (an IOU — the same cascade that happens in decimal when you borrow across a run of 0s, except in binary every digit is either 0 or 1, so the IOU fills the entire column.) the scan keeps going until it hits the first 1. that bit has something to give. it flips to 0 — debt paid — and the cascade stops dead. everything above it never gets touched.
step through and watch where the cascade stops. try a number with more trailing zeros — the borrow has to travel further before it finds something to take.
the borrow eats one specific bit and flips everything below it.
three zones
so line up x and x − 1 after the borrow. the bits don't disagree everywhere — only in a specific region. and that region has a clean structure:
above the lowest set bit: untouched. x and x − 1 are identical here, bit for bit.
the lowest set bit itself: flipped from 1 to 0. where the borrow stopped.
below the lowest set bit: every bit inverted. the trailing zeros became ones.
toggle the bits and watch the zones shift. the boundary always sits at the lowest set bit — move it, and the zones reorganize around it.
that last zone is where people's intuition usually goes soft, and it's worth working through slowly. why must the bits below the lowest set bit all be zero in x? because if any of them were 1, the lowest set bit would be lower — they'd be it. the definition is doing all the work. and why must they all be ones in x − 1? because each zero in x gets hit by the borrow cascade, which flips it to 1 on its way through. the structure is circular in a satisfying way: the definition of "lowest set bit" guarantees trailing zeros, and trailing zeros are exactly what the borrow cascade needs to produce a clean inversion.
the AND
now AND them.
in the zone above: x and x − 1 agree. 1 AND 1 = 1. 0 AND 0 = 0. everything survives.
at the lowest set bit: x has 1, x − 1 has 0. 1 AND 0 = 0. gone.
in the zone below: x has 0, x − 1 has 1. 0 AND 1 = 0. gone.
everything above the lowest set bit is preserved. the lowest set bit and everything below it: zeroed out. one bit removed.
toggle the bits of x and watch the zones shift. the pattern holds for every nonzero number — the borrow always cascades to exactly the right depth, and the AND always cleans up exactly the right region.
why the scan was never necessary
subtraction already does the searching. the borrow cascade ripples upward through the trailing zeros and stops at the first 1 — which is exactly the bit you wanted to find. x − 1 disagrees with x in exactly the right places: at the lowest set bit and below. AND enforces that disagreement, zeroing out every position where they differ. the mask you'd normally build by hand — find the position, shift, negate — subtraction builds it for you, for free, as a side effect of how borrowing works.
that's why x = x & (x - 1) is the inner loop of popcount: each round clears one set bit, and you count how many rounds it takes to hit zero. that's why x & (x - 1) == 0 tests for powers of two — a power of two has exactly one set bit, so one round kills everything. it shows up in Fenwick trees, in hash tables, anywhere you need the lowest set bit gone fast.
one subtraction, one AND. the borrow cascade is the scan.