为什么 b = (b - x) & x 会得到下一个子集？

Question

《竞争性程序员手册》第 99 页建议采用以下方法来遍历集合的所有子集x（集合位代表集合中的数字）：

int b = 0;
do {
    // Process subset b
} while (b = (b - x) & x);

我了解有关位表示和按位运算符的所有背景知识。我不明白的是为什么b = (b - x) & x会导致获得下一个子集。 这篇文章给出了一个例子，但没有提供见解。那么，为什么这会起作用呢？

Answer 1

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.

到那时，我们已经遇到了重要位2^n的所有可能值n。这些值是 的子集x。