The Competitive Programmer's Handbook on page 99 suggests the following way of going through all subsets of a set x (the set bits represent the numbers in the set):
int b = 0;
do {
// Process subset b
} while (b = (b - x) & x);
I understand all the background about bit representation and bitwise operators.
What I am not understanding is why b = (b - x) & x results in getting the next subset.
This post gives an example, but does not provide an insight.
So, why does this work?
Things become clearer when we remember two's complement. The negative of a number is just 1 plus the bitwise NOT of that number. Thus,
(b - x) = (b + ~x + 1)
Let's work through an example of one iteration of the algorithm. Then I'll explain the logic.
Suppose
x = . 1 1 . . 1 .
b = . [.][.] . . [1] .
^
where . denotes zero.
Let's define "important" bits to be the bits that are in the same position as a 1 in x. I've surrounded the important bits with [], and I've marked the right-most important zero in b with ^.
~x = 1 [.][.] 1 1 [.] 1
~x + b = 1 [.][.] 1 1 [1] 1
~x + b + 1 = 1 [.][1] . . [.] .
(~x + b + 1) & x = . [.][1] . . [.] .
Notice that ~x + b always has a string of ones to the right of the right-most important zero of b. When we add 1, all those ones become zeros, and the right-most important zero becomes a 1.
If we look only at the important bits, we see that b transformed from [.][.][1] into [.][1][.]. Here are what the important bits will be if we continue:
[.][1][.]
[.][1][1]
[1][.][.]
[1][.][1]
[1][1][.]
[1][1][1]
If we write the important bits side-by-side like this, as if they were a binary number, then the operation effectively increments that number by 1. The operation is counting.
Once all the important bits are ones, (b - x) & x simply becomes (x - x) & x, which is 0, causing the loop to terminate.
By that point, we've encountered all 2^n possible values of the n important bits. Those values are the subsets of x.