Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count the set bits (the Hamming weight). The clean baseline checks each of the 32 bits with a shift-and-mask loop. The trick the interviewer wants is Brian Kernighan's `n &= (n - 1)`, which clears the lowest set bit each iteration, so the loop runs only as many times as there are 1-bits.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can count set bits correctly across the full 32-bit range — including negatives in Java — and whether you know the Brian Kernighan optimisation rather than only the naive bit scan.
Where candidates slip
Using a signed right shift (`>>`) in Java on a negative input, which sign-extends with 1s forever and loops infinitely. Also off-by-one or wrong loop bound when scanning all 32 positions.
How to stand out
Explain WHY `n & (n - 1)` clears the lowest set bit (the borrow chain), note it runs in O(set bits), and connect it to the power-of-two check.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCount the 1 bitsIterate every bit or only the set ones?Every positionOnly set bitsExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Shift and Mask — Check Each Bit
1Hint 1Explore hintHide hint
How do you read just the lowest bit of a number? And how do you bring the next bit down into that position?
2Hint 2Explore hintHide hint
n & 1 isolates the lowest bit. Shifting n right by one moves the next bit into place. Repeat until n is 0.
3Hint 3Explore hintHide hint
Loop 32 times (or until n == 0). Each step add (n & 1) to the count, then shift n right. In Java use the UNSIGNED shift >>> so negatives terminate.
A · Core idea
Walk the integer one bit at a time. At each step add the lowest bit (n & 1) to a counter, then shift n right by one so the next bit becomes the lowest. Stop after the value reaches 0 (or after 32 steps).
Why `n & 1` reads the lowest bit. ANDing with 1 (binary ...0001) keeps only bit 0 and zeroes everything else, yielding 1 if the lowest bit is set and 0 otherwise. Adding that to the count tallies one bit per step.
Why the shift must be UNSIGNED in Java. Java's >> is an arithmetic shift: it copies the sign bit into the top, so a negative number stays negative forever and the loop never reaches 0. The >>> operator is the logical shift that pulls in 0 from the top, so the value strictly shrinks toward 0. Python sidesteps this entirely because its ints are arbitrary-precision and these inputs are non-negative, so n >>= 1 is fine.
Why looping to `n == 0` is enough. Once the remaining high bits are all zero there are no more 1s to find, so you can stop early — though for a fixed 32-bit width, capping at 32 iterations is equivalent.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 11 (binary 1011)Interactive diagram
Bits sliding through position 0
n=1011Each shift moves a new bit into the lowest position where n & 1 inspects it.
3C · Code with teaching comments
Reference implementation previewpublic int hammingWeight(int n) { int count = 0; for (int i = 0; i < 32; i++) { count += (n & 1); n >>>= 1;Explore the full codeHide the full code
D · Why it works and complexityO(32) = O(1) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
This approach pays for every bit position whether it's set or not — 32 iterations even for n = 1. That observation ('I'm visiting zeros I don't care about') is exactly the inefficiency Brian Kernighan's trick removes.
ComplexityO(32) = O(1) time, O(1) space — A 32-bit integer has a fixed number of positions, so the loop runs at most 32 times — constant. No extra storage beyond the counter.
E · Edge cases and pitfalls5n = 0 — Loop body never finds a set bit (or runs 32 times adding 0) → returns 0.Explore edge casesHide edge cases
Edge cases handled
n = 0Loop body never finds a set bit (or runs 32 times adding 0) → returns 0.n = -1 (all 32 bits set)With >>> the value shrinks each step; all 32 bits are 1 → returns 32. With >> it would loop forever — the classic bug.
Pitfalls
- Using >> instead of >>> in Java on a negative input — infinite loop from sign extension.
- Writing `count += n & 1` but forgetting operator precedence — wrap (n & 1) when adding to be safe.
- Hard-coding 32 in a language where the width differs, instead of looping until n == 0.
Approach 2 of 2 · Optimal
Brian Kernighan — Clear the Lowest Set Bit (Optimal)
1Hint 1Explore hintHide hint
Is there a single operation that removes exactly one set bit per step, so you only iterate as many times as there are 1s?
2Hint 2Explore hintHide hint
Think about what n - 1 does to the binary representation: it flips the lowest set bit to 0 and all the zeros below it to 1.
3Hint 3Explore hintHide hint
Therefore n & (n - 1) clears the lowest set bit. Loop `n &= (n - 1)` and count iterations until n becomes 0.
A · Core idea
Repeatedly clear the lowest set bit with n &= (n - 1) and count how many times you can do it before n hits 0. That count is the number of 1-bits.
Why `n - 1` flips the lowest set bit and everything below it. Subtracting 1 borrows from the lowest 1. Say n ends in ...1000. Then n - 1 is ...0111: the lowest set bit became 0, and every 0 below it became 1 (the borrow propagated). All bits above the lowest set bit are untouched.
Why ANDing then clears exactly that bit. Above the lowest set bit, n and n - 1 are identical, so AND keeps those bits. At and below the lowest set bit, the two numbers are bitwise complements (1000 vs 0111), so AND zeroes all of them. Net effect: the single lowest set bit disappears and nothing else changes. Example: 12 = 1100, 11 = 1011, 12 & 11 = 1000 — the lowest set bit (position 2) is gone.
Why this beats the bit scan. The shift-and-mask loop always runs 32 times; Kernighan runs once per set bit. For sparse integers like n = 8 (one set bit) that's a single iteration instead of 32. It also dodges the signed-shift trap entirely, since we never shift — we just keep clearing bits until nothing is left.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 11 (binary 1011)Interactive diagram
Kernighan clearing the lowest set bit
n=1011Each n &= (n - 1) erases exactly one 1 until none remain.
3C · Code with teaching comments
D · Why it works and complexityO(set bits) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
n & (n - 1) is the Swiss-army identity of bit manipulation: it clears the lowest set bit. As a bonus, n & (n - 1) == 0 (for n > 0) means n has exactly one set bit — i.e. it's a power of two. Recognising this one identity unlocks a whole family of problems.
ComplexityO(set bits) time, O(1) space — Each iteration removes exactly one set bit, so the loop runs exactly popcount(n) times — never more than 32, often far fewer. Only a counter is stored.
E · Edge cases and pitfalls5n = 0 — Loop never runs → returns 0 immediately.Explore edge casesHide edge cases
Edge cases handled
n = 0Loop never runs → returns 0 immediately.n = -1 (all bits set)Clears one bit per iteration for 32 iterations → returns 32. No shifting, so the signed-shift trap can't occur.
Pitfalls
- Writing `n & (n - 1)` but forgetting to assign it back — `n &= (n - 1)` is required, otherwise infinite loop.
- Using this to detect powers of two without guarding n > 0 — `0 & -1 == 0` falsely looks like a power of two.
- Assuming it's asymptotically faster than the bit scan for dense inputs — both are O(1) for fixed width; Kernighan just does less constant work.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int hammingWeight(int n) { int count = 0; while (n != 0) { n &= (n - 1); count++;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Signed shift on a negative integer (Java)
`>>` copies the sign bit into the top, so a negative n stays negative and the loop never reaches 0. Use the unsigned `>>>`.
Explore the code comparisonHide the code comparison
Signed shift on a negative integer (Java)
`>>` copies the sign bit into the top, so a negative n stays negative and the loop never reaches 0. Use the unsigned `>>>`.
Don't write this
while (n != 0) {
count += (n & 1);
n >>= 1; // sign-extends: -1 stays -1 forever
}Write this instead
while (n != 0) {
count += (n & 1);
n >>>= 1; // logical shift: pulls in 0, terminates
}2Forgetting to assign back the AND result
`n & (n - 1)` computes a new value but discards it unless you store it. Without the assignment, n never changes and the loop is infinite.
Explore the code comparisonHide the code comparison
Forgetting to assign back the AND result
`n & (n - 1)` computes a new value but discards it unless you store it. Without the assignment, n never changes and the loop is infinite.
Don't write this
while n:
n & (n - 1) # result thrown away — infinite loop
count += 1Write this instead
while n:
n &= n - 1 # store the cleared value
count += 1Revise
Carry the pattern into the interview
Pattern to remember
Set-bit counting / Hamming weight
Code pattern to memorize
count = 0
while n != 0:
n &= (n - 1) # clears the lowest set bit
count += 1
return countRules to remember
- 1
n & (n - 1)clears the lowest set bit — subtracting 1 flips that bit to 0 and all bits below it to 1, then AND wipes them. - 2Brian Kernighan's loop runs once per set bit, not once per bit position — O(number of 1s).
- 3In the shift-and-mask version, mask with
n & 1then unsigned shiftn >>>= 1in Java;>>would sign-extend forever on negatives. - 4Python ints are arbitrary precision and non-negative for these inputs, so
n & 1thenn >>= 1is safe. - 5Loop until
n == 0, not a fixed 32 — Kernighan stops as soon as the bits run out.
Use this pattern when
- Count, or reason about, the number of set bits in an integer
- Hamming weight / Hamming distance style questions
- You want to iterate only over the 1-bits, skipping the zeros
- Detecting powers of two (`n & (n - 1) == 0`)
Choose another pattern when
- You need the value of a specific bit, not the total count → shift-and-mask that position directly
- Counting bits for every number 0..n → reuse subproblems with DP (Counting Bits)
- The language offers a trusted builtin (Integer.bitCount, bin(n).count('1')) and the interviewer allows it → use it and explain it
- You need to set/clear a bit, not count → that's masking, not Kernighan
Interview takeaway
`n & (n - 1)` clearing the lowest set bit is one of the two or three bit tricks every interviewer expects you to know. It turns 'count the 1s' from 32 iterations into exactly popcount iterations, and the same identity detects powers of two.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternSet-bit counting with Brian Kernighan. Recognise it whenever you must count or iterate over the 1-bits of an integer. The n & (n - 1) identity also powers Hamming Distance and the power-of-two check.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Counting BitsCount set bits for every number 0..n. Reuse subresults with DP: dp[i] = dp[i >> 1] + (i & 1).
- Hamming DistanceComing soonXOR the two numbers, then count set bits of the result with this exact technique.
- Power of TwoComing soonn > 0 && (n & (n - 1)) == 0 — exactly one set bit means it's a power of two.
- Reverse BitsSame per-bit machinery, but build the reversed result instead of counting.