Data Structures · Bit Manipulation · A Field Guide

The bit
vocabulary

Eight classic problems, but not eight tricks. They're all built from a handful of moves: read the low bit, drop it, cancel with XOR, delete the lowest 1. Learn the words, not the sentences.

01011001
01 · The idea

Bit operations are ordinary meanings in disguise

Every "clever" bit trick is a plain sentence once translated. n & 1 asks what's the last binary digit? n >> 1 says drop it. a ^ b marks where two numbers differ. n & (n−1) means delete the rightmost 1. Once you read them this way, bit problems become normal digit-by-digit reasoning — just in base 2.

02 · Play with the words

A live bit register

Type a number, then apply an operation. The register shows the low 16 bits; changed bits flash terracotta and the resulting value is spelled out. This is the whole vocabulary in one place — poke it until each expression reads like plain language.

Bit playground

n =
Apply an operation to see it act on the bits. Operations that return a value (like n & 1) update n; predicates just report.

Watch n & (n−1) repeatedly — each press deletes exactly one 1, so the number of presses to reach zero is the popcount. That's the Hamming-weight solution, live.

XOR is a canceling pair

Two equal numbers annihilate: x ^ x = 0. Fold a whole array and every duplicate vanishes, leaving only the lonely one. That's Single Number in a single line.

Peeling the last digit

n & 1 reads the rightmost bit; n >> 1 peels it off. Reverse Bits, Counting Bits, trailing zeros — all just decimal-digit reversal, done in binary.

Deleting the rightmost 1

n & (n−1) clears the lowest set bit. Loop until zero and you've counted the ones — the fastest popcount, and the key to Counting Bits' DP.

04 · Watch pairs cancel

Single Number by XOR fold

XOR is associative and commutative, so order doesn't matter — every value that appears twice cancels to 0, and the accumulator ends holding the unique one. Step through and watch the running XOR.

XOR accumulator

The accumulator visits ugly intermediate values, but every pair eventually zeroes out. For "every element three times except one," XOR can't help — you count each bit mod 3 instead (tab 3 below).

05 · The eight problems

Same words, different sentences

Each is a short application of the vocabulary. Tap through — the key idea matters far more than the code.

06 · The cheat sheet

Every expression, translated

Expression Plain meaning
n & 1 Read the lowest bit
n >> 1 Drop the lowest bit (signed shift)
n >>> 1 Drop the lowest bit, fill zero from the left
n << 1 Append a 0 / multiply by 2
a ^ a 0 — equal values cancel
a ^ 0 a — XOR with zero is identity
n & (n − 1) Remove the lowest set bit
n & −n Isolate the lowest set bit
a ^ b Mark every position where a and b differ
1 << k A mask with only bit k set
(n >> k) & 1 Read bit k
x & (x + 1) == 0 x is all-ones (000…0111…1)
07 · The six moves

Six patterns cover all eight

1 · XOR cancellation
x ^ x = 0
Single Number I — pairs vanish, the loner survives.
2 · Inspect the low bit
n & 1
Reverse Bits, popcount, trailing zeros, even/odd, counting bits.
3 · Discard the low bit
n >> 1
Process the binary string right to left — divide by two.
4 · Remove the lowest set bit
n & (n−1)
Hamming weight, Counting Bits DP.
5 · Count bits mod frequency
count % k
Single Number II — the k-repeat generalization.
6 · XOR as difference detector
n ^ (n>>1)
Alternating Bits, Hamming distance — compare neighbors at once.
Recognizing a bit problem Wording like "binary representation," "every number repeated k times," "constant space despite duplicates," "power of two," "alternating bits," or "Hamming distance" is the tell. Then ask: can XOR cancel? Can I reason per bit? Does the low bit or n & (n−1) help?
08 · One month from now

Keep the words, rebuild the sentences

  1. Read a bit operation as its plain meaning before anything else.
  2. Duplicates + constant space → XOR fold; pairs cancel, the loner remains.
  3. Need per-bit reasoning (triples, Hamming) → tally each bit position independently.
  4. Counting or clearing ones → n & (n−1) deletes the lowest set bit.
  5. Building an answer over 0…n → reuse a smaller result: bits[i] = bits[i>>1] + (i&1).
The transferable insight Don't memorize eight solutions — memorize the vocabulary and how to translate it. Bit-manipulation problems stop looking like magic syntax and start behaving like ordinary reasoning over binary digits.