The last pattern chapter is the party-trick drawer: an XOR that makes duplicates annihilate, one AND that erases a bit, and two matrix moves you memorize as choreography. Tiny mechanisms, disproportionate payoff — once you've seen each trick, its problems become five-minute solves.
Every pattern so far was a strategy. This chapter is different: it's a small drawer of mechanisms — bit tricks and matrix choreography that solve their problems almost by themselves. You can't derive them under pressure and you don't need to: each one is thirty seconds to learn and a lifetime to keep.
The drawer holds five things: XOR's pair-cancellation, the bit toolbox (shift, mask, test), the n & (n−1) erasure trick, two memorized matrix moves (rotate, spiral), and fast power by squaring. Interviewers love these as warm-ups and as the second problem of a round — quick to state, quick to grade, and merciless to anyone meeting them cold. Let's make sure that's not you.
An integer is a row of switches. Bit k is worth 2^k, so 1011₂ is 8 + 2 + 1 = 11. Everything in this chapter is three gates and two slides applied to that row:
That's the whole alphabet. Each operation is O(1) — one CPU instruction, no matter which trick you build from it. The compound moves (test bit k with (n >> k) & 1, clear it with n & ~(1 << k)) are just the alphabet spelling short words. You already met bitmasks working for a living in Chapter 18's backtracking states; here they take center stage.
Three facts make XOR the best party trick in the drawer: x ^ x = 0 (anything cancels itself), x ^ 0 = x (zero is invisible), and XOR is commutative and associative (order never matters). Put together: XOR a list of numbers, and every value that appears an even number of times silently vanishes.
That is the entire solution to Single Number Easy — "every element appears twice except one; find it in O(1) space". XOR everything; the pairs annihilate; the loner is what's left in the accumulator. No sorting, no hash map (Chapter 4's O(n)-space counter would work, but the follow-up "constant space?" is exactly why the interviewer picked this problem).
Missing Number Easy is the same trick wearing a beard: XOR all the indices 0..n and all the array values. Every present number pairs up with its own index and cancels; the missing one has no partner and survives. (Gauss offers a second door: expected sum n(n+1)/2 minus actual sum. Both are O(n) time, O(1) space — mention both and the interviewer relaxes.)
Before the marquee trick, get your hands dirty. The byte below is live: click any cell to flip that switch, then hit the operator buttons and watch what each one physically does to the row. Two things to notice while you play: << and >> really are ×2 and ÷2 (with bits falling off the ends), and n & (n−1) always deletes exactly one bit — the lowest 1 — no matter how the rest of the byte looks.
Watch the "power of two?" readout, too. A power of two is a row with a single 1 in it — so erasing its lowest set bit leaves zero. That's the one-line test interviewers fish for: n > 0 and n & (n−1) == 0.
Why does it work? Subtracting 1 from a binary number flips the lowest 1 to 0 and every 0 below it to 1 — the borrow ripples exactly that far and stops. So n and n−1 agree on every bit above the lowest 1 and disagree on everything from it down. AND them, and the disagreement zone dies: 10110100 & 10110011 = 10110000. One surgical erasure per operation.
Number of 1 Bits Easy (a.k.a. Hamming weight) falls immediately — Kernighan's loop: erase until zero, counting erasures. It runs once per set bit, not once per bit; on sparse numbers that's a real win, and saying so out loud is free signal.
Counting Bits Easy is where the trick graduates into a pattern: compute the bit count for every i in 0..n. Here's the pivot — i & (i−1) is i with one bit erased, which makes it a smaller number you've already answered. So bits[i] = bits[i & (i−1)] + 1, and the whole table fills in O(n) — one lookup and one add per entry. That is a dynamic program (Chapter 20's cache-the-subproblem move) hiding inside a bit trick, and it's the flagship code in Section 9.
Reverse Bits Easy asks for a 32-bit integer written backwards. The honest solution is a conveyor belt: 32 times, shift the result left to make room, drop the input's lowest bit into the gap, shift the input right. Three alphabet letters per step:
res = (res << 1) | (n & 1), then n >>= 1 — repeated exactly 32 times.
Note the complexity conversation: this is O(32), i.e. O(1) — a fixed 32 moves regardless of the value. Fixed-width bit problems are constant-time by construction, and pointing that out beats mumbling "O(n)... of, um, bits". The show-off follow-up (swap halves, then quarters, then bytes — reversal in 5 masked steps) is nice trivia, but the conveyor belt is what you should write: correct, obvious, done in a minute.
Now the math half of the drawer — and a confession: matrix problems aren't really math. They're choreography. Nobody derives the rotation under pressure; you memorize two moves and compose them.
Rotate Image Medium: turn an n×n matrix 90° clockwise, in place. The two moves:
Compose them: (i, j) → (j, i) → (j, n−1−i) — which is precisely the 90°-clockwise map. Both moves are in-place swaps, so the whole rotation is O(n²) time — you touch each cell a constant number of times — and O(1) space. Counter-clockwise? Transpose, then flip columns. 180°? Flip rows, then columns. It's all the same two dance steps. Watch them below, then peel the spiral in the same widget.
Spiral Matrix Medium: read an m×n matrix in spiral order. The naive approach — simulate a walker with a direction and turn on collisions — works, but the version that never breaks is border peeling: keep four boundary pointers, top, bottom, left, right, and repeat four passes:
Loop while top ≤ bottom and left ≤ right. The two italicized guards are the whole difficulty of the problem: when the unvisited region collapses to a single row or column mid-lap, they stop you from walking it twice. Every cell is visited exactly once — O(mn) time, and the output is the space, so O(1) extra.
This "shrink the live region behind you" shape should feel familiar: it's Chapter 5's converging pointers, promoted to 2-D. Four walls closing in instead of two.
Pow(x, n) Medium looks like a one-liner until you see n can be ±2³¹. A multiply-n-times loop is O(n) — two billion multiplications, thanks, no. The trick is that exponents split by halving: x²ᵏ = (x²)ᵏ, and if the exponent is odd, peel one factor off first. So: square the base, halve the exponent, collect a factor whenever the exponent is odd — O(log n), "31 squarings instead of two billion multiplies". Chapter 9's halving religion, practiced on arithmetic instead of arrays.
Here's the pleasing part: "is the exponent odd" is n & 1, and "halve it" is n >> 1 — fast power is literally a walk along the exponent's bits, collecting x^(2^k) for each set bit k. The chapter's two halves were one chapter all along. Handle negatives by x → 1/x, n → −n, and mention the edge case everyone forgets: n = −2³¹ can't be negated in 32 bits — do the negation in a wider type (Python shrugs; Scala uses a Long).
That closes the pattern drawer — all twenty tools from the Chapter 1 galaxy are now on your belt. Chapter 23 turns the whole collection into a single decision tree; before that, the skeleton for this chapter's grab-bag:
The pattern, as a whiteboard skeleton:
The flagship is the chapter's best crossover: Number of 1 Bits Easy as the warm-up, then Counting Bits Easy as the main act — where the erasure trick turns into a one-line dynamic program. Read the DP line the way Chapter 20 taught: express the answer for i in terms of an already-solved smaller subproblem. Here the "smaller subproblem" isn't i−1 — it's i with one bit surgically removed.