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

Question

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

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

我看到这篇关于位操作及其如何表示集合的文章。

表达式b=(b-x)&x是什么意思？它是如何工作的？我熟悉 == 但不熟悉 = 在 do while 循环中。这是如何运作的？当 (b-x)&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;
}

以上代码给出的输出为：

Answer 1

首先是简单的部分：

Does the loop terminate when the value of (b-x)&x becomes zero? I'm familiar with == but not with = being here in the do while loop. How does that work?

是的。

一个 do/while 循环是这样的：

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

执行以下步骤：

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

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

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

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

What does the expression b=(b-x)&x mean?

= 是赋值。 -是减法。 & 是“按位与”。

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

什么是按位与？按位与是一种操作，您可以在其中记下二进制数字，将它们排列起来，然后创建一个新数字，其中如果 both 输入中的位为 1 和 0，则每个位为 1除此以外。示例：

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

所以 90 和 232 是 72。

How does it work?

该程序基本上将数字视为二进制。 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...

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

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

What does the expression "b=(b-x)&x" mean?

c++

loops

bit-manipulation

set