Bit tricks (n & (n−1), masks)

49 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

How many 1s are in the binary form of 13? Write it out: 13 = 8 + 4 + 1 = 1101, three 1s. By hand you look at each bit. A computer can do the same, testing all 32 bits of an integer one by one, 32 steps whether the number has one set bit or thirty. For a question like "is this number a power of two", scanning bits is clumsy: you want a test that is one or two operations, not a loop.

Build the structure, one piece at a time

There is no data structure, only the binary digits themselves and three operations: AND (&, 1 only where both bits are 1), subtraction, and shifts. The first trick is about what subtracting 1 does to a binary number.

Subtracting 1 from 1101 gives 1100. Subtracting 1 from 1100 gives 1011. Look at the pattern: the lowest 1 turns into 0, and every 0 below it turns into 1, because the borrow ripples through the trailing zeros and stops at the first 1. All bits above the lowest 1 are untouched.

Now AND the number with its decrement. The bits above the lowest 1 are identical in both, so they survive. The lowest 1 meets a 0, so it dies. The trailing zeros meet 1s but are 0 themselves, so they stay 0. Result: the original number with its lowest set bit removed.

Three steps, three set bits. Two more tricks fall out of the same picture. A power of two has exactly one set bit, so removing it leaves 0: n & (n − 1) = 0 (with n > 0). And negation in two's complement flips every bit and adds 1, which produces a number that agrees with n only at the lowest set bit and below, so n & (−n) isolates that lowest bit: 12 & −12 = 4. Shifts complete the kit: n << 1 doubles, n >> 1 halves, and (n >> k) & 1 reads bit k.

Why it is correct

Each trick is an identity about binary digits, not a coincidence. Write n as H·2^k+1 + 2^k, where 2^k is the lowest set bit and H holds the higher bits. Then n − 1 = H·2^k+1 + (2^k − 1), and 2^k − 1 is k ones in binary, occupying exactly the positions below bit k. ANDing with n, whose bits below k are all 0 and whose bit k is 1 against a 0, leaves H·2^k+1. The invariant of the counting loop is that each iteration removes exactly one set bit, so the loop runs once per set bit and the count is exact.

n & (n − 1) = n − 2^k, where 2^k is the lowest set bit of n

Why it is fast

Counting set bits runs one iteration per set bit, O(popcount), at most 32 and usually far fewer, instead of a fixed 32-bit scan; the power-of-two test is a single AND and a comparison, O(1). Every operation here is one machine instruction with no division or branching inside, which is why these tricks appear in tight loops and in hardware.

How to recognise it in an interview

Cues: "without using multiplication or division", "count the 1 bits", "power of two", "reverse the bits", "add two integers without +". Say: I will reason about the binary digits directly; the key identity is that n & (n − 1) clears the lowest set bit. Number of 1 Bits is the loop above. Power of Two is the one-line test. Sum of Two Integers uses XOR for the sum without carries and (a & b) << 1 for the carries, repeating until the carry is 0; Counting Bits fills a table with count[n] = count[n & (n − 1)] + 1.

02The idea in one line

n & (n−1) clears the lowest set bit; shifts and masks build numbers without arithmetic.

Reach for it when: Power of two, number of 1 bits, counting bits, reverse bits, sum without +.

Cost: O(bits) time.

03The walk-through, step by step

The video works one example: Count set bits of 13 with n & (n−1). These are its captions in order, so you can follow without the video or check a step you missed.

1. 13 = 1101: three set bits, but we never scan them one by one
2. n − 1 = 1100: borrows flip the lowest 1 and the zeros under it
3. n & (n−1) = 1100 = 12: lowest set bit gone, count = 1
4. n − 1 = 1011: borrows flip the lowest 1 and the zeros under it
5. n & (n−1) = 1000 = 8: lowest set bit gone, count = 2
6. n − 1 = 0111: borrows flip the lowest 1 and the zeros under it
7. n & (n−1) = 0000 = 0: lowest set bit gone, count = 3
8. n is 0 after 3 steps: 13 has 3 set bits
9. Same trick: n & (n−1) == 0 means n is a power of two; n & −n isolates the lowest bit
10. Loop runs once per set bit: O(popcount), no division

04Asked at Google

10 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Bit Manipulation: XOR cancels pairs, Enumerate subsets by mask.