Creating multiple numbers with a specific number of bits

Question

Problem

I need to create 32 bit numbers (signed or unsigned does not matter, the most significant bit will never be set in any case), and each number must have a given number of bits.

Naive decision

The simplest solution is, of course, to start from scratch. In the cycle, the number now increases by one, the number of bits is counted, if the counter has the desired value, the number is stored in the list if the cycle does not repeat. The loop is stopped if enough numbers are found. Of course, this works great, but it's terribly slow as soon as the number of desired bits gets very high.

The best decision

The simplest number having (say) 5 Bits, a given number in which the first 5 bits are set. This number can be easily created. Inside the 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. The following pair of numbers is easy to create. Now we will pretend that the number should be 6 bits wide, and the top one is not set. Now we begin to shift the first zero bit to the right, so we get 101111, 110111, 111011, 111101, 111110. We could repeat this by adding another edge and repeat this process. 0111110, 1011110, 1101110, etc. However, in this way the numbers will grow much faster than necessary, because, using this simple approach, we leave numbers like 1010111.

So, is there a better way to create all possible permutations, a general approach that you can use, regardless of how many bits the next number will have and no matter how many sets of bits you need to set?

Answer 1

You can use a bit-twiddling hack with hackersdelight.org .

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

If you use this as a primitive to increase your number, all you have to do is find the starting point. Getting the first number with N bitmaps is very simple. It is just 2 ^ (N-1) -1.

You will very quickly sort through all possible numbers.

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); } } 

Answer 2

Try to approach the problem from the opposite side - what you are trying to do is equivalent to "find n numbers in the range 0-31".

Suppose you are trying to find 4 numbers. You start with [0,1,2,3], and then each time increase the last number (getting [0,1,2,4], [0,1,2,5] ...) until you reach the limit [0,1,2,31]. Then increase the penultimate number and set the last number one higher: [0,1,3,4]. Go back to increase the last number: [0,1,3,5], [0,1,3,6] ... etc. As soon as you reach the end of this, you will return to [0,1,4, 5] - in the end you will reach [0,1,30,31], at this moment you need to go back to the next step: [0,2, 3.4] and exit again. Continue until you are finally done with [28,29,30,31].

Given a set of numbers, it is obviously easy to convert them to 32-bit numbers.

Answer 3

You want to generate combinations, see this Wikipedia article .

Answer 4

You either need factorial permutations (Google), or one of the Wiki algorithms