Computers store every number as a row of bits — 1s and 0s. Bit manipulation is the art of working on those bits directly with a handful of tiny, fast operators. It feels low-level, but a few tricks show up again and again in interviews, and they run in a single CPU instruction.
The star of this lesson is one line: n &= n - 1. Subtracting 1 flips the lowest 1 bit (and
everything below it) — so ANDing the result back into n clears the lowest set bit. Do that in
a loop and you count the 1-bits in a number, one per iteration.
Intuition
Think of n as a row of light switches, each either on (1) or off (0). The number 13 is 00001101 — three switches are on. Counting set bits means counting how many switches are on.
The naive way is to look at every switch one at a time. Brian Kernighan's trick is cleverer: it jumps straight to the lowest switch that is on and turns it off, skipping all the zeros in between. So instead of looping once per bit, you loop once per on switch. A number with three 1s takes exactly three steps, no matter how wide it is.
Why does n & (n - 1) turn off the lowest 1? Subtracting 1 from a binary number flips the lowest 1 to 0 and turns every 0 below it into 1 (borrowing, just like decimal). ANDing that with the original keeps every higher bit the same but zeroes out that lowest 1 and the run of 1s it created. The net effect: the lowest set bit vanishes.
Walk through it
Step through the animation on the right. We start with n = 13 = 00001101 and count = 0. The bit cells are labeled by position underneath (bit 0 is the rightmost, worth 1).
Each loop does two things. First we spotlight the lowest 1 bit — the one n & (n - 1) is about to wipe. Then we clear it: that cell flips to 0, turns the "visited" color, and count ticks up by one. After clearing bit 0 we get 00001100 (12), then 00001000 (8), then 00000000 (0). The moment n hits 0, the while n: condition is false, the loop stops, and we return count = 3.
The code, line by line
def count_set_bits(n):
count = 0
while n:
# n & (n - 1) clears the lowest set bit
n &= n - 1
count += 1
return countcountstarts at0and ends as the number of 1-bits.while n:keeps looping as long asnhas any 1 left. The instantnbecomes0, we are done.- Line 5,
n &= n - 1, is the whole trick — it removes exactly one set bit (the lowest) per pass. - Because each pass removes one 1-bit, the loop body runs once per set bit, not once per bit.
The other bitwise operators you should know
You will not pass an interview on Kernighan alone. Keep these in your back pocket:
| Operator | Symbol | What it does |
|---|---|---|
| AND | a & b | 1 only where both bits are 1 (mask / check a bit) |
| OR | a | b | 1 where either bit is 1 (set a bit) |
| XOR | a ^ b | 1 where bits differ (toggle / find the odd one out) |
| NOT | ~a | flips every bit |
| Left shift | a << k | multiply by 2**k (append k zeros) |
| Right shift | a >> k | divide by 2**k (drop the low k bits) |
Three patterns fall right out of these:
- Is
neven?n & 1 == 0. The lowest bit is the "ones" digit, so it tells you odd vs even instantly. - Is
na power of two?n > 0 and (n & (n - 1)) == 0. A power of two has exactly one set bit, so Kernighan's clear leaves0. - Find the lone number (every value appears twice except one): XOR everything together. Pairs cancel (
x ^ x == 0), leaving the loner.
Complexity
| Case | Time | Notes |
|---|---|---|
| Kernighan (this solution) | O(s) (moderate) | s = number of set bits; one pass each |
| Bit-by-bit (shift & check) | O(w) (moderate) | w = bit width, e.g. 32 or 64 |
O(1) (fast)Kernighan's loop runs once per 1-bit, so for sparse numbers it is faster than scanning all w bits. Either way the extra space is O(1) — just the count variable.
When to use / pitfalls
Memorize the three one-liners: n & 1 for even/odd, n & (n - 1) to clear the lowest set bit (and
to test power-of-two), and XOR to cancel pairs. They turn a surprising number of "tricky" array
problems — single number, missing number, counting bits — into two-line solutions.
Watch the edge cases. n & (n - 1) == 0 is true for 0 too, so the power-of-two check must also
require n > 0. And in languages with fixed-width integers, ~a and left shifts can overflow or hit
sign bits — Python integers are arbitrary precision, which hides bugs that would bite you in C or Java.
Practice
Run Kernighan on n = 8 (which is 1000 in binary). How many times does the loop body execute, and what is the final count?
1. What does n &= n - 1 do to n?
2. Why does Kernighan's loop run once per set bit instead of once per bit?
3. How do you check if n is a power of two?
4. An array has every value twice except one. Which operator finds the loner in one pass?