In submask enumeration, why does s = (s - 1) & m walk exactly the subsets of mask m?

## What a submask is If a mask `m` encodes a set, a *submask* `s` is a mask whose set bits are a subset of `m`'s set bits — formally `(s & m) == s`. A mask with k set bits has 2^k submasks, from `m` itself down to 0. The question is how to visit all of them without testing all 2^n candidate integers and filtering, which would waste time proportional to the whole universe rather than to `m`. ## Why the step works The idiom is: ``` s = m repeat: use s if s == 0: stop s = (s - 1) & m ``` Take the step apart. **`s - 1`.** In binary, subtracting one from a non-zero value performs a borrow: the lowest set bit becomes 0, and every bit below it (which were all 0) becomes 1. Bits above the lowest set bit are untouched. So `10100 - 1` = `10011`. **`& m`.** The borrow may have set bits at positions `m` does not contain — they were 0 in `s` only because they are outside `m` entirely, or because `s` had already cleared them. ANDing with `m` erases every position outside `m` and keeps every position inside it. The bits that survive are: all of `s`'s bits above the borrow point, plus all of `m`'s bits below it. That combination is precisely the largest submask of `m` that is strictly less than `s`. It is smaller, because the borrow cleared a bit and everything restored below is worth less than the bit removed. It is the largest such value, because the borrow filled every lower position `m` allows. And it is a submask, because the AND guarantees it. A step that always jumps to the *immediately preceding* submask, starting from the largest, therefore enumerates all of them in strictly decreasing order, exactly once each, with no duplicates and no gaps. ## A trace Let `m = 1010` (decimal 10, elements at positions 1 and 3). It has 2^2 = 4 submasks. | step | s (binary) | s - 1 | (s - 1) & m | |---|---|---|---| | 1 | 1010 | 1001 | 1000 | | 2 | 1000 | 0111 | 0010 | | 3 | 0010 | 0001 | 0000 | | 4 | 0000 | — | stop | Visited: `1010`, `1000`, `0010`, `0000` — the four submasks, decreasing, each once. Notice step 2: `s - 1` produced `0111`, three bits that are mostly nonsense for this mask, and the AND cleaned them down to the single legal bit `0010`. That salvage step is the whole trick. ## The termination trap The natural-looking form ``` s = m while s != 0: use s s = (s - 1) & m ``` is wrong for most uses: it exits before processing `s = 0`, so the empty submask is never seen. If the algorithm partitions a group into a chosen part and a leftover part, dropping the empty submask means dropping the case "assign nothing here, everything to the other side" — often a legal and sometimes optimal answer. The safe shapes are a `repeat … until` with the break after the body (shown above), or an explicit `use 0` after the loop. When authors write the `while s != 0` form deliberately, they are excluding the empty case on purpose and should say so in a comment. A second, rarer trap: if `m` itself is 0, the correct enumeration is the single submask 0, which the break-after-body form handles and the `while` form skips entirely. ## Cost, and where 3^n comes from Enumerating the submasks of one mask with k set bits costs 2^k steps — proportional to the answer size, which is optimal. The interesting number is the total when you do this for *every* mask of an n-element universe, which is the shape that appears in set-partition algorithms: sum over all m of 2^(popcount(m)) = 3^n The clean argument is per element rather than per mask: for a given (m, s) pair, each of the n elements is in exactly one of three states — inside `s` (hence inside `m`), inside `m` but outside `s`, or outside `m` altogether. Three independent choices for each of n elements gives 3^n pairs. The naive alternative — loop over all 2^n masks and, for each, test all 2^n candidates for submask-hood — costs 4^n, and for n = 20 that is the difference between about 3.5 billion and about a trillion. Candidates who quote 4^n have described the filtering approach, not this one. ## When you reach for it The pattern shows up whenever a mask must be split into a part and its complement within the mask: covering a set of shifts with one qualified group at a time, partitioning a roster into teams, or any "choose some of the currently-available items, recurse on the rest" shape. The complement of `s` inside `m` is `m & ~s` — cheap, and available on every iteration, which is why the pair (s, m ^ s) falls out of the same loop for free.