https://www.chessprogramming.org/Traversing_Subsets_of_a_Set
https://www.chessprogramming.org/Traversing_Subsets_of_a_Set
Note that as he mentions, this method actually walks through the subsets of a set in "proper" order (increasing order of the numbers): the operation (x-X)&X actually finds the next largest x' that is a subset of X.
I had to work out an example in detail to understand it better: Suppose we're running through subsets of {2, 3, 5, 7}, represented by the bitset X=0b10101100:
(76543210)
…10101100
Suppose we're currently at the subset {2, 5}, represented by x = 0b100100: (543210)
x = 100100
Then we want to go to the next subset {3, 5}. We can do this by:• Taking (x|X̅), in this case:
(9876543210)
(x|X̅) = …1101110111
• Adding 1 to it: (9876543210)
(x|X̅)+1 = …1101111000
• Then keeping only the ones that are still compatible with X: (543210)
((x|X̅)+1)&X = 101000
With some algebra we can see that we get the same result by doing (x-X)&X.Basically, "the next subset" means "find the smallest element not in the current subset, add it to the current subset, and remove everything smaller than it" which is exactly what's going on with the +1 and carries.
Wonderful to see things didn't work out that way, thanks for posting.