为什么 b = (b - x) & x 导致获得下一个子集？

Question

第 99 页的 Competitive Programmer's Handbook 建议采用以下方式遍历集合的所有子集 x（集合位表示集合中的数字）：

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

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

Answer 1

当我们记住 two's complement 时，事情会变得更加清晰。一个数的负数就是 1 加上该数的按位非。因此，

(b - x) = (b + ~x + 1)

让我们来看一个算法迭代的例子。那我再解释一下逻辑。

假设

x =                 .  1  1  .  .  1  .
b =                 . [.][.] .  . [1] .
                          ^

其中 . 表示零。

让我们将“重要”位定义为与 x 中的 1 处于相同位置的位。我用 [] 包围了重要的位，并且用 ^.

标记了 b 中的 right-most 重要的零

~x =                1 [.][.] 1  1 [.] 1
~x + b =            1 [.][.] 1  1 [1] 1
~x + b + 1 =        1 [.][1] .  . [.] .
(~x + b + 1) & x =  . [.][1] .  . [.] .

请注意 ~x + b 总是在 b 的 right-most 重要零的右侧有一串 1。当我们添加 1 时，所有这些都变成零，并且 right-most 重要的零变成 1.

如果我们只看重要的位，我们会看到 b 从 [.][.][1] 变成了 [.][1][.]。如果我们继续，以下是重要的部分：

[.][1][.]
[.][1][1]
[1][.][.]
[1][.][1]
[1][1][.]
[1][1][1]

如果我们像这样写重要的位 side-by-side，就好像它们是二进制数一样，那么该操作实际上将该数字递增 1。该操作正在计数。

一旦所有重要位都为 1，(b - x) & x 就变成了 (x - x) & x，即 0，导致循环终止。

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

的子集

为什么 b = (b - x) & x 导致获得下一个子集？

Why does b = (b - x) & x result in getting the next subset?

bit-manipulation