Bit Manipulation

How to think about it

XOR is its own inverse: pairs vanish. n & (n-1) drops the lowest set bit. n & -n isolates it. Bitmasks encode subsets of a small universe (n ≤ 20) for DP or enumeration.

Template shapes

Shape	Core move	Notes
XOR fold	x ^= a[i]	Single number
Lowest bit	n & -n / n & (n-1)	Count / remove
Mask DP	for mask in 0..1<<n	Subsets

Complexity baseline

Often O(n) word ops, or O(2^n · n) for subset DP.

From template to problem

1. Map the problem to a bitwise identity.
2. Watch language-specific int size.
3. Prefer bit tricks over O(n) scans when the identity is clear.
4. For masks: iterate submasks carefully if needed.

/** Bit template: single number via XOR fold. */
export function singleNumber(nums: number[]): number {
  let x = 0;
  for (const v of nums) x ^= v;
  return x;
}

/** Bit template: single number via XOR fold. */
export function singleNumber(nums: number[]): number {
  let x = 0;
  for (const v of nums) x ^= v;
  return x;
}