17. Bit Manipulation

TL;DR

Encode choices and state in the bits of integers: XOR cancels duplicates, bitmasks enumerate subsets, lowbit tricks clear the least significant 1, and a few masks test class membership (for example power of two). Use this pattern when the domain is boolean per position, XOR canceling pairs, or small n with 2^n states.

Recognition Cues

• Phrases: "single number appears once, others twice", "swap without extra variable", "count set bits", "all subsets", "is power of two", "bitwise AND/OR/XOR", "only one bit differs".
• Shapes: small n (often n <= 20 for 1 << n); array of integers with paired-XOR story; need to flip or mask by position.
• Constants: 1 << index to isolate bit index.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Mental Model

XOR is associative/commutative; value XOR value is 0, so a pile of numbers cancels in pairs and leaves the odd one out. Brian Kernighan clears the lowest set bit: value & (value - 1); repeat until zero to count ones. A bitmask is a row of n independent yes/no flags; mask from 0 to (1 << n) - 1 visits all subsets. Power of two (positive) has exactly one bit: value & (value - 1) == 0 (with value > 0).

Generic Recipe

1. Classify the task: XOR cancel, bit count, subset iterate, or single-bit predicate.
2. For XOR "one unique": fold entire array with XOR, or XOR indices with values for "missing number" patterns.
3. For population count: loop with value & (value - 1) or use language intrinsics in production.
4. For all subset bits: for mask := 0; mask < (1 << n); mask++ and test membership with mask & (1 << bit) != 0.
5. Never assume sign of shift in Go: use uint for 1 << index when index is large to avoid surprises; check language shift rules.

Complexity

• Time: XOR pass (O(n)); Brian Kernighan count (O(\text{number of set bits})); enumerate all masks (O(2^n \cdot n)) if you scan bits per mask.
• Space: (O(1)) extra for classic tricks; (O(1)) for bitmask loop variable.

Generic Code Template

Go

package main

func singleNumberXOR(values []int) int {
	answer := 0
	for _, value := range values {
		answer ^= value
	}
	return answer
}

func countSetBitsBrianKernighan(value int) int {
	count := 0
	for value != 0 {
		value &= value - 1
		count++
	}
	return count
}

func enumerateSubsetsMask(elementCount int, visit func(mask int)) {
	limit := 1 << elementCount
	for mask := 0; mask < limit; mask++ {
		visit(mask)
	}
}

func isPowerOfTwoPositive(value int) bool {
	return value > 0 && value&(value-1) == 0
}

func swapWithoutTemp(left, right *int) {
	if left == right {
		return
	}
	*left ^= *right
	*right ^= *left
	*left ^= *right
}

func main() {}

JavaScript

function singleNumberXor(values) {
  return values.reduce((accumulator, value) => accumulator ^ value, 0);
}

function countSetBitsBrianKernighan(value) {
  let bits = value >>> 0;
  let count = 0;
  while (bits !== 0) {
    bits &= bits - 1;
    count += 1;
  }
  return count;
}

function enumerateSubsetsMask(elementCount, visit) {
  const limit = 1 << elementCount;
  for (let mask = 0; mask < limit; mask += 1) {
    visit(mask);
  }
}

function isPowerOfTwoPositive(value) {
  return value > 0 && (value & (value - 1)) === 0;
}

function swapWithoutTemp(pair) {
  let [left, right] = pair;
  if (left === right) {
    return pair;
  }
  left ^= right;
  right ^= left;
  left ^= right;
  return [left, right];
}

Useful bit operations (reference)

Variants

• XOR tricks — single unique, two uniques (segment into groups), missing number with index XOR.
• Bit count — Brian Kernighan, lookup table for bytes, hardware popcount.
• Bitmask DP — when subsets matter with constraints (Dynamic programming pattern).
• Arithmetic via bits — add without + (full adder style), multiply by shifts.

Representative Problems

• 136. Single Number — XOR cancellation
• 191. Number of 1 Bits — Brian Kernighan / popcount
• 268. Missing Number — XOR or sum index trick

Anti-patterns

• Shifting 1 in Go with a signed large shift amount—prefer explicit uint64 for masks when n is big.
• Using XOR swap on aliased pointers to the same memory (no-op or wrong); guard same-address case.
• Enumerating 1 << n when n is 30+ without noticing overflow / exponential blowup.
• Confusing logical versus arithmetic right shift on signed types (especially in JavaScript, use >>> for unsigned 32-bit intent).