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?

Dufy

See also: Generate all binary strings of length n with k bits set – Stannary

using the natural (also refered as Lehmer) mapping between representation of integers in combinadic form (combinatorial number system) and actual (lexicographicaly-sorted combinations) does the generation. Handling binary representations of numbers is the key to generating both combinations, permutations and power sets – Girlie

Answer 1

You can use the bit-twiddling 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.

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 bits = 2;
    int a = pow(2,bits) - 1;
    int i;

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

Filip

Wow, this is even better. Actually Jon Skeet's reply already have me an idea for a simple algorithm to get what I'm looking for, but this is even easier (though I probably never came up with something as clever as this piece of code!) :-) – Dufy

Oh - you don't have to come up with such tricks. It's just handy to know what tricks are out there and remember them if they help to solve a problem. I've only done one bit-twiddeling hack ever, and it's highly architecture specific. – Filip

Cool! Since smallest will always be power of 2, it "feels like" there should be a faster way to shift new_smallest right by that much than using a division, but I can't think of a way... – Scarborough

@j_random_hacker: Take a look at the other solutions that are in the link I've posted. You'll find versions that do the same and avoid the division by using count_leading_zeros ect. Most CPU's can execute these in a single cycle. You get rid of the division that way. – Filip

@NilsPipenbrinck It gives me error "unary minus operator applied to unsigned type". I think it has something to do with "unsigned". – Stallfeed

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.

Moores

Wow, this is tricky! You are absolutely right: why would I want to fiddle around with bits. Actually I need to only permute bit positions and bit positions can be expressed as numbers. This turns my problem into a much easier, solvable problem. – Dufy

Answer 3

You want to generate combinations, see this Wikipedia article.

Fandango

Answer 4

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

Jeraldjeraldine