# how does subset of subset loop works?

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


how does this loop gives all subset of y.

I can see that it prints all the subsets but how do it intuitively understand/prove that it should print the subsets and that loop will execute 2^n -1 times?

source :
10th point in http://codeforces.com/blog/entry/18169#comment-407423

Consider an example of y = 11000111. x starts off equal to y, and at every step x decreases by 1 until it hits 11000000. Now x-1 is 10111111, and to discard the bits not present in y it is $\text{AND}$ed with y. So x becomes 10000111, and it goes on.

To summarize you start with x = y and keep decreasing its value by 1 until the last sequence of 1 s is exhausted. Then at the next step x-1 flips all the low bits upto the lowest set 1, which leaves a continuous trailing sequence of 1 s. To remove the 1 s not present in y, \text{AND} it with y, and repeat. This counts down through only the set bits in y.

1 Like