News for hackers. Stuff that matters.
Re:EABitTricks.h by CGamesPlay on Monday December 19, 2022 @11:50AM (#34054286)
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.
Re:EABitTricks.h by TeMPOraL on Monday December 19, 2022 @12:04PM (#34054483)
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.
Re:EABitTricks.h by doomrobo on Monday December 19, 2022 @12:12PM (#34054585)
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
Re:EABitTricks.h by rzzzt on Monday December 19, 2022 @12:09PM (#34054551)
Iterates through all possible N-combinations of a set that has M elements?
Re:EABitTricks.h by nerdponx on Monday December 19, 2022 @12:48PM (#34055070)
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.
Re:EABitTricks.h by kccqzy on Monday December 19, 2022 @03:01PM (#34056860)
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.