Bit Manipulation

Every integer is really a row of bits — binary digits, each worth a power of two. Bit manipulation means operating on those bits directly instead of on the number as a whole. Done right, it turns operations that would need a loop into a single, branch-free instruction.

The payoff is speed and elegance. Checking if a number is even, doubling it, testing membership in a small set, or finding the one unpaired value in a list — all collapse into one or two bitwise operations. The cost is that the code reads cryptically until the handful of core patterns become second nature.

Binary basics

Bits are numbered from the right starting at 0, and bit i contributes 2^i to the value. So 13 is 1101 in binary: 8 + 4 + 0 + 1. The rightmost bit tells you parity — if bit 0 is set the number is odd, otherwise even.

The operators

There are six workhorses. & (AND) keeps a bit only where both operands have it. | (OR) keeps a bit where either has it. ^ (XOR) keeps a bit where the two differ. ~ (NOT) flips every bit. << (left shift) multiplies by powers of two by sliding bits left, and >> (right shift) divides by them, sliding right.

Checking, setting, clearing, toggling a bit

The four fundamental single-bit operations all revolve around a mask — the value 1 << i, which is a single set bit at position i.

const getBit    = (x, i) => (x >> i) & 1        // read bit i (0 or 1)
const setBit    = (x, i) => x | (1 << i)        // force bit i to 1
const clearBit  = (x, i) => x & ~(1 << i)       // force bit i to 0
const toggleBit = (x, i) => x ^ (1 << i)        // flip bit i

getBit(0b1010, 1)   // 1
setBit(0b1010, 0)   // 0b1011  (11)
clearBit(0b1010, 1) // 0b1000  (8)
toggleBit(0b1010, 2)// 0b1110  (14)

The essential tricks

A few idioms show up again and again. x & (x - 1) drops the lowest set bit — loop it and count iterations to count set bits (Brian Kernighan's algorithm), or test it against zero to check if x is a power of two. x & -x isolates the lowest set bit (the backbone of Fenwick trees). And XOR-ing a list finds the lone unpaired element.

// 1. Is x a power of two? (exactly one bit set)
const isPowerOfTwo = (x) => x > 0 && (x & (x - 1)) === 0

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

// 3. Find the single number where every other value appears twice
function singleNumber(nums) {
  let acc = 0
  for (const n of nums) acc ^= n // pairs cancel to 0
  return acc
}

Bitmasks — sets in an integer

When a set is small (say up to ~20–30 items), you can pack it into a single integer where bit i means "item i is present." Membership becomes a bit test, union is |, intersection is &, and iterating all subsets is a loop over integers. This is the foundation of bitmask dynamic programming (e.g. the traveling salesman DP).

• Flags & permissions — one bit per option, combined with | and tested with &.
• Subset enumeration — iterate 0 .. (1 << n) - 1 to visit every subset of an n-element set.
• Bitmask DP — encode "which items are used" as a mask (TSP, assignment problems).
• Fast math — x << 1 doubles, x >> 1 halves, x & 1 tests oddness.