Core Bit Tricks

Enumerate All Subsets of a Mask

To iterate all subsets of a bitmask: start with s = mask, then repeatedly do s = (s-1) & mask until s is 0. This skips bits not in the original mask. Used in bitmask DP optimizations.

O(2^n * n)

O(2^n)

say this out loud

Iterating submasks with sub equals sub minus one and mask visits every subset exactly once, which is the standard companion to bitmask DP.

How It Works

To enumerate every subset of a given bitmask, start with s = mask and repeatedly apply s = (s - 1) & mask until s reaches zero. Subtracting 1 produces the next smaller integer, and ANDing with the mask snaps it down to the largest value that uses only the mask's bits, so the loop visits every submask exactly once, in strictly decreasing order, without ever touching bits outside the mask.

A mask with k set bits has 2^k submasks, and each is generated in O(1), so enumeration costs O(2^k) instead of the naive O(2^n) scan over all integers with a containment filter. In bitmask DP, iterating submasks of every mask totals O(3^n) across the whole table (each of the n bit positions independently being in the mask, in the submask, or in neither), which is the standard bound for subset-sum-over-subsets style transitions.

Step-by-Step Visualization

Enumerate every submask of 101, meaning every mask whose set bits are a subset of these

found0

1/9

Code

Java

static List<Integer> enumerateSubsets(int mask) {
  List<Integer> subsets = new ArrayList<>();
  int s = mask;
  while (s > 0) {
    subsets.add(s);
    s = (s - 1) & mask;
  }
  subsets.add(0); // Empty subset
  return subsets;
}
// enumerateSubsets(0b101) → [5, 4, 1, 0] → [101, 100, 001, 000]

Tips & Gotchas

1Iterate s = mask, then s = (s-1) & mask until s = 0

2This enumerates all subsets of the bitmask

3Total subsets of mask with k bits = 2^k

Practice Problems

1Partition to K Equal Sum Subsets
2The Number of Good Subsets
3Maximum Students Taking Exam
4Smallest Sufficient Team

About the Core Bit Tricks Pattern

Fundamental bit operations that appear in many problems. These are building blocks. Memorize them.

Key insight

Key tricks: n & (n-1) clears lowest set bit (power-of-2 check). XOR of all elements cancels pairs. Bit masks can represent subsets for DP. These are often O(1) space solutions.

Common Bit Manipulation Interview Problems

Single Number
Number of 1 Bits
Counting Bits
Missing Number
Reverse Bits
Power of Two

Frequently Asked Questions

Why does (s - 1) & mask visit every submask exactly once?

Restricted to the mask's bit positions, submasks correspond one-to-one with k-bit integers, and (s - 1) & mask is exactly the decrement operation in that compressed space. Starting from the full mask and decrementing until zero therefore walks all 2^k submasks in descending order with no repeats.

Why is iterating submasks of all masks O(3^n) rather than O(4^n)?

Count pairs (mask, submask) directly: each bit position independently has three consistent states. Set in both, set only in the mask, or set in neither. Three choices across n positions gives 3^n total pairs, which is the true cost of a subset-over-subsets DP.

Does the loop include the empty subset and the mask itself?

It starts at the full mask, so that is included, but the standard do-while formulation must run once more when s hits zero to emit the empty submask, a common off-by-one. Decide whether your DP transition needs the empty or full submask and guard accordingly to avoid self-transitions.