Creating multiple numbers with certain number of bits set

Question

Problem

I need to create 32 Bit numbers (signed or unsigned doesn't matter, the highest bit will never be set anyway) and each number must have a given number of Bits set.

Naive Solution

The easiest solution is of course to start with the number of zero. Within a loop the number is now increased by one, the number of Bits is counted, if the count has the desired value, the number is stored to a list, if not the loop just repeats. The loop is stopped if enough numbers have been found. Of course this works just fine, but it's awfully slow once the number of desired Bits gets very high.

A Better Solution

The simplest number having (let's say) 5 Bits set is the number where the first 5 Bit are set. This number can be easily created. Within a loop the first bit is set and the number is shifted to the left by one. This loop runs 5 times and I found the first number with 5 Bits set. The next couple of numbers are easy to create as well. We now pretend the number to be 6 Bit wide and the highest one is not set. Now we start shifting the first zero bit to the right, so we get 101111, 110111, 111011, 111101, 111110. We could repeat this by adding another 0 to front and repeating this process. 0111110, 1011110, 1101110, etc. However that way numbers will grow much faster than necessary, as using this simple approach we leave out numbers like 1010111.

So is there a better way to create all possible permutations, a generic approach, that can be used, regardless how many bits the next number will have and regardless how many set bits we need set?

Answer 1

You either need Factoradic Permutations (Google on that) or one of algorithms on Wiki

Answer 2

Try approaching the problem from the opposite way round - what you're trying to do is equivalent to "find n numbers in the range 0-31".

Suppose you're trying to find 4 numbers. You start with [0,1,2,3] and then increase the last number each time (getting [0,1,2,4], [0,1,2,5] ...) until you hit the limit [0,1,2,31]. Then increase the penultimate number, and set the last number to one higher: [0,1,3,4]. Go back to increasing the last number: [0,1,3,5], [0,1,3,6]... etc. Once you hit the end of this, you go back to [0,1,4,5] - eventually you reach [0,1,30,31] at which point you have to backtrack one step further: [0,2,3,4] and off you go again. Keep going until you finally end up with [28,29,30,31].

Given a set of numbers, it's obviously easy to convert them into the 32 bit numbers.

Answer 3

You can use the bit-twiddeling hack from hackersdelight.org.

In his book he has code to get the next higher number with the same number of one-bit set.

If you use this as a primitive to increase your number all you have to do is to find a starting point. Getting the first number with N bits set is easy. It's just 2^(N-1) -1.

You will iterate through all possible numbers very fast that way.

  unsigned next_set_of_n_elements(unsigned x) 
  {
     unsigned smallest, ripple, new_smallest, ones;

     if (x == 0) return 0;
     smallest     = (x & -x);
     ripple       = x + smallest;
     new_smallest = (ripple & -ripple);
     ones         = ((new_smallest/smallest) >> 1) - 1;
     return ripple | ones;
  }

  // test code (shown for two-bit digits)

  void test (void)
  {
    int start = 3; // pick a number with two bits set..
    int i;

    for (i=0; i<100; i++)
    {
       printf ("next number is %d\n", a);
       a = next_set_of_n_elements(a);
    }
  }

The code (and other variations of the trick) can be found here:

http://hackersdelight.org/HDcode/snoob.c

Answer 4

You want to generate combinations, see this Wikipedia article.