🔢 Bit Manipulation

A learning sheet — treat an integer as an array of bits (a tiny set). Then masks select, XOR toggles, and shifts multiply — all in O(1).

🧠 1 · How to think (and invent it)

An integer is just bits indexed from the right. Three mental models cover almost everything: an int is a bitset (each bit = a flag / set member); XOR is a toggle that cancels itself; and a mask (AND with a chosen pattern) selects bits. Master a handful of idioms and these problems become one-liners.

The single most useful property: a ^ a = 0 and a ^ 0 = a, and XOR is order-independent. So XOR-ing a pile of numbers makes every pair vanish — whatever's left is the odd one out.

Watch it get invented — Single Number

1. Start brute. Every value appears twice except one. A hash-map count finds it — but in O(n) extra space.
2. The leap. XOR everything. Identical values cancel in pairs (a ^ a = 0), and order doesn't matter, so the duplicates annihilate and only the unique value survives.
3. Payoff. One pass, O(1) space, no map.

🎯 2 · Attack plan

🔎 3 · Recognition map

🧩 4 · The four core patterns

§4.1 is a vocabulary you memorize; §4.2–4.4 apply it. Each: a one-liner, a 🔑 invariant, a template, a 🎤 interview lens.

4.1 · The idiom toolkit

“Mask to select, shift to move, AND-with-(n−1) to peel the lowest bit.”

const getBit   = (n: number, i: number) => (n >> i) & 1;
const setBit   = (n: number, i: number) => n | (1 << i);
const clearBit = (n: number, i: number) => n & ~(1 << i);
const toggleBit= (n: number, i: number) => n ^ (1 << i);

const isPowerOfTwo = (n: number) => n > 0 && (n & (n - 1)) === 0;   // one set bit
const lowestSetBit = (n: number) => n & (-n);                      // isolate it
const clearLowest  = (n: number) => n & (n - 1);                   // remove it

// Count set bits — Brian Kernighan: loops once per 1-bit
function popcount(n: number): number {
  let c = 0;
  while (n) { n &= n - 1; c++; }
  return c;
}

4.2 · XOR tricks

“XOR everything; pairs cancel, the loner survives.”

// Single Number — every value twice except one
const singleNumber = (nums: number[]) => nums.reduce((a, b) => a ^ b, 0);

// Missing Number in [0..n] — XOR the indices and the values together
function missingNumber(nums: number[]): number {
  let x = nums.length;
  for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i];   // every present value cancels
  return x;
}

// Single Number III — exactly TWO values appear once, the rest twice
function singleNumberIII(nums: number[]): number[] {
  const xorAll = nums.reduce((a, b) => a ^ b, 0);   // = a ^ b  (the two loners)
  const diff = xorAll & (-xorAll);                   // a bit where a and b differ
  let a = 0;
  for (const x of nums) if (x & diff) a ^= x;        // partition by that bit → isolates a
  return [a, a ^ xorAll];                            // b = (a^b) ^ a
}

4.3 · Bitmask — an int as a set

“Bit i set = item i chosen; loop 0…2ⁿ−1 to walk every subset.”

Setup: for small n, a state (which items are picked / visited) fits in one integer. Enumerate all subsets by counting, test membership with a mask, and compress DP state into the int.

// All subsets of items[0..n-1]
function subsets<T>(items: T[]): T[][] {
  const n = items.length, out: T[][] = [];
  for (let mask = 0; mask < (1 << n); mask++) {
    const pick: T[] = [];
    for (let i = 0; i < n; i++) if (mask & (1 << i)) pick.push(items[i]);
    out.push(pick);
  }
  return out;
}

// Enumerate every submask of `mask` (for bitmask DP over subsets)
function submasks(mask: number): number[] {
  const out: number[] = [];
  for (let sub = mask; sub > 0; sub = (sub - 1) & mask) out.push(sub);
  out.push(0);
  return out;
}

4.4 · Bit arithmetic — add without +

“Sum-without-carry is XOR; the carry is AND shifted left; repeat.”

Setup: binary addition splits into two parts — the column sum ignoring carries (a ^ b) and the carries themselves ((a & b) << 1). Fold the carry back in until it's gone.

// Sum of Two Integers without + or -
function getSum(a: number, b: number): number {
  while (b !== 0) {
    const carry = (a & b) << 1;   // where both bits are 1 → carry up
    a = a ^ b;                    // add the columns, ignoring carry
    b = carry;                    // now add the carry in
  }
  return a;
}

⏱️ 5 · Complexity

⚠️ 6 · Pitfalls — and the test that catches each

📊 Coverage — pattern → LeetCode (medium & hard)

Own each pattern and these are in range. Bold = Hard tier.

✅ 7 · Self-check

Cover the right column (blurred — hover/tap to reveal). Say your answer out loud first.

Write these cold (no peeking)

• idioms isPowerOfTwo, popcount (Kernighan), get/set/clear/toggle
• xor singleNumber + singleNumberIII
• bitmask subsets + submask enumeration
• arithmetic getSum (add without +)

For each: write what each bit means (flag? set member? digit?) as a comment before the code.