3 ms·

My favourite bit of bit twiddling doesn't seem to appear here - how to enumerate all the subsets of bits set. Like so many bit-twiddling hacks, I first saw this

by thom 4y ago

My favourite bit of bit twiddling doesn't seem to appear here - how to enumerate all the subsets of bits set. Like so many bit-twiddling hacks, I first saw this in chess engines: https://www.chessprogramming.org/Traversing_Subsets_of_a_Set https://www.chessprogramming.org/Traversing_Subsets_of_a_Set

moonchild 4y ago
Wow, that's beautiful. On modern hardware, I would probably have just used the pext hammer, which would perform fine, but not with anything approaching the elegance of that solution.
deleted 4y ago
[deleted]
chucksmash 4y ago
I could swear this site shut down for lack of hosting resources in early 2019. All I can find now in reference to this is a reddit thread saying it was DOS'd around that time. I remember when I could access the site intermittently, they were displaying a banner saying they were going to take it offline permanently. Wonderful to see things didn't work out that way, thanks for posting.
- thom 4y ago
  Oh, that would be a tragedy. Honestly it is up there with c2.com for me in the hours I've spend just marvelling at people's knowledge!
rockwotj 4y ago
I used this trick to land my first Silicon Valley when I was asked to generate the power set in an interview. It seemed to impress my interviewer a lot.
svat 4y ago
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.

by thom 4y ago

moonchild 4y ago

Wow, that's beautiful. On modern hardware, I would probably have just used the pext hammer, which would perform fine, but not with anything approaching the elegance of that solution.

deleted 4y ago

[deleted]

chucksmash 4y ago

I could swear this site shut down for lack of hosting resources in early 2019. All I can find now in reference to this is a reddit thread saying it was DOS'd around that time. I remember when I could access the site intermittently, they were displaying a banner saying they were going to take it offline permanently. Wonderful to see things didn't work out that way, thanks for posting.

thom 4y ago
Oh, that would be a tragedy. Honestly it is up there with c2.com for me in the hours I've spend just marvelling at people's knowledge!

rockwotj 4y ago

I used this trick to land my first Silicon Valley when I was asked to generate the power set in an interview. It seemed to impress my interviewer a lot.

svat 4y ago

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.