the question (how many 1-bits?)
how many 1-bits does 44 have?
44 = 0 0 1 0 1 1 0 0
7 6 5 4 3 2 1 0 ← bit position
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
7 6 5 4 3 2 1 0 ← bit position
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. on paper, subtracting 1 starts at the bottom and works right to left looking for a bit to borrow from. each trailing zero has nothing to give, so it borrows 2 from the column above, hands 1 down to pay the debt, and keeps 1 for itself. that's why the zero flips to one: it kept the change. (same arithmetic as decimal, where 1000 − 1 = 999: each zero borrows ten, pays one, keeps nine. in binary, "keeps one" fills the whole column.) the borrow keeps passing upward 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 interlocks: 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.
step through the phases: x, then x − 1, then the AND, then what survives. 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 for you, for free, as a side effect of how borrowing works.
that's why x = x & (x - 1) is the inner loop of Kernighan's 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, with one famous trap: a power of two has exactly one set bit, so one round kills everything, but 0 passes the test too. zero has no 1 anywhere, so the borrow runs off the end of the register, flipping every column on the way and leaving all ones behind; 0 & (0 − 1) is 0 & 11111111, which is 0. the one input where the cascade never finds a bit to stop at. guard it with x != 0 or ship the bug. the idiom 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.
(and now that you can read the three zones: predict what x & -x computes. then check yourself against the cascade.)