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

Question

Given that x is a set, the following code goes through the subsets of a set x:

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

I came across this reading about bit manipulation and how it's used to represent sets.

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

The usage of the code is as follows:

#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;
}

The output given by the above code is:

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

Answer 1

Easy parts first:

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?

Yes.

A do/while loop like this:

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

does the following steps:

1. Execute cout << b<<"\n";.
2. Execute b = (b-x)&x and remember the result.
3. If the result isn't zero, go back to step 1.

= is assignment. It sets a variable to a value, as in i = 0;. But... huh? What's the result of an assignment? In C, the result of an assignment is the value that was assigned. This lets you write a = b = c = 0;, to set three variables a, b and c to 0. This is equivalent to a = (b = (c = 0));, i.e. it sets c to 0, then it sets b to the result of that, then it sets a to the result of that. (In C++ it's possible to write a class which doesn't follow this rule, but we're only dealing with ints here, not classes)

Some people like to use this trick to make their code shorter. You could've written it like this instead:

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

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

= is assignment. - is subtraction. & is "bitwise AND".

This subtracts x from b. Then, it bitwise-ANDs the answer to that with x. Then, it sets b to the answer to that.

What is bitwise AND? Bitwise AND is an operation where you write down the numbers in binary, lines them up, then creates a new number, where each bit is 1 if the bits in both inputs are 1, and 0 otherwise. Example:

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

so 90 & 232 is 72.

How does it work?

This program is basically treating the numbers as binary. Each bit in x is 1 to say something is "in the set", or 0 to say that it's not.

b then goes through all the possible combinations of those bits. b = (b-x) & x; is a bit of a "voodoo magic spell" to change the combination to the next one in order, for example:

  - 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...

You can be sure that whoever invented this trick was very clever.