Bit Masks

A bit mask represents a subset of up to 32 items as a single integer, letting you set, clear, toggle, and test membership with O(1) bitwise operations and iterate all subsets in O(2^n) time for bitmask DP.

5 min read Level 3/5 #dsa#bits#bit-mask

What you'll learn

Set, clear, toggle, and test a single bit using shift and AND/OR/XOR
Iterate over all subsets of a given mask in order
Recognise the bitmask DP pattern for small-n combinatorial problems

A bit mask stores a subset of items as a single integer: bit k is 1 if item k is in the set, 0 if it is not. With 32-bit integers you can represent any subset of up to 32 items and perform set operations in a single CPU instruction.

The Four Fundamental Operations

Let k be the zero-based index of the bit you want to manipulate.

const set    = (mask, k) => mask |  (1 << k);  // turn bit k ON
const clear  = (mask, k) => mask & ~(1 << k);  // turn bit k OFF
const toggle = (mask, k) => mask ^  (1 << k);  // flip bit k
const test   = (mask, k) => (mask >> k) & 1;   // 1 if bit k is set, else 0

let m = 0b0000;
m = set(m, 2);    console.log(m.toString(2)); // 100
m = set(m, 0);    console.log(m.toString(2)); // 101
m = toggle(m, 2); console.log(m.toString(2)); // 001
console.log(test(m, 0)); // 1
console.log(test(m, 3)); // 0

Iterating All Set Bits

To visit only the positions that are ON, repeatedly isolate the lowest set bit with n & -n, then strip it with n &= n - 1.

function forEachBit(mask, fn) {
  let m = mask;
  while (m !== 0) {
    const lowest = m & -m;          // isolate lowest set bit
    const k = Math.log2(lowest);    // its index
    fn(k);
    m &= m - 1;                     // clear that bit
  }
}

forEachBit(0b10110, k => console.log(k)); // 1, 2, 4

Iterating All Subsets of a Mask

This loop visits every subset (including empty and the mask itself) in descending order without any extra storage.

function allSubsets(mask) {
  const subs = [];
  for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
    subs.push(sub);
  }
  subs.push(0); // include the empty subset
  return subs;
}

console.log(allSubsets(0b111).map(s => s.toString(2)));
// ['111', '110', '101', '100', '011', '010', '001', '0']

The trick sub = (sub - 1) & mask moves to the next subset by borrowing a bit and masking off positions not in the original mask.

Bitmask DP Teaser

When n is small (typically n <= 20), you can let a DP state be a bitmask representing which items have been used. The classic example is the Travelling Salesman Problem:

// dp[mask][i] = min cost to visit exactly the cities in `mask`,
// ending at city i.  mask has n bits; there are 2^n * n states.
function tspCost(dist) {
  const n = dist.length;
  const FULL = (1 << n) - 1;
  const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));
  dp[1][0] = 0; // start at city 0, only city 0 visited

  for (let mask = 1; mask <= FULL; mask++) {
    for (let u = 0; u < n; u++) {
      if (!(mask & (1 << u))) continue;
      if (dp[mask][u] === Infinity) continue;
      for (let v = 0; v < n; v++) {
        if (mask & (1 << v)) continue;
        const next = mask | (1 << v);
        dp[next][v] = Math.min(dp[next][v], dp[mask][u] + dist[u][v]);
      }
    }
  }

  let ans = Infinity;
  for (let u = 1; u < n; u++) {
    ans = Math.min(ans, dp[FULL][u] + dist[u][0]);
  }
  return ans;
}

Up Next

Count how many bits are set in an integer efficiently with Brian Kernighan’s algorithm and the popcount technique.

Counting Bits →