What does n = n & (n - 1) do each pass of a bit-counting loop, and how many passes run?
answer
- What does subtracting one borrow through?
- Track the bits below the lowest one
- One bit disappears per pass
- Iterations track density, not width
- The count equals the population count
basics
~20 sEach pass clears the lowest set bit of n and leaves every other bit alone, so the loop runs exactly once per set bit — the population count — not once per bit of the word width.
solid answer
~50 sSubtracting 1 borrows through the trailing zeros: the lowest set bit flips to 0 and every zero below it becomes 1, while all higher bits are untouched. AND-ing that back with `n` keeps the higher bits as they were, zeroes the lowest set bit, and yields 0 in the positions below it because those were already 0 in `n`. Net effect: exactly one set bit is removed per pass, so a loop that repeats until `n` is zero runs `popcount(n)` times — three passes for a bitboard with three occupied cells, sixty-four only when every bit is set. That is the point of the trick over the naive shift-and-test loop, which always pays the full word width. It is data-dependent, though: the running time leaks how many bits are set, and the branch is unpredictable.
code
pseudocode · 9 linescount = 0
while n != 0:
n = n & (n - 1) // drops the lowest set bit
count = count + 1
// trace, n = 01101000
// pass 1: n - 1 = 01100111, AND -> 01100000
// pass 2: n - 1 = 01011111, AND -> 01000000
// pass 3: n - 1 = 00111111, AND -> 00000000
// count = 3, and the word had 3 set bitsgo deeper
Recall what the expression does in one sentence — it removes the lowest set bit — and be able to trace it on a small binary value on the whiteboard without hesitating.
Derive it: show how subtracting one borrows through the trailing zeros, then argue position by position why the AND preserves the high bits and zeroes the rest. Then state the iteration count as the population count.
Bring in the consequences of data-dependent timing: an unpredictable branch in a hot loop, and elapsed time that leaks input density. Know when to reach for a branch-free or hardware count instead.
Judge whether the trick belongs in your codebase at all. It is a one-line comment away from unreadable, so pin it behind a named, tested helper and let the hot-path variant be an implementation detail the team never has to re-derive.
## Why subtracting one behaves that way Write `n` as `H 1 0...0` — some arbitrary high part `H`, then the lowest set bit, then `t` trailing zeros. Subtracting 1 cannot borrow from the zeros (they have nothing to give), so the borrow propagates up to the lowest set bit, turns it into 0, and lights every position below it: `n - 1` is `H 0 1...1`. The high part `H` is never disturbed. Now AND the two: - In the high part, both words hold `H`, and `H AND H = H` — preserved. - At the lowest set bit, `n` has 1 and `n - 1` has 0 — cleared. - Below it, `n` has 0 and `n - 1` has 1 — `0 AND 1 = 0`, so those stay 0. So `n & (n - 1)` is precisely "`n` with its lowest set bit removed". Note the wording: the *lowest set bit*, not "the lowest bit" and not "bit 0". For an even word, bit 0 was already 0 and is not what changes. ## The counting loop ``` count = 0 while n != 0: n = n & (n - 1) count = count + 1 ``` The loop trades one set bit per iteration, so it executes exactly `popcount(n)` times. On a 64-bit occupancy word for an 8x8 puzzle grid holding six pieces, that is six iterations; the naive alternative — shift right and test bit 0 sixty-four times — pays 64 regardless. Worst case they converge: a fully occupied board costs 64 iterations either way, so the loop's bound is `O(popcount(n))`, which is `O(w)` in the width `w` of the word but usually far below it. Saying "it is O(1)" deserves a follow-up rather than a nod. It is constant *in the number of elements of some collection*, because the word width is fixed — but within the word it is proportional to the density, and that difference is exactly what a scale question is probing. ## The companion identity: n & -n The same decomposition explains the other classic. In two's complement, `-n` is `NOT n + 1`: complementing turns `H 1 0...0` into `H' 0 1...1`, and adding one ripples through those trailing ones back up to the lowest set bit, giving `H' 1 0...0`. So `n` and `-n` agree in exactly one position — the lowest set bit — and disagree above it. Therefore `n & -n` **isolates** the lowest set bit, where `n & (n - 1)` **clears** it. Two things to be precise about. First, `n & -n` returns the bit's **place value** (`2^k`), not its index `k`; converting to an index requires a trailing-zero count or a lookup. Second, both identities return 0 for `n = 0`, which is the right answer only if you accept "no lowest set bit" as zero — a validator that treats a zero result as meaningful is the source of a whole bug family. Together the pair gives you a tidy enumeration of set positions: `low = n & -n` to grab one, `n = n & (n - 1)` to advance. For an occupancy bitboard that is how you walk the occupied cells without visiting the empty ones — the cost tracks the pieces on the board, not the size of the board. ## Where the trick stops being the right answer Because the iteration count depends on the data, the branch at the top of the loop is unpredictable on a dense, varied input, and a mispredict can cost more than the arithmetic saved. That also makes the routine unsuitable anywhere timing must not depend on the value being processed — a secret bit pattern leaks its density through the clock. And when the same word is counted enormously often, the loop is the wrong shape entirely: a branch-free fixed sequence, or a hardware population-count operation, beats it because it pays the same fixed cost at every density. The reasoning also does not run backwards. There is no equally cheap `n & (n + 1)`-style identity for the *highest* set bit: finding the top bit means a logarithm-style search, a lookup, or a dedicated leading-zero-count operation, not a one-line borrow trick.
- How does n & -n differ from n & (n - 1)?It isolates the lowest set bit instead of clearing it. In two's complement `-n` is `NOT n + 1`, which flips everything above the lowest set bit but leaves that bit standing, so the AND keeps exactly it. Be precise about the result: you get the bit's place value `2^k`, not the index `k` — an index needs a trailing-zero count or a small lookup.
- A feature-flag audit tool must report which enabled flag has the lowest position. How do you get it, and what does it return for a word with nothing enabled?`low = n & -n` gives the lowest enabled flag's place value in one operation; map it to a name via a trailing-zero count or a table. For a word with no flags enabled the expression yields 0, which is not a valid flag — treat zero as "nothing enabled" explicitly before reporting, or the tool names flag 0 for an empty word.
- What input makes the loop slowest, and why does that matter beyond raw speed?A fully dense word — every bit set — costs one pass per bit of the width. Because the iteration count is data-dependent, the loop branch is hard to predict on varied input, and the elapsed time reveals how many bits were set. That rules the loop out where timing must be independent of the value, and it is the reason a branch-free or hardware count is preferred in hot paths.
Subtracting one is a borrow reaching for the nearest lit lamp: that lamp goes dark and every lamp below it switches on. AND-ing with the original keeps only what was lit before, so the trick costs one pass per lamp.
saying these in an interview costs you the question
- Says it clears the lowest bit rather than the lowest set bit
- Claims the loop always runs once per word bit
- Calls the loop constant time with no density caveat
- Thinks n & -n returns the bit index
- Believes a symmetric one-liner finds the highest set bit
- Confuses clearing the low bit with isolating it