And as expected, this one is covered by Knuth in his "Bitwise Tricks and Techniques" section of TAOCP (pages 133–202 of Volume 4A, which start with "Now comes t

And as expected, this one is covered by Knuth in his "Bitwise Tricks and Techniques" section of TAOCP (pages 133–202 of Volume 4A, which start with "Now comes the fun part"). Specifically, this one is equation (84) on page 150, or page 18 of the draft (pre-fascicle 1a) here: https://cs.stanford.edu/~knuth/fasc1a.ps.gz https://cs.stanford.edu/~knuth/fasc1a.ps.gz 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.