14 — Bit Manipulation

Bitwise Operators

---

Essential Tricks

// Check if n is power of 2
const isPowerOf2 = (n: number) => n > 0 && (n & (n - 1)) === 0;

// Get i-th bit (0-indexed from right)
const getBit = (n: number, i: number) => (n >> i) & 1;

// Set i-th bit to 1
const setBit = (n: number, i: number) => n | (1 << i);

// Clear i-th bit (set to 0)
const clearBit = (n: number, i: number) => n & ~(1 << i);

// Toggle i-th bit
const toggleBit = (n: number, i: number) => n ^ (1 << i);

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

// Lowest set bit
const lowestBit = (n: number) => n & (-n);

// Check if i-th bit is set
const isSet = (n: number, i: number) => (n & (1 << i)) !== 0;

---

XOR Properties

a ^ a = 0        (cancel itself)
a ^ 0 = a        (identity)
a ^ b = b ^ a    (commutative)
(a ^ b) ^ c = a ^ (b ^ c)  (associative)

Single Number (find unique in array of pairs)

function singleNumber(nums: number[]): number {
  return nums.reduce((xor, n) => xor ^ n, 0);
}
// [4,1,2,1,2] → 4^1^2^1^2 = 4 (pairs cancel)

Two Single Numbers

function singleNumbers(nums: number[]): [number, number] {
  let xor = nums.reduce((a, b) => a ^ b, 0); // a ^ b
  const diffBit = xor & (-xor); // Lowest bit where a and b differ
  
  let a = 0, b = 0;
  for (const n of nums) {
    if (n & diffBit) a ^= n;
    else b ^= n;
  }
  return [a, b];
}

---

Bitmask / Subset Enumeration

// Iterate all subsets of {0, 1, ..., n-1}
function allSubsets(n: number) {
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset: number[] = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(i);
    }
    // process subset
  }
}

// Iterate all subsets of a given mask
function subsetsOfMask(mask: number) {
  for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // process sub
  }
  // Don't forget empty subset (sub = 0)
}

---

Common Problems

Missing Number

function missingNumber(nums: number[]): number {
  let xor = nums.length;
  for (let i = 0; i < nums.length; i++) {
    xor ^= i ^ nums[i];
  }
  return xor;
}

Reverse Bits

function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>= 1;
  }
  return result >>> 0; // Unsigned
}

Power of Two

const isPowerOfTwo = (n: number) => n > 0 && (n & (n - 1)) === 0;
// 8 = 1000, 7 = 0111 → 1000 & 0111 = 0

---

Bit Manipulation in Interviews

---

Key Takeaways

• XOR is the most powerful bit trick — pairs cancel, finds unique elements
• n & (n-1) clears lowest set bit — count bits, check power of 2
• Bitmask DP uses integers to represent subsets — O(2^n) states
• Bit operations are O(1) and much faster than arithmetic equivalents
• JavaScript: use >>> 0 for unsigned 32-bit results