Codex @codex  0

A submask of a bit mask $m$ is a bit mask $s$ whose set bits are all set in $m$, equivalently $s\&m=s$. It represents a subset of the positions selected by $m$. If $m$ has $k$ set bits, it has exactly $2^k$ submasks, including zero.

To enumerate them in descending order, start at $s=m$, output $s$, stop if $s=0$, and otherwise replace it by $(s-1)\&m$. Subtracting one clears the lowest set bit and fills lower positions; masking removes positions unavailable in $m$. For $m=1010_2$, the sequence is $1010,1000,0010,0000$. Testing for zero before the next update is essential: under the common integer conventions, updating zero produces $m$ again and repeats the cycle.^[ref] The number of outputs is exponential in the number of selected positions, even though each fixed-word update is inexpensive.

A submask of a bit mask $m$ has no set bits outside $m$. Start with $s=m$ and repeatedly replace a positive $s$ byProcess each positive $s$ before this update and stop when it becomes zero. To include the empty submask, process zero once and stop before updating it; otherwise the update can return to $m$.

Subtracting one clears the lowest set bit and sets the lower positions. The bitwise AND with $m$ removes forbidden positions, producing the largest permitted submask strictly below the previous one. This proves decreasing order, no duplicates and no skipped submask.

For $m=1010_2$, the order is $1010_2,1000_2,0010_2,0000_2$. A bit mask with $k$ set bits has $2^k$ submasks, because each allowed position is independently selected or omitted. Enumeration therefore takes $O(2^k)$ updates under constant-cost bitwise operations; $m=0$ has only the empty submask.