Bit Manipulation & Bitmask DP

The 10-second versionCopy Anchor Link

Underneath every type you've ever used, a computer has exactly one alphabet: bits. The operators &, |, ^, ~, << and >> act on all the bits of a word at once — one instruction for thirty-two or sixty-four of them — and a few arithmetic tricks fall straight out of them: x & (x - 1) clears the lowest set bit, x & -x isolates it, XOR makes pairs cancel so the lone unpaired number survives, and popcount counts the ones. Then the big idea: because a bit can mean "in or out," a subset is just an integer. That lets you do dynamic programming over all 2ⁿ subsets — the state is a bitmask — which is exactly how the travelling salesman problem is solved exactly.

Why this existedCopy Anchor Link

There is no "true", no "5", no "A" in the hardware — only voltages we call 0 and 1, and every operation a CPU performs is some function of those bits. We talk about &, | and ^ because they act on a whole word in parallel: one instruction, many booleans. That free parallelism is the reason bits are worth learning instead of just tolerating.

The ideas are old and load-bearing:

• 1854 — George Boole publishes An Investigation of the Laws of Thought, an algebra for true and false. AND, OR and NOT — the operations we now call bitwise.
• 1937 — Claude Shannon, still a master's student, shows in his thesis that Boolean algebra maps perfectly onto electrical relay circuits. That single insight is why a computer is a digital machine: logic became hardware.
• 1962 — Held and Karp solve the travelling salesman problem by doing dynamic programming over subsets, encoding each subset as an integer. Bitmask DP is born.
• 1972 — MIT's HAKMEM memo collects a pile of bit-level "hacks" that remain the folklore of the field; Henry Warren's Hacker's Delight (2002) writes them all down.
• Today — a POPCNT instruction counts set bits in a cycle, and chess engines represent an entire board position as a handful of 64-bit integers.

Why it mattered then: Shannon's thesis turned an abstract algebra into a wiring diagram, and every chip since is that idea etched in silicon. The tricks and the subset trick are just us reading that hardware back out at the programming level.

Inside the inventor's headCopy Anchor Link

The first realisation is simply this: a word is a row of independent booleans, and a bitwise instruction is a row operation. That's why x & y is "multiply two bit-vectors for free" and why a single ^ across a whole array can cancel out everything that appears twice.

From there the tricks start to fall out, each a small piece of arithmetic worth internalising. Take clearing the lowest set bit. Subtracting 1 from a number flips its lowest 1 to 0 and turns every bit below it into 1. AND the original with that and the lowest set bit — and only it — vanishes: x & (x - 1). Do this in a loop and you've counted the set bits in as many iterations as there are ones, not bits. Take the negative instead and you isolate the lowest set bit: x & -x (two's complement lines everything up so exactly one bit survives). That one is the secret engine inside Fenwick trees.

The first attempt at "find the number that appears once when every other appears twice" is a hash set — fine, but the hash is the point being missed. XOR is its own inverse: a ^ a is 0, and a ^ 0 is a. XOR everything together and every pair annihilates, leaving the odd one out in one pass and O(1) memory.

// JS bitwise ops are 32-bit and signed: stay within 32 bits, or use BigInt.const popcountNaive = (x) => {                   // test every bit  let c = 0;  while (x) { c += x & 1; x >>>= 1; }  return c;};const popcount = (x) => {                         // one iteration per set bit  let c = 0;  while (x) { x &= x - 1; c++; }                  // clear the lowest set bit  return c;};const lowestBit = (x) => x & -x;                  // isolates the lowest set bit

And then the leap. If a bit can mean "yes or no," then a whole word of bits can mean a subset: bit k set means "element k is in the subset." Suddenly a subset isn't an array you copy around — it's a single integer you can store, pass, and index. Count from 0 to 2ⁿ - 1 and you've visited every possible subset exactly once. That is the gateway to bitmask DP.

The final approachCopy Anchor Link

The vocabularyCopy Anchor Link

Six operators, and that's the whole language. Five appear as symbols below; the sixth, OR — set a bit to 1 where either side has a 1 — uses the pipe character, which is busy being the table separator here, so we name it rather than draw it:

And the tricks built from them:

The invariantCopy Anchor Link

Two different families live here, so there are two invariants. The trick invariant: every idiom above is a statement about two's-complement arithmetic — you can prove x & (x - 1) clears the lowest set bit by looking only at that bit and what borrowing does below it. The DP invariant: an integer mask in the range 0 to 2ⁿ - 1 is in one-to-one correspondence with a subset of n items, bit k meaning "item k is included." Iterating mask from 0 upward therefore visits every subset exactly once, and mask & (1 << k) is the membership test.

Bitmask DP: the travelling salesmanCopy Anchor Link

Give n cities and the distance between each pair. A tour visits every city once and returns home. The state is (which cities have I visited, where am I now) — and "which cities" is exactly a bitmask. Let dp[mask][i] be the cheapest way to start at city 0, visit exactly the set mask of cities, and end at city i:

dp[mask | (1 << j)][j] = min(dp[mask][i] + dist[i][j])    for every j not in mask

The answer is the cheapest dp[full][i] + dist[i][0]. There are 2ⁿ masks and n ending cities, and each transition tries n next cities, so it is O(2ⁿ · n²) — polynomial in 2ⁿ, which is exactly the Held–Karp bound. Enumerating the sub-masks of a fixed mask has its own idiom worth keeping in your pocket:

for (int s = mask; s; s = (s - 1) & mask) { ... }   // every non-empty sub-mask of mask

That (s - 1) & mask step drops to the next smaller set of bits that is still contained in mask — no wasted iterations on bit patterns outside it.

A worked trace: enumerating subsetsCopy Anchor Link

Take mask = 0b1011 (bits 0, 1, 3 set — three items present). The idiom s = (s - 1) & mask walks every non-empty sub-mask, largest first:

Every non-empty subset appears exactly once, and the walk stops when s reaches 0. The cost is one step per sub-mask — 2³ - 1 = 7 here — not 2³ times something, which is what makes subset-sum-of-subsets style DP turn out cheap.

Here is the full bitmask DP for the travelling salesman. Pay attention to the dp dimensions and the final closing edge home:

// JS bitwise ops are 32-bit: 1 << n is safe for n <= 30. For larger n use BigInt masks.function tsp(n, dist) {  const INF = Infinity;  const full = 1 << n;  const dp = Array.from({ length: full }, () => new Array(n).fill(INF));  dp[1][0] = 0;                                  // visited {0}, standing at city 0  for (let mask = 1; mask < full; mask++) {    if (!(mask & 1)) continue;                   // tours must start at city 0    for (let i = 0; i < n; i++) {      if (!(mask & (1 << i)) || dp[mask][i] === INF) continue;      for (let j = 0; j < n; j++) {        if (mask & (1 << j)) continue;           // already visited        const next = mask | (1 << j);        dp[next][j] = Math.min(dp[next][j], dp[mask][i] + dist[i][j]);      }    }  }  let best = INF;  for (let i = 1; i < n; i++)    best = Math.min(best, dp[full - 1][i] + dist[i][0]);  return best;}

ComplexityCopy Anchor Link

The bit tricks are Θ(1) (or Θ(bits) for a whole-word scan) because they touch a fixed number of machine words. The DP is where the 2ⁿ shows up: better than the n! of brute force, but still exponential — a reminder that some exact problems simply don't have a small polynomial algorithm.

Where you meet it todayCopy Anchor Link

• Chess and board games. Bitboards store the whole position as a few 64-bit integers per piece type; sliding moves are shifts and masks, and "which squares are attacked" is one AND. This is why strong engines can search millions of positions per second.
• Fenwick trees and lowbit. Every Fenwick update does i & -i to jump to the next node — the "isolate lowest set bit" trick from this very page.
• Similarity search and bioinformatics. Hamming distance between two fingerprints is popcount(a ^ b); that's the core of SimHash, locality-sensitive hashing, and fast genomic comparisons.
• Networking and systems. Permission masks, feature flags, bitmap indexes and Bloom filters are all "a set as an integer" — bits packing many booleans into one word.

Here's a taste of each flavour, mixing the tricks with the subset-as-integer idea:

// JS has no native 64-bit integer: stay within 32 bits, or reach for BigInt.const isSet = (mask, k) => (mask & (1 << k)) !== 0;   // 32-bit board maskconst lowbit = (i) => i & -i;                          // lowest set bitconst hamming32 = (a, b) => {                          // 32-bit fingerprints  let x = a ^ b, c = 0;  while (x) { x &= x - 1; c++; }                       // one step per differing bit  return c;};const hamming64 = (a, b) => {                          // 64-bit via BigInt  let x = BigInt(a) ^ BigInt(b), c = 0n;  while (x) { x &= x - 1n; c++; }  return Number(c);};

RecapCopy Anchor Link

• Bits are the machine's native language; &, |, ^, ~ and the shifts act on a whole word in parallel.
• Memorise the classics: x & (x - 1) clears the lowest set bit, x & -x isolates it, XOR cancels pairs so the unique number survives, and popcount counts the ones.
• A subset of n items is exactly an integer in 0 to 2ⁿ - 1; mask & (1 << k) tests membership and counting enumerates every subset once.
• Bitmask DP — TSP, assignment — is exponential (O(2ⁿ · n²)), but exact and vastly better than n!.
• In JavaScript, bitwise operators are 32-bit: keep masks within 32 bits, or switch to BigInt.

Next up: Segment Trees — a structure that uses these low-bit tricks to answer range queries fast.