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

1. Shift-then-XOR reveals where adjacent bits differ — the basis of the alternating-bits check.
2. i ^ (i >> 1) turns a counter into Gray code, where successive values differ by one bit.
3. Reverse bits by symmetric swaps or a log-step mask cascade rather than rebuilding the number digit by digit.
4. A bitmask doubles as a compact set: one integer can track an entire row's occupancy.
5. Precomputed window masks make "is this block free?" a single AND, turning layout questions into bit tests.