Submask

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.