Iterating Subsets

Common iteration patterns:

// All masks from 0 to 2^n - 1
for mask := 0 to (1 << n) - 1 // All submasks of a given mask (decreasing order)
for sub := mask; sub > 0; sub := (sub - 1) & mask
// Don't forget sub = 0 if needed // All masks with exactly k bits set
// Use bitmask enumeration or next_permutation trick

The submask trick $(\text{sub} - 1) \land \text{mask}$ generates all subsets of mask. Subtracting $1$ flips the lowest set bit and sets all lower bits. The AND keeps only bits from the original mask.

Total work across all masks: $\sum_{\text{mask}} 2^{\text{popcount(mask)}} = 3^n$. Each bit is either absent, present in mask only, or present in both. Three choices per bit gives $3^n$.