Subsets as Bitmasks
In short: give each of n items a bit position, and every number from 0 to 2ⁿ−1 is a
different subset — bit i is 1 when item i is in it. Counting upward visits every subset
exactly once in O(n · 2ⁿ) time, and set algebra becomes bit operations: union is |,
intersection is &, difference is a & ~b, and membership is a >> i & 1. It's
O(1) extra space per mask, since a whole subset lives in one machine word, so this is a
tool for small n, not for n = 40.
Quarry's query planner has a handful of candidate indexes it could keep in memory: by id, by shard, by epoch, by type. Each costs memory and each speeds up some queries. Which combination should it keep? With a few candidates, the honest answer is to try every combination and keep the best. That's 2ⁿ subsets for n candidates, and this lesson shows the cheapest way to walk them: count.
In the algorithm-design section you generated subsets with backtracking, a recursive
tree of "take it or leave it" choices. Bitmasks flatten that whole tree into a single
for loop over integers. There's no recursion and no call stack, and each subset is
stored in one machine word.
A subset is a number
Give each of the n items a bit position. A subset is then an n-bit number whose bit i
is 1 when item i is in it. Every n-bit number from 0 to 2ⁿ − 1 is a different
subset, and every subset is one of those numbers. Counting upward visits them all:
Counting from 0 to 7 in three bits visits every subset of three indexes exactly once.
mask 0 = 000 selects nothing. That's the empty set, keeping no indexes at all. 3 cells. At index 2.
In code, turning a mask back into items is one comprehension:
mask = 0b1101
print([i for i in range(4) if mask >> i & 1])The cost is the number of masks times the work per mask, O(n · 2ⁿ) to list every subset. That's fine for n = 20, which is about 20 million steps, and impossible for n = 40. Bitmask enumeration is a tool for small n. When n is small, it's often the simplest correct solution there is.
The classic slip is precedence again. This planner should see all 8 subsets:
It prints 4 ['id', 'shard']. Subtraction binds tighter than <<, so the range stops at 1 << 2 and half the subsets never appear.
Set operations become bit operations
Once subsets are masks, set algebra is single instructions:
| Set operation | Mask operation |
|---|---|
| A ∪ B | a | b |
| A ∩ B | a & b |
| A − B | a & ~b |
| is item i in A? | a >> i & 1 |
| A ⊆ B | a & b == a |
| |A| | a.bit_count() |
This is a bitset, and you'll see it throughout the course. The capstone uses one to record which shards a batch of records touches. A bitset of 64 items fits in one word, and a union of two sets costs a single OR.
Gray code: one change per step
Plain counting sometimes flips many bits at once. Going from 3 to 4 flips all three.
If each subset needs expensive work to set up, such as loading an index or recomputing a
total, you'd rather each step change one item. The Gray code
g = i ^ (i >> 1) gives exactly that. It visits every mask, and consecutive masks
differ in exactly one bit:
print([i ^ (i >> 1) for i in range(4)])In Gray order the same eight subsets appear, but each step adds or removes exactly one index.
Start from the empty set, 000. 3 cells. At index 2.
That property turns a running total into an O(1) update per step. Trace a Gray-order walk that keeps the memory cost of the chosen indexes up to date without re-adding:
Enumerating only the submasks
Sometimes you want the subsets of a particular set m, not of everything. Looping
over all 2ⁿ masks and skipping those with bits outside m wastes time. This loop
visits only the submasks, in decreasing order:
s = m
while True:
...use s...
if s == 0: break
s = (s - 1) & mSubtracting 1 borrows through the low bits, and & m throws away every bit outside m.
The result is the next smaller number made only of m's bits.
m = 0b1011
count = 0
s = m
while True:
count += 1
if s == 0:
break
s = (s - 1) & m
print(count)Run it yourself. The greyed cells are bits outside m, which the loop never turns
on. Change m to see how the number of frames tracks 2 ** m.bit_count():
Your submask loop only ever lights bits inside m, so it takes 2 to the popcount of m frames, not 2 to the width.
Summed over every mask m of n bits, the submask walks cost 3ⁿ in total. Each item is
outside m, in m but not s, or in both. That 3ⁿ is the price of the DP-over-subsets
problems in the planning section, and of the capstone exercise below.
How large can n get? Quarry allows its planner about ten million steps per decision, and enumerating all subsets of n candidate indexes costs about n·2ⁿ steps:
| n | n·2ⁿ steps |
|---|---|
| 10 | 10,240 |
| 16 | 1,048,576 |
| 18 | 4,718,592 |
| 19 | 9,961,472 |
| 20 | 20,971,520 |
n = 19 just fits. One more candidate more than doubles the cost to 21 million. Exponential cost has a hard wall, and the planner should switch to a greedy or DP method well before 20 candidates.
Interview corner — an even split
Quarry has up to 16 shards, each with a known size in GB. Can they be divided between
two machines so both hold exactly the same total? Every division is a mask, where
bit i on means shard i goes to machine A. So you check 2ⁿ masks and compare each
subset's sum with half the total:
It's exponential, and that's fine for 16 shards. A DP on sums, from the dynamic-programming lesson, scales in the total instead. Knowing which regime you're in is what the question is really testing.
Quick practice
a, b = 0b1100, 0b1010
print(a & b, a | b, a & ~b)It prints False True — backwards. mask & i treats i as a bitmask, not a bit position. Fix the test.
🎯 Your turn
Write pick_indexes(sizes, gains, budget). Index i costs sizes[i] MB and saves
gains[i] ms per query. Try every subset and return the indices of the subset with
the largest total gain whose total size is <= budget, in increasing order. If two
subsets tie on gain, prefer the one using less memory. The tests never tie beyond
that. Keeping nothing ([]) is always allowed.
pick_indexes([40, 25, 60], [9, 5, 12], 70)→[0, 1](65 MB, gain 14)pick_indexes([80], [10], 50)→[]
Hint — loop mask over range(1 << n), compute the subset's size and gain, skip it
if it's over budget, and keep the best (gain, -size) seen so far.
Then press ▶ Run, try the Live App chips, and hit ✓ Check. ✅