Bitmask Enumeration — Subsets & Submasks

How to read this

• Mode 1 (all subsets): the loop for mask in 0 .. 2ⁿ−1 treats each integer as a subset. Watch the bit row turn each integer into the set of present elements; the log records every one of the 2ⁿ subsets in increasing integer order.
• Mode 2 (submasks): pick a mask; the loop s = (s − 1) & mask walks every subset contained in it, in strictly decreasing order, ending at the empty set 0. Amber-bordered bits are in the mask; green-filled bits are in the current submask.
• Counts to verify: Mode 1 produces exactly 2ⁿ rows; Mode 2 produces exactly 2^{popcount(mask)} rows. Try a few masks and confirm.
• The 3ⁿ idea: summing the Mode-2 row count over every possible mask gives Σ 2^{popcount(mask)} = 3ⁿ — the cost of "submasks of every mask".
• Controls: Step advances one subset/submask; Run auto-plays; Reset rebuilds with the current n and mask.
• Bit positions: each cell shows the bit value (0/1) and its element index i; the big binary string at top mirrors the same value, high bit on the left.
• Try this: in Mode 2 set mask = 0 — the only submask is the empty set, so the walk is a single step. Set mask = (1<<n)−1 — every subset is a submask, so Mode 2 matches Mode 1 exactly.
• Decreasing order: note Mode 2 starts at the mask itself and ends at 0, each step strictly smaller — that is why the loop terminates without an explicit counter.
• Progress bar: the bar fills as a fraction of the total subsets/submasks, giving an at-a-glance sense of how many remain.