2

I have a function to increment a bitstring as follows:

void increment(boost::dynamic_bitset<> &bitset)
{   
    for (int loop = 0; loop < bitset.size(); ++loop)
    {
        if ((bitset[loop] ^= 0x1) == 0x1)
        {
            break;
        }
    }
}

I want a function that is called in the same fashion as increment would be called, but modifies the bitstring differently. Every time it is called, I want to get the next bitstring with the same number of 0s as the previous one.

For example, if the bitstring is of length 10, the first 10 calls to this function will give a bitstring with a single 0. Then, calls 11 to 20 will return bitstrings with 2 0s. I want this to continue all the way down until the bitstring is all 0s.

How could I set up such a function? Thanks!

Jim
  • 4,509
  • 16
  • 50
  • 80
  • Looks like an XY problem – Seth Carnegie Feb 16 '12 at 22:13
  • If your string only has length 10, you can just iterate over the integral range `[0, 1 << 10)` and use those integers. – Kerrek SB Feb 16 '12 at 22:18
  • @SethCarnegie Ok, clarification on the problem :) I am representing a set of large objects by a bit-string and want to do some tests on all the subsets of that bit-string. However, I know that the subsets I'm interested in usually only have a few elements from the set missing, so I want to generate all the subsets starting from only one element removed and working downwards. – Jim Feb 16 '12 at 22:20
  • @KerrekSB That was for illustration purposes. The bitstring is usually of length at least 400. – Jim Feb 16 '12 at 22:20
  • There are 9 bitstrings of length 10 with a single zero and 36 bitstrings with two zeros. There are rather a large number of bitstrings of length 400 with two zeros. It's binomial coefficients. – Don Roby Feb 16 '12 at 23:54

1 Answers1

0

You can find the answer in Matters Computational, chapter 1.24.3 "Shifts-order". You'll have to change integers to bitsets and flip the values. Possibly this implementation is not optimal when used with bitsets.

Evgeny Kluev
  • 24,287
  • 7
  • 55
  • 98