how doest subsets of subsets iteration works?
i read
for ( x = y; x > 0; x = ( y & (x1) ) )
generates all subsets of bitmask y.
How does this iteration works? Any intuitive explaination?
source : http://codeforces.com/blog/entry/45223
see suboptimal solution section.
2 answers

Intuition: Taken as a number, the bitmask
y
cannot have more thany
subsets. So, by counting downx
, you are guaranteed to hit every subset ofy
by bitmasking. But this creates a lot of duplicates. Think about1101
. If you count down from that and mask withy
, the sequence will go.1101
,1100
,1001
,1000
,1001
,1000
, and so on. By assigningx
the result of the masking operation, you skip to its last occurrence.Proof: This leads to a simple proof by induction. Clearly, for bit strings of length 1, this procedure works. The only two subsets,
1
, and0
, are emitted in that order.Now suppose this procedure works for bitstrings of length
N
. SupposeZ
is a bitstring of lengthN
. If you create the bitstring0Z
, then you follow the same sequence as forZ
along, since subtraction does not ever turn on higher order bits. If you create the bitstring1Z
, then the following happens: For the first2^nnz(Z)
steps, the originalZ
sequence is followed, with1
prepended. And for the last2^nnz(Z)
steps, the originalZ
sequence is followed, with0
prepended. Since the procedure visits every element of the smaller sequence twice, prepending1
the first time, and0
the second, we conclude that the procedure emits every subset of1Z
.Taken together, we see that the procedure works for all bit strings.

The first simple fact that is used here is that if we, say, take value
7
(111
in binary) and start decrementing it repeatedly (all the way to0
) we'll pass through binary representations111, 110, 101, 100, 011, 010, 001, 000
which in a rather obvious way to represent all possible subsets of an original 3set.
The second fact is that in binary "to decrement
x
" ("to subtract 1 fromx
") means: to invert all bits ofx
starting from the least significant (rightmost) one and to the left up to (and including) the first1
in the representation ofx
. "To the left" here means "in direction of increasing bit significance".E.g.
00001000  1 = 00000111, i.e. we invert the `1000` tail 01010101  1 = 01010100, i.e. we invert just the `1` tail 10000000  1 = 01111111, i.e. we invert the whole thing and so on
The decrement operation "turns off" the least significant
1
bit in the binary representation and "turns on" all zero bits to the right of it.Now, the third fact is that in your case
1
bits ofx
are always a subset of1
bits ofy
, since we begin withx = y
and dox = (whatever) & y
on every iteration.When we do
x  1
we "turn off" (set to0
) the lowest1
inx
and "turn on" (set to1
) all0
inx
to the right from that lowest1
.When we follow that with
& y
inx = (x  1) & y
we "turn off" some original bit ofy
inx
and "turn on" all lower original bits ofy
inx
.At this point it should already be fairly obvious that this operation is simply a "masked decrement" of
x
: by doingx = (x  1) & y
we simply decrement the value ofx
under assumption that only bits masked byy
form the value ofx
, while all other bits are just negligible "padding bits".To draw the parallel to the above example with decrementing
7
, the initial value ofy
might look as10010100
. Operationx = (x  1) & y
will see this value as a "distributed 7" of sorts (speaking informally). Thex
will proceed through the following values1..1.1.., 1..1.0.., 1..0.1.., 1..0.0.., 0..1.1.., 0..1.0.., 0..0.1.., 0..0.0..
where
.
designates the "pading"bits" ofx
, which do not really participate in this "masked decrement" operation (in reality they will be0
). Note the similarity with the original example with7
.