4 ms·

I wonder what the real-world applications for this are

CGamesPlay 4y ago
It can be used to enumerate all subsets of size N from a set of size M. Start with 1 << N - 1, and then repeatedly call this function until the value is larger than 1 << M. Every subset of size N will be visited, in order.
- TeMPOraL 4y ago
  Can you explain what you mean by "set" and "subset"? What do they contain? How they're represented? I can't make heads or tails of your answer as-is.
  - rzzzt 4y ago
    Iterates through all possible N-combinations of a set that has M elements?
  - doomrobo 4y ago
    Take a 64 bit number and treat it like a bit field where each bit represents inclusion/exclusion of an element in a set S of size 64. Thus every number with M 1s represents a (distinct) M-sized subset of S
  - nerdponx 4y ago
    Every bit in a bitfield represents a "thing". The bitfield represents a collection of distinct things. If bit "i" is 1, then the corresponding thing "i" is in the collection.
- kccqzy 4y ago
  That's certainly a very smart way of doing so. Years ago, I had a similar need and I consulted TAOCP to find the “standard” algorithm to do so, which is done by a binomial tree. The tree T is defined recursively as T(0) = nil and T(n) = [Cons(0, T(0)), Cons(1, T(1)), ..., Cons(n-1, T(n-1))]. There's no need to construct the tree explicitly; it's just a conceptual formalism that helps formulate an algorithm to traverse the tree. The text did mention using bitwise operations to do so; in fact it says it presents a “remarkable sequence of seven bitwise operations that will convert any binary number to the lexicographically next t-combination” but I haven't been able to find those seven operations.
otherjason 4y ago
This can be used generate all bit sequences over a particular range that have the same Hamming weight. I have needed that before when testing error-correction code decoders to make sure they properly correct all of the possible error patterns that they should be able to.
psychphysic 4y ago
It's filtering by popcount effectively [0] and crops up quite a bit. [0] https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://vaibhavsagar.com/blog/2019/09/08/popcount/
- psychphysic 4y ago
  I misunderstood the task
thom 4y ago
Chess engine stuff, at the very least. With an integer mask representing an 8x8 board and 1s representing a single type of piece, you can find all subsets of pawn positions etc.
mafuy 4y ago
I've used this to enumerate grids with a certain number of open and closed cells (0 and 1 bits). It is simply the next permutation of a bit string. C++ offers this in its standard lib, but that version is slower by factor 1000 or so. I've also tested this with arbitrary bit-width numbers (LLVM can do that) and it worked fine. I've not checked if the code is the exact same tho.
- hoseja 4y ago
  >slower by factor of 1000 It's also for generic iterables.
ggm 4y ago
I'm going out on a limb and say "bloom filters" so it has applications in fast filtering, seen-count, DB stuff like parallelism, discrete-different buckets, partially ordered sets being applied in a stream of events...

It can be used to enumerate all subsets of size N from a set of size M. Start with 1 << N - 1, and then repeatedly call this function until the value is larger than 1 << M. Every subset of size N will be visited, in order.

TeMPOraL 4y ago
Can you explain what you mean by "set" and "subset"? What do they contain? How they're represented? I can't make heads or tails of your answer as-is.
- rzzzt 4y ago
  Iterates through all possible N-combinations of a set that has M elements?
- doomrobo 4y ago
  Take a 64 bit number and treat it like a bit field where each bit represents inclusion/exclusion of an element in a set S of size 64. Thus every number with M 1s represents a (distinct) M-sized subset of S
- nerdponx 4y ago
  Every bit in a bitfield represents a "thing". The bitfield represents a collection of distinct things. If bit "i" is 1, then the corresponding thing "i" is in the collection.
kccqzy 4y ago
That's certainly a very smart way of doing so. Years ago, I had a similar need and I consulted TAOCP to find the “standard” algorithm to do so, which is done by a binomial tree. The tree T is defined recursively as T(0) = nil and T(n) = [Cons(0, T(0)), Cons(1, T(1)), ..., Cons(n-1, T(n-1))]. There's no need to construct the tree explicitly; it's just a conceptual formalism that helps formulate an algorithm to traverse the tree. The text did mention using bitwise operations to do so; in fact it says it presents a “remarkable sequence of seven bitwise operations that will convert any binary number to the lexicographically next t-combination” but I haven't been able to find those seven operations.

otherjason 4y ago

This can be used generate all bit sequences over a particular range that have the same Hamming weight. I have needed that before when testing error-correction code decoders to make sure they properly correct all of the possible error patterns that they should be able to.

psychphysic 4y ago

It's filtering by popcount effectively [0] and crops up quite a bit. [0] https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://vaibhavsagar.com/blog/2019/09/08/popcount/

psychphysic 4y ago
I misunderstood the task

thom 4y ago

Chess engine stuff, at the very least. With an integer mask representing an 8x8 board and 1s representing a single type of piece, you can find all subsets of pawn positions etc.

mafuy 4y ago

I've used this to enumerate grids with a certain number of open and closed cells (0 and 1 bits). It is simply the next permutation of a bit string. C++ offers this in its standard lib, but that version is slower by factor 1000 or so. I've also tested this with arbitrary bit-width numbers (LLVM can do that) and it worked fine. I've not checked if the code is the exact same tho.

hoseja 4y ago
>slower by factor of 1000 It's also for generic iterables.

ggm 4y ago

I'm going out on a limb and say "bloom filters" so it has applications in fast filtering, seen-count, DB stuff like parallelism, discrete-different buckets, partially ordered sets being applied in a stream of events...