Bit Patterns
What is this?
Sometimes what matters is not the value of a number but the shape made by its on and off switches — like reading a barcode rather than a price tag. These problems look for arrangements such as switches that strictly alternate on-off-on-off, or treat the whole row of switches as a compact map of which seats in a cinema are taken.
💡 Fun fact: Gray code, where each step flips just one switch, was patented by Bell Labs physicist Frank Gray in 1953 and is still used on rotary encoders so a sensor never misreads a value while spinning between positions.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: many problems are really about the shape of the bits, not their value. Shifting a number against itself and XOR-ing exposes where adjacent bits agree or differ, and treating a bitmask as a compact set lets you track occupancy or build sequences with one integer.
The pattern
The central move is shift-then-XOR. If you slide n right by one and XOR with itself, every position where two neighboring bits differ becomes a 1. For alternating bits, that result is all ones, which you confirm by checking (x & (x+1)) == 0. Gray code uses the same neighbor relationship the other way: i ^ (i >> 1) maps consecutive integers to codes that differ by exactly one bit, generating the whole sequence directly.
Reversing bits flips the layout end to end — either swap symmetric positions one pair at a time, or use a divide-and-conquer cascade of masks that swaps halves, then quarters, then bytes in O(log w) steps. The seat-allocation problem treats a row as a bitmask of occupied seats: set a bit per booked seat, then AND against fixed window masks to test whether a contiguous block of seats is still free, updating the mask as families are placed.
The problems
- Binary Number with Alternating Bits — shift-XOR to mark differing neighbors, then check the result is all ones.
- Gray Code — generate the reflected sequence directly with
i ^ (i >> 1). - Reverse Bits — swap symmetric bits, or cascade divide-and-conquer masks for
O(log w)reversal. - Cinema Seat Allocation — keep a per-row bitmask of occupied seats and AND against window masks to find free contiguous blocks.
Key takeaways
- Shift-then-XOR reveals where adjacent bits differ — the basis of the alternating-bits check.
i ^ (i >> 1)turns a counter into Gray code, where successive values differ by one bit.- Reverse bits by symmetric swaps or a log-step mask cascade rather than rebuilding the number digit by digit.
- A bitmask doubles as a compact set: one integer can track an entire row's occupancy.
- Precomputed window masks make "is this block free?" a single AND, turning layout questions into bit tests.
Core idea: Walk the integers
0, 1, 2, ... 2ⁿ−1and map each indexitoi ^ (i >> 1)— that single XOR hands you a full Gray code where every neighbour flips exactly one bit.
Problem, rephrased
Imagine you're wiring a dial that physically rotates through 2ⁿ discrete positions. As the dial clicks from one position to the next, you want the binary label printed under the contact brush to change in exactly one bit. If two bits had to change at once, the brush could momentarily land on a garbage in-between value during the transition. Your job: produce the ordered list of labels.
Formally: given a non-negative integer n, return an ordering of all 2ⁿ integers in the range [0, 2ⁿ) such that:
- the sequence starts at 0, and
- the binary representations of every adjacent pair — including the wrap from the last value back to the first — differ in exactly one bit.
Input n |
Output sequence | Why |
|---|---|---|
0 |
[0] |
2⁰ = 1 element; trivially valid |
1 |
[0, 1] |
0 → 1 flips bit 0; 1 → 0 (wrap) flips bit 0 |
2 |
[0, 1, 3, 2] |
00 → 01 → 11 → 10 → 00, one bit each step |
3 |
[0, 1, 3, 2, 6, 7, 5, 4] |
see the worked example below |
Trace n = 2 in binary to feel it:
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson