Lesson 12 · Intermediate

Bit manipulation — the tricks worth memorizing

📖 Walk me through it — plain English

Computers store every number as a row of bits — tiny on/off switches, written as 1s and 0s. The number 13, for example, is 1101 in this on/off form (that's 8 + 4 + 0 + 1). "Bit manipulation" just means flipping or comparing those switches directly instead of doing ordinary arithmetic. It feels like a magic trick the first time, but there are only about six patterns to learn, and then a whole class of problems becomes easy.

The star of this lesson is XOR, written ^. XOR compares two numbers bit by bit and outputs a 1 wherever the two bits differ, and 0 wherever they're the same. Two facts fall out of that rule and do all the work: any number XOR'd with itself is 0 (every bit matches itself, so every output bit is 0), and any number XOR'd with 0 is unchanged. So XOR is like a light switch: flip it with the same value twice and you're back where you started.

The classic problem ("Single Number") is: you're given a list where every value appears exactly twice except one loner that appears once. Find the loner. The trick: XOR every value in the list together. Each pair cancels itself out to 0 (because x ^ x = 0), and the leftover loner gets XOR'd against 0, so it survives untouched. Order doesn't even matter.

Analogy: imagine everyone at a party pairs up to leave, except one person with no partner. If you "cancel out" each matched pair as they walk out the door, whoever is still standing at the end is the single one. XOR is the bouncer doing that cancelling automatically.

List to process: [4, 1, 2, 1, 2]. In 3-bit binary: 4 = 100, 1 = 001, 2 = 010. We keep a running total called out, shown as 3 bit-cells. Start at 0.

Step 1 · XOR in the first value, 4 (= 100). out was 000, so every differing bit flips on. out becomes 100.

Step 2 · XOR in 1 (= 001). The rightmost bit differs (0 vs 1) so it flips on; the others match and stay. out becomes 101.

Step 3 · XOR in 2 (= 010). The middle bit differs (0 vs 1) so it flips on. out becomes 111.

Step 4 · XOR in 1 (= 001) — the second 1, the partner of Step 2. The rightmost bit now matches (1 vs 1) so it flips back OFF. The pair has cancelled. out becomes 110.

Step 5 · XOR in 2 (= 010) — the partner of Step 3. The middle bit matches (1 vs 1) and flips back OFF. Both pairs are now gone, leaving only the loner.

Done · out = 100 = the answer, 4. That's exactly the value that appeared only once.

Why it works: every paired value gets XOR'd in twice, and XOR'ing the same value twice returns to the starting state (the two flips on each bit undo each other), so all pairs vanish to 0. The single value is XOR'd in once against that 0, so it passes through unchanged. We touch each element exactly once and keep just one running number, so it runs in O(n) time (n = list length) and O(1) extra space — no hash set or sorting needed.

The lesson's other snippet, popcount, counts how many bits are set to 1. Its engine is n & (n - 1), which erases the lowest 1-bit each time. So you loop, stripping off one 1-bit per pass, and count the passes — the loop runs only as many times as there are 1-bits, which is faster than checking all 32 positions.

Bit problems look obscure until you know ~6 tricks. After that they're free points.

Operators

a & b — bitwise AND

a | b — bitwise OR

a ^ b — XOR (different bits)

~a — invert all bits

a << k — left shift (× 2^k)

a >> k — right shift (÷ 2^k)

The 6 tricks

n & 1 — parity (1 = odd)

n & (n - 1) — clears the lowest set bit. Iterate to count set bits in O(set-bits).

n & -n — isolates the lowest set bit. Powers Fenwick trees.

n & (n - 1) == 0 — n is a power of 2 (and n > 0).

a ^ a == 0, a ^ 0 == a — Single Number: XOR everything; duplicates cancel.

1 << k — bit at position k. Use as a mask: n | (1 << k) sets it, n & ~(1 << k) clears it, (n >> k) & 1 reads it.

Playground

→

n & 1:

n & (n-1):

n & -n:

power of 2?

popcount:

n << 2:

Template — Single Number (find the one un-paired)

def single_number(nums):
    out = 0
    for v in nums:
        out ^= v          # pairs cancel; the loner survives
    return out

def popcount(n):
    cnt = 0
    while n:
        n &= n - 1; cnt += 1
    return cnt

function singleNumber(nums: number[]): number {
  let out = 0;
  for (const v of nums) out ^= v;
  return out;
}
// JS note: bitwise ops force 32-bit signed int. For values > 2^31, use BigInt.

The classic XOR trick — write it and run it live:

→ Going deeper: Bit tricks compress state; segment trees answer range queries on that state. See Segment tree & Fenwick.