“b=(bx)&x”是什么意思？

Question

鉴于 x 是一个集合，以下代码遍历集合 x 的子集：

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

我读到了有关位操作及其如何用于表示集合的阅读。

表达式b=(bx)&x是什么意思？它是如何工作的？我熟悉==但不熟悉=在 do while 循环中。这是如何运作的？当 (bx)&x 的值变为零时循环是否终止？

代码的用法如下：

#include <iostream>

using namespace std;

void subsets(int x, int b){
    do{
        cout << b<<"\n";
    }while(b = (b-x)&x);
}

int main()
{
    int x = (1<<1)|(1<<3)|(1<<4)|(1<<8);
    int b = 0;
    subsets(x, b);
    return 0;
}

上面代码给出的输出是：

0
2
8
10
16
18
24
26
256
258
264
266
272
274
280
282

Answer 1

首先是简单的部分：

当 (bx)&x 的值变为零时循环是否终止？我熟悉 == 但不熟悉 do while 循环中的 = 。这是如何运作的？

是的。

do像这样的 /循环while：

do{
    cout << b<<"\n";
}while(b = (b-x)&x);

执行以下步骤：

1. 执行cout << b<<"\n";。
2. 执行b = (b-x)&x并记住结果。
3. 如果结果不为零，则返回步骤 1。

=是作业。它将变量设置为一个值，如 中所示i = 0;。但是……嗯？任务的结果是什么？在 C 中，赋值的结果就是被赋值的值。这让您可以编写a = b = c = 0;、 来设置三个变量a、b和c为 0。这相当于a = (b = (c = 0));，即它设置c为 0，然后设置b为 0 的结果，然后设置a为 0 的结果。（在 C++ 中，可以编写一个不遵循此规则的类，但我们int这里只处理 s，而不是类）

有些人喜欢使用这个技巧来缩短他们的代码。你可以这样写：

do{
    cout << b<<"\n";
    b = (b-x)&x;
}while(b);

表达式 b=(bx)&x 是什么意思？

=是作业。-是减法。&是“按位与”。

这x从 中减去b。然后，将答案与 进行按位与运算x。然后，它设置b为该问题的答案。

什么是按位与？按位与是一种运算，您以二进制形式写下数字，将它们排列起来，然后创建一个新数字，其中如果两个输入中的位均为 1 ，则每位为 1，否则为 0。例子：

    01011010 = 90
  & 11101000 = 232
  -----------------
    01001000 = 72

所以 90 & 232 是 72。

它是如何工作的？

该程序基本上将数字视为二进制。中的每一位x都是 1 表示某个东西“在集合中”，或者是 0 表示它不在集合中。

b然后遍历这些位的所有可能的组合。b = (b-x) & x;有点像“巫毒咒语”，可以按顺序将组合更改为下一个，例如：

  - 000000000 <- b the first time
    011001001 <- x
 -----------------
    100110111 <- b-x
  & 011001001 <- x
 -----------------
    000000001 <- (b-x)&x (b the second time)
  - 011001001 <- x
 -----------------
    100111000 <- b-x
  & 011001001 <- x
 -----------------
    000001000 <- (b-x)&x (b the third time)
  - 011001001 <- x
 -----------------
    100111111 <- b-x
  & 011001001 <- x
 -----------------
    000001001 <- (b-x)&x (b the fourth time)
 ...etc...

可以肯定，发明这个技巧的人非常聪明。