Bit Manipulation — The Complete Guide

AND (&)  — Both bits must be 1 → 1. Otherwise → 0.
           1010 & 1100 = 1000
           Use: Check if a bit is set, clear bits, mask bits

OR  (|)  — At least one bit is 1 → 1. Both 0 → 0.
           1010 | 1100 = 1110
           Use: Set a bit, combine flags

XOR (^)  — Bits are different → 1. Same → 0.
           1010 ^ 1100 = 0110
           Use: Find unique element, toggle bits, swap without temp

NOT (~)  — Flip every bit. 0→1, 1→0.
           ~1010 = 0101 (simplified; actual result depends on bit width)
           Use: Invert a mask

LEFT SHIFT (<<)  — Shift bits left, fill with 0s. Equivalent to ×2.
                    0011 << 1 = 0110 (3 → 6)
                    Use: Multiply by powers of 2, create bit masks

RIGHT SHIFT (>>) — Shift bits right, drop rightmost. Equivalent to ÷2.
                    0110 >> 1 = 0011 (6 → 3)
                    Use: Divide by powers of 2, check individual bits

// Check if bit i is set (1)
(n >> i) & 1            // or: n & (1 << i)

// Set bit i to 1
n | (1 << i)

// Clear bit i (set to 0)
n & ~(1 << i)

// Toggle bit i
n ^ (1 << i)

// Check if n is a power of 2
n > 0 && (n & (n - 1)) === 0

// Get the lowest set bit (rightmost 1)
n & (-n)               // or: n & ~(n - 1)

// Clear the lowest set bit
n & (n - 1)

// Count set bits (Brian Kernighan's)
let count = 0;
while (n) { n &= (n - 1); count++; }

// Check if n is even/odd
(n & 1) === 0  // even
(n & 1) === 1  // odd

// Single unique element (all others appear twice)
function findUnique(nums: number[]): number {
  let xor = 0;
  for (const n of nums) xor ^= n;
  return xor;
}

// TWO unique elements (all others appear twice)
function findTwoUnique(nums: number[]): [number, number] {
  // Step 1: XOR all → gives xor of the two unique numbers
  let xor = 0;
  for (const n of nums) xor ^= n;

  // Step 2: Find any set bit (the two numbers differ here)
  const diffBit = xor & (-xor); // lowest set bit

  // Step 3: Split into two groups by that bit, XOR each group
  let a = 0, b = 0;
  for (const n of nums) {
    if (n & diffBit) a ^= n;
    else b ^= n;
  }

  return [a, b];
}
// Why this works: the two unique numbers differ in at least one bit.
// Splitting by that bit puts them in different groups.
// Within each group, all pairs still cancel, leaving one unique each.

// Count set bits (Hamming weight)
function countBits(n: number): number {
  let count = 0;
  while (n) {
    n &= (n - 1); // clear lowest set bit
    count++;
  }
  return count;
}
// Why n & (n-1) clears the lowest set bit:
// n     = ...1000  (lowest set bit is at position 3)
// n-1   = ...0111  (borrows from that bit, flips everything below)
// n&n-1 = ...0000  (the lowest set bit is gone)
//
// This runs in O(k) where k = number of set bits, not O(32).

// Hamming distance between two numbers
function hammingDistance(x: number, y: number): number {
  return countBits(x ^ y);
  // XOR gives 1s exactly where x and y differ
}

function isPowerOfTwo(n: number): boolean {
  return n > 0 && (n & (n - 1)) === 0;
}
// 8 = 1000, 7 = 0111 → 1000 & 0111 = 0000 → true
// 6 = 0110, 5 = 0101 → 0110 & 0101 = 0100 → false (not power of 2)

// Power of 4: power of 2 AND set bit is at an even position
function isPowerOfFour(n: number): boolean {
  return n > 0 && (n & (n - 1)) === 0 && (n & 0x55555555) !== 0;
  // 0x55555555 = 01010101... (bits at even positions)
}

function subsets(nums: number[]): number[][] {
  const n = nums.length;
  const result: number[][] = [];

  for (let mask = 0; mask < (1 << n); mask++) {
    const subset: number[] = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) { // bit i is set → include nums[i]
        subset.push(nums[i]);
      }
    }
    result.push(subset);
  }

  return result;
}
// For nums = [1, 2, 3]:
// mask=0 (000) → []
// mask=1 (001) → [1]
// mask=2 (010) → [2]
// mask=3 (011) → [1, 2]
// mask=4 (100) → [3]
// mask=5 (101) → [1, 3]
// mask=6 (110) → [2, 3]
// mask=7 (111) → [1, 2, 3]
// Only works for n ≤ ~20 (2^20 ≈ 1 million states)

// Reverse bits of a 32-bit integer
function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1); // shift result left, add lowest bit of n
    n >>>= 1;                          // shift n right (unsigned)
  }
  return result >>> 0; // convert to unsigned 32-bit
}
// Process one bit at a time: extract from n, place into result.
// This pattern works for any "transform bits" problem.

function singleNumber(nums: number[]): number {
  let result = 0;

  for (let bit = 0; bit < 32; bit++) {
    let sum = 0;
    for (const n of nums) {
      sum += (n >> bit) & 1; // count how many numbers have this bit set
    }
    if (sum % 3 !== 0) {
      result |= (1 << bit); // this bit belongs to the unique number
    }
  }

  return result;
}
// For each of the 32 bit positions, count how many numbers have a 1.
// If count % 3 ≠ 0, the unique number has a 1 at that position.
// This generalizes: for "appears k times except one", use count % k.

function missingNumber(nums: number[]): number {
  let xor = nums.length; // start with n (the last index)

  for (let i = 0; i < nums.length; i++) {
    xor ^= i ^ nums[i]; // XOR index and value
  }

  return xor;
}
// nums = [3, 0, 1], n = 3
// xor = 3 ^ (0^3) ^ (1^0) ^ (2^1)
//     = 3 ^ 3 ^ 0 ^ 1 ^ 0 ^ 2 ^ 1
//     = (3^3) ^ (0^0) ^ (1^1) ^ 2
//     = 0 ^ 0 ^ 0 ^ 2 = 2 ← the missing number

Input: [4, 1, 2, 1, 2]

Binary representations:
  4 = 100
  1 = 001
  2 = 010

XOR accumulation:
  result = 000 (start with 0)
  result ^= 4:  000 ^ 100 = 100
  result ^= 1:  100 ^ 001 = 101
  result ^= 2:  101 ^ 010 = 111
  result ^= 1:  111 ^ 001 = 110  ← the 1 cancels
  result ^= 2:  110 ^ 010 = 100  ← the 2 cancels

  result = 100 = 4 ✓

Key: XOR is commutative, so order doesn't matter.
Pairs cancel: 1^1 = 0, 2^2 = 0. Only 4 remains.

Why does n & (n-1) clear the lowest set bit?

Example: n = 12 = 1100

n     = 1100
n - 1 = 1011  (subtracting 1 flips the lowest set bit and all bits below it)
n & (n-1) = 1000  (the lowest set bit at position 2 is cleared!)

Another example: n = 10 = 1010
n     = 1010
n - 1 = 1001
n & (n-1) = 1000  ✓ (lowest set bit at position 1 cleared)

Power of 2 check: n = 8 = 1000
n     = 1000
n - 1 = 0111
n & (n-1) = 0000  → equals 0 → IS a power of 2 ✓

Non-power: n = 6 = 0110
n     = 0110
n - 1 = 0101
n & (n-1) = 0100  → NOT 0 → NOT a power of 2 ✓

Brian Kernighan's bit counting:
  n = 13 = 1101
  Iteration 1: 1101 & 1100 = 1100 (count=1)
  Iteration 2: 1100 & 1011 = 1000 (count=2)
  Iteration 3: 1000 & 0111 = 0000 (count=3)
  n = 0, stop. Answer: 3 set bits ✓

nums = [a, b, c]  (n = 3, so 2^3 = 8 subsets)

mask  binary  bits set    subset
────  ──────  ─────────   ──────
  0    000    none        []
  1    001    bit 0       [a]
  2    010    bit 1       [b]
  3    011    bits 0,1    [a, b]
  4    100    bit 2       [c]
  5    101    bits 0,2    [a, c]
  6    110    bits 1,2    [b, c]
  7    111    bits 0,1,2  [a, b, c]

For each mask, check each bit:
  mask = 5 (101):
    bit 0: 101 & 001 = 001 ≠ 0 → include a
    bit 1: 101 & 010 = 000 = 0 → skip b
    bit 2: 101 & 100 = 100 ≠ 0 → include c
    → subset = [a, c] ✓

This is equivalent to backtracking but uses integer arithmetic.
Faster for small n (≤ 20) because no recursion overhead.

What does the problem ask?
├── Find unique element among duplicates?
│   ├── Others appear TWICE → XOR all elements
│   ├── Others appear THREE times → bit count mod 3 at each position
│   ├── TWO unique elements → XOR all, split by differing bit, XOR groups
│   └── Missing number in 0..n → XOR values with indices
├── Count or check bits?
│   ├── Count set bits → Brian Kernighan's: n &= (n-1), count++
│   ├── Power of 2 → n > 0 && (n & (n-1)) === 0
│   ├── Power of 4 → power of 2 AND bit at even position
│   ├── Hamming distance → countBits(x ^ y)
│   └── Counting bits 0..n → DP: dp[i] = dp[i>>1] + (i&1)
├── Transform bits?
│   ├── Reverse bits → bit-by-bit: extract lowest, place in result
│   ├── Set/clear/toggle bit i → use masks: | (1<<i), & ~(1<<i), ^ (1<<i)
│   └── Swap without temp → a ^= b; b ^= a; a ^= b
├── Generate all subsets (n ≤ 20)?
│   → Bitmask: loop 0 to 2^n - 1, check each bit
└── Not sure?
    → Start with hash map / math. If O(1) space is required, think bits.