What does the expression n & (n - 1) do at the bit level, and what problems does that one operation let you solve cheaply?

technical-conceptual · Mid level · software-engineering

What the interviewer is really asking

Probes whether the candidate can reason precisely about what n & (n-1) does to the binary representation, derive the power-of-two and bit-count uses from it, and apply judgment about when a bit trick is worth the readability cost.

What to say

• n & (n - 1) clears the lowest set bit of n. Subtracting 1 flips that lowest 1 to 0 and turns every 0 below it into 1; ANDing with the original keeps everything above the lowest set bit and zeroes that bit and everything under it — net effect, the rightmost 1 disappears.
• Two direct uses fall out: a power of two has exactly one set bit, so n > 0 && (n & (n - 1)) == 0 tests it in one operation; and repeatedly applying n &= n - 1 until n is 0 counts set bits in time proportional to the number of 1s (Kernighan's algorithm), not the full bit-width.
• Show judgment about when to use it. It's the right tool in genuinely hot or low-level paths (bitmask state, flag sets, population counts) where it beats a loop over every bit, but in ordinary code a clear helper or the language's built-in popcount/bit_count is more readable — and bit tricks like XOR-swap are a net loss on modern CPUs, so I don't reach for cleverness without a measured reason.

What to avoid

• Confuse n & (n - 1) (clears the lowest set bit) with n & -n (isolates the lowest set bit) — they're related but do opposite-feeling things.
• Forget the n > 0 guard on the power-of-two check, so 0 is wrongly reported as a power of two.
• Present bit tricks as automatically faster and reach for things like XOR-swap, which is actually slower than a temp variable on modern pipelined CPUs and breaks when the two operands alias.

Example answers

Strong: I needed a fast population count over millions of permission bitmasks. Instead of looping all 64 bit positions per mask, I used n &= n - 1 to strip one set bit per iteration, so the loop ran once per set bit — far fewer iterations on sparse masks — and where the platform had it I used the hardware popcount built-in instead.

Weak: I think n & (n - 1) is some trick for powers of two — I'd have to look up exactly what it does.