12 ms·

My favorite so far /// GetNextWithEqualBitCount /// How to get the next higher integer with the same number of bits set. /// This function is suppo

by ot 4y ago

My favorite so far /// GetNextWithEqualBitCount /// How to get the next higher integer with the same number of bits set. /// This function is supposed (claim by original author) to be able to /// wrap around and continue properly, but testing indicates otherwise. /// Do not call this with x = 0; as that causes a divide by 0. /// Doesn't work for an input of all bits set. /// Do not assign the result of this to a type of less size than the input argument. /// This function has certain real-world applications. /// This function has been called 'snoob' by some.

Centigonal 4y ago
snoob - I want to know why
- rparolin 4y ago
  snoob = Same Number Of One Bits https://www.geeksforgeeks.org/next-higher-number-with-same-number-of-set-bits/ https://www.geeksforgeeks.org/next-higher-number-with-same-n...
- faturan 4y ago
  It stands for "same number of one bits".
smcl 4y ago
Full marks for honesty, IMO. It'd be tempting to delete this before making it publicly visisble.
rosywoozlechan 4y ago
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...
adamnemecek 4y ago
What is the correct implementation of this?
- psychphysic 4y ago
  Have a look at popcount[0]. It's even a single instruction on many platforms [1]. [0] https://en.cppreference.com/w/cpp/numeric/popcount https://en.cppreference.com/w/cpp/numeric/popcount [1] https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://vaibhavsagar.com/blog/2019/09/08/popcount/
  - danbruc 4y ago
    This gives you the number of set bits, not the next larger number with the same number of set bits.
    - psychphysic 4y ago
      Filter larger, zip Popcount, filter with same popcount, min. If you need the full implementation spelled out I can do that when I get in from my commute home.
      - anonymoushn 4y ago
        Step 1 is computing a set of ~2^64 things?
        psychphysic 4y ago
        Lol just gotten in and looked at this at a desktop I thought we were filtering a list. My bad. Funny though. Interesting task I guess really you want to find the first (from right) and move the first set bit left to fill it.
        danbruc 4y ago
        You could keep incrementing from the current value until the population count matches again, but in the worst case - probably from 2^62 to 2^63 with a single set bit or wrapping around from 2^63 to 2^0 - that would still take pretty much 2^64 steps.
danbruc 4y ago
If the wrap around does not work anyway, you can do the following and have it also work for all zeros and all ones. At least I think so, this is a bit ad hoc without putting too much thought into it. edges = x & (x ^ (x >> 1)) edge = edges & -edges mask = edge | (edge << 1) x ^= mask If you are willing to accept a conditional expression, this will make the wrap around work, I currently have no good idea how to make it work without a condition. x = (mask == 0) ? x <<< popcount(x) : x ^ mask The idea is as follows. To increase the number, you have to toggle some bit from zero to one, and to make the increase as small as possible, it should be as far to the right as possible. But to keep the number of ones the same, you also have to toggle one bit from one to zero. This one must not be to the left of the bit you toggle from zero to one or the number would decrease, otherwise it should be as far to the left as possible to make the number as small as possible. In essence this means that you have to find the rightmost occurrence of 01 and turn it into 10. x ^ (x >> 1) finds all the 01 and 10 edges, edges = x & (x ^ (x >> 1)) finds only the 01 edges. edge = edges & -edges clears all but the rightmost set bit - the two's complement first inverts all bits, then adding one turns all the ones on the right into zeros until reaching the rightmost zero which gets turned into a one - leaving use with one set bit indicating the rightmost 01 edge. mask = edge | (edge << 1) duplicates that bit and this is then used to flip the corresponding two bits with x ^= mask. Eventually all set bits will end up on the left and there will be no 01 edge leaving x stuck in this state.
- strbean 4y ago
  > I currently have no good idea how to make it work without a condition. Would this work? Or not worth computing both values each time? x = ((mask == 0) * x <<< popcount(x)) & ((mask != 0) * x ^ mask)
  - danbruc 4y ago
    I have no idea if this would be worth doing. One could also use a conditional move like CMOV on x86 if available on the target architecture to avoid a jump. On the one hand I have the gut feeling that there should be a nice trick to do this, on the other hand this seems to either require a population count dependent shift or rotation or reversing the word, which also has no really simple trick as far as I know and is usually done with a logarithmic number of shifts.
pbsd 4y ago
That appears to be a direct C++ translation of item 175 from HAKMEM [1]. This does not require a division and can be done much faster, see section 1.24 of [2]. [1] http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item175 http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item175 [2] https://jjj.de/fxt/fxtpage.html#fxtbook https://jjj.de/fxt/fxtpage.html#fxtbook
- tasty_freeze 4y ago
  > This does not require division... From the link: IDIVM D,C
  - pbsd 4y ago
    "This" as in finding the next combination. Gosper's trick does.
    - danbruc 4y ago
      The division performs a right shift, the version given in the FXT book replaces it with a while loop and has the note that one could use a bit scan and a shift. I would assume bit scan and shift is the fastest option - if accessible from the language used - but I am not sure if the loop could beat the division. Also the version from the EA library claims to - but fails to - perform the wrap around, the version in the FXT book does not try to wrap around and I would guess the version in HAKMEM also does not wrap around properly.
deleted 4y ago
[deleted]

by ot 4y ago

Centigonal 4y ago

snoob - I want to know why

rparolin 4y ago
snoob = Same Number Of One Bits https://www.geeksforgeeks.org/next-higher-number-with-same-number-of-set-bits/ https://www.geeksforgeeks.org/next-higher-number-with-same-n...
faturan 4y ago
It stands for "same number of one bits".

smcl 4y ago

Full marks for honesty, IMO. It'd be tempting to delete this before making it publicly visisble.

rosywoozlechan 4y ago

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...

adamnemecek 4y ago

What is the correct implementation of this?

psychphysic 4y ago
Have a look at popcount[0]. It's even a single instruction on many platforms [1]. [0] https://en.cppreference.com/w/cpp/numeric/popcount https://en.cppreference.com/w/cpp/numeric/popcount [1] https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://vaibhavsagar.com/blog/2019/09/08/popcount/
- danbruc 4y ago
  This gives you the number of set bits, not the next larger number with the same number of set bits.
  - psychphysic 4y ago
    Filter larger, zip Popcount, filter with same popcount, min. If you need the full implementation spelled out I can do that when I get in from my commute home.
    - anonymoushn 4y ago
      Step 1 is computing a set of ~2^64 things?
      - psychphysic 4y ago
        Lol just gotten in and looked at this at a desktop I thought we were filtering a list. My bad. Funny though. Interesting task I guess really you want to find the first (from right) and move the first set bit left to fill it.
      - danbruc 4y ago
        You could keep incrementing from the current value until the population count matches again, but in the worst case - probably from 2^62 to 2^63 with a single set bit or wrapping around from 2^63 to 2^0 - that would still take pretty much 2^64 steps.

danbruc 4y ago

If the wrap around does not work anyway, you can do the following and have it also work for all zeros and all ones. At least I think so, this is a bit ad hoc without putting too much thought into it. edges = x & (x ^ (x >> 1)) edge = edges & -edges mask = edge | (edge << 1) x ^= mask If you are willing to accept a conditional expression, this will make the wrap around work, I currently have no good idea how to make it work without a condition. x = (mask == 0) ? x <<< popcount(x) : x ^ mask The idea is as follows. To increase the number, you have to toggle some bit from zero to one, and to make the increase as small as possible, it should be as far to the right as possible. But to keep the number of ones the same, you also have to toggle one bit from one to zero. This one must not be to the left of the bit you toggle from zero to one or the number would decrease, otherwise it should be as far to the left as possible to make the number as small as possible. In essence this means that you have to find the rightmost occurrence of 01 and turn it into 10. x ^ (x >> 1) finds all the 01 and 10 edges, edges = x & (x ^ (x >> 1)) finds only the 01 edges. edge = edges & -edges clears all but the rightmost set bit - the two's complement first inverts all bits, then adding one turns all the ones on the right into zeros until reaching the rightmost zero which gets turned into a one - leaving use with one set bit indicating the rightmost 01 edge. mask = edge | (edge << 1) duplicates that bit and this is then used to flip the corresponding two bits with x ^= mask. Eventually all set bits will end up on the left and there will be no 01 edge leaving x stuck in this state.

strbean 4y ago
> I currently have no good idea how to make it work without a condition. Would this work? Or not worth computing both values each time? x = ((mask == 0) * x <<< popcount(x)) & ((mask != 0) * x ^ mask)
- danbruc 4y ago
  I have no idea if this would be worth doing. One could also use a conditional move like CMOV on x86 if available on the target architecture to avoid a jump. On the one hand I have the gut feeling that there should be a nice trick to do this, on the other hand this seems to either require a population count dependent shift or rotation or reversing the word, which also has no really simple trick as far as I know and is usually done with a logarithmic number of shifts.

pbsd 4y ago

That appears to be a direct C++ translation of item 175 from HAKMEM [1]. This does not require a division and can be done much faster, see section 1.24 of [2]. [1] http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item175 http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item175 [2] https://jjj.de/fxt/fxtpage.html#fxtbook https://jjj.de/fxt/fxtpage.html#fxtbook

tasty_freeze 4y ago
> This does not require division... From the link: IDIVM D,C
- pbsd 4y ago
  "This" as in finding the next combination. Gosper's trick does.
  - danbruc 4y ago
    The division performs a right shift, the version given in the FXT book replaces it with a while loop and has the note that one could use a bit scan and a shift. I would assume bit scan and shift is the fastest option - if accessible from the language used - but I am not sure if the loop could beat the division. Also the version from the EA library claims to - but fails to - perform the wrap around, the version in the FXT book does not try to wrap around and I would guess the version in HAKMEM also does not wrap around properly.

deleted 4y ago

[deleted]