# how doest subsets of subsets iteration works?

`for ( x = y; x > 0; x = ( y & (x-1) ) )`

generates all subsets of bitmask y.

How does this iteration works? Any intuitive explaination?

see suboptimal solution section.

Intuition: Taken as a number, the bitmask `y` cannot have more than `y` subsets. So, by counting down `x`, you are guaranteed to hit every subset of `y` by bitmasking. But this creates a lot of duplicates. Think about `1101`. If you count down from that and mask with `y`, the sequence will go. `1101`, `1100`, `1001`, `1000`, `1001`, `1000`, and so on. By assigning `x` 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`, and `0`, are emitted in that order.

Now suppose this procedure works for bitstrings of length `N`. Suppose `Z` is a bitstring of length `N`. If you create the bitstring `0Z`, then you follow the same sequence as for `Z` along, since subtraction does not ever turn on higher order bits. If you create the bitstring `1Z`, then the following happens: For the first `2^nnz(Z)` steps, the original `Z` sequence is followed, with `1` prepended. And for the last `2^nnz(Z)` steps, the original `Z` sequence is followed, with `0` prepended. Since the procedure visits every element of the smaller sequence twice, prepending `1` the first time, and `0` the second, we conclude that the procedure emits every subset of `1Z`.

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 to `0`) we'll pass through binary representations

``````111, 110, 101, 100, 011, 010, 001, 000
``````

which in a rather obvious way to represent all possible subsets of an original 3-set.

The second fact is that in binary "to decrement `x`" ("to subtract 1 from `x`") means: to invert all bits of `x` starting from the least significant (rightmost) one and to the left up to (and including) the first `1` in the representation of `x`. "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 of `x` are always a subset of `1` bits of `y`, since we begin with `x = y` and do `x = (whatever) & y` on every iteration.

When we do `x - 1` we "turn off" (set to `0`) the lowest `1` in `x` and "turn on" (set to `1`) all `0` in `x` to the right from that lowest `1`.

When we follow that with `& y` in `x = (x - 1) & y` we "turn off" some original bit of `y` in `x` and "turn on" all lower original bits of `y` in `x`.

At this point it should already be fairly obvious that this operation is simply a "masked decrement" of `x`: by doing `x = (x - 1) & y` we simply decrement the value of `x` under assumption that only bits masked by `y` form the value of `x`, while all other bits are just negligible "padding bits".

To draw the parallel to the above example with decrementing `7`, the initial value of `y` might look as `10010100`. Operation `x = (x - 1) & y` will see this value as a "distributed 7" of sorts (speaking informally). The `x` will proceed through the following values

``````1..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" of `x`, which do not really participate in this "masked decrement" operation (in reality they will be `0`). Note the similarity with the original example with `7`.