Submask (source code)
= Submask
A <submask> of a <bit mask> $m$ is a <bit mask> $s$ whose <bit>[set bits] are all set in $m$, equivalently $s\mathbin{\&}m=s$. It represents a <subset> of the positions selected by $m$. If $m$ has $k$ <bit>[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)\mathbin{\&}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.<Enumerating submasks of a bitmask in the CP-Algorithms documentation>[Enumerating all submasks of a given mask]{ref} The number of outputs is exponential in the number of selected positions, even though each fixed-word update is inexpensive.
Back to article page
