How does this algorithm generate all subsets of a set

I am currently taking a course in query optimization and I have an algorithm that calculates the costs of joining all subsets of a given set of relations. To do that, we are given a subroutine enumerating all these subsets. In our script, it says: "[...] code fragment with which subset bitvector representations can be generated very efficiently. In C, this fragment looks as follows:

S1 = S & - S;
do { /* do something with subset S1 */
S1 = S & (S1 - S);
} while (S1 != S);

S represents the input set. S1 iterates through all subsets of S where S itself and the empty set are not considered.

However, I do not understand it: When we take the set difference of S and S, we get the empty set. So the while loop will always output the empty set as S1 and never terminate. What am I missing?

> When we take the set difference of S and S, we get the empty set. So the while loop will always output the empty set as S1 and never terminate. What am I missing?

S and S1 are integers used as bitvectors, meaning that each bit corresponds to one of the possible set elements, with the presence or absence of that element in the subset corresponding to whether its bit takes the value 1 or 0. The difference operator - is not a set difference, it is an arithmetic difference.

The code assumes two's complement representation for signed integers. In this convention, the representation of the arithmetic inverse of any operand can be formed by flipping all the bits of its representation and adding 1 to the result (treating it as an unsigned operand and ignoring overflow). From this emerges the property that S & - S evaluates to an integer in which all bits are zero except the least-significant bit (if any) that is set in S.

Example: Suppose S is a 32-bit integer with value 22. The binary representation of S is

00000000000000000000000000010110

Flipping all the bits produces

11111111111111111111111111101001

Adding 1 produces

11111111111111111111111111101010

, which is the representation of -22. Computing the bitwise & with S turns off all bits that are not set in S, yielding

00000000000000000000000000000010

. As advertised, this has all bits zero except the bit at the position of the least-significant 1 bit in S.

The S1 = S & (S1 - S) would perhaps be more easily understood if reformulated as S1 = S & (S1 + (-S)), or even better as S1 = S & (S1 + (~S) + 1). Given that all the bits that are set in S1 are also set in S, adding ~S just turns on all the bits that are not set in S, too. Furthermore adding 1 to that will flip all the least-significant bits up to and including the first that is not set in S1 + (~S), which is necessarily one that is set in S (because we just turned on all the ones that weren't). Then the bitwise & turns back off all the bits that are not set in S. The overall result is as if we count upward by one, using a counter composed of only those bits that are set in S.

Example: continuing from the above, S1 + ~S is

00000000000000000000000000000010 + 11111111111111111111111111101001
==
11111111111111111111111111101011

Adding 1 yields

11111111111111111111111111101100

And masking off the bits not set in S yields

00000000000000000000000000000100

You can verify for yourself that the next iterations produce, in succession

00000000000000000000000000000110
00000000000000000000000000010000
00000000000000000000000000010010
00000000000000000000000000010100
00000000000000000000000000010110

, where the last of those is equal to S.

It may also be interesting to note that the original S1 = S & -S is just a special case of this, as if S1 were initially 0: S1 = S & (0 - S).

Note well that the formulation you asked about serves the general case, where the initial S is an arbitrary subset of all the possible elements. If we could assume that S would be a bitvector representing all possible elements, using its rightmost bits, then we could use this alternative, which is much easier to follow:

for (int S1 = 1; S1 < S; S1++) {
    /* do something with subset S1 */
}

Note also that there is a flaw in the original code presented. It is supposed to avoid considering the full set S or the empty set, but it will consider both before it stops if S represents a set containing exactly one element. To avoid that, it needs to test the termination condition before the first iteration, maybe just by using a while loop instead of a do .. while:

S1 = S & - S;
while (S1 != S) {
    /* do something with subset S1 */
    S1 = S & (S1 - S);
}