Bit manipulation, permutation bit

Question

I am trying to create a loop that will go through all different integers, where exactly 10 of the last 40 bits are set high, the rest are set to low. The reason is because I have a map with 40 different values, and I want to summarize all the different ways so that ten of these values ​​can be multiplied. (This is just out of curiosity, so this is really a “bitmanip” loop of interest, not the amount as such.)

If I did this, for example, 2 out of 4 bits, it would be easy to set everything manually,

0011 = 3, 0101 = 5, 1001 = 9, 0110 = 6, 1010 = 10, 1100 = 12, 

but with 10 out of 40, I can’t find a way to create them effectively. I tried starting at 1023 (= 1111111111 in binary), finding a good way to manipulate this, but without success. I tried to do this in C ++, but this is really a general method (if any) that is of interest. I made some kind of search engine, but with little success, if anyone has a good link, this, of course, will be appreciated. :)

Answer 1

A bit more complicated, but done exclusively with bit manipulation. Your example:

 #define WIDTH 4 #define BITS 2 void printbits(long pattern) { long bit; for (bit = 1L << WIDTH - 1; bit; bit >>= 1) putchar(pattern & bit ? 49 : 48); putchar('\n'); } void movebits(pattern, bit) { long mask = 3L << bit; while (((pattern ^= mask) & mask) && (mask < 1L << WIDTH)) { mask <<= 1; printbits(pattern); if (bit) movebits(pattern, bit - 1); } } int main() { long pattern = (1L << BITS) - 1L, mask; printbits(pattern); movebits(pattern, BITS - 1); } 

Your real application:

 #define WIDTH 40 #define BITS 10 

and, as polygenic lubricants say, get ready to wait a bit :) Of course, you will replace printbits with something more useful to you ...

(Edited for insufficient testing: / Damn typos ...)

Answer 2

You can use any standard implementation of the selection / combination algorithm. Basically you want to select 10 bits, out of 40, which will be set to 1 .

However, 40 choose 10 - 847 660 528 . And this number will be multiplied by the many possible “tail” bits that are not in the top 40. Presumably, the tail bits are not subject to any rules, so if there are k bits, this will be 2 ^{k more} .

This algorithm, even if you implement it, will be very slow. It might be nice to think of a more effective approach to solving any problem that you have.

Related Questions

• Algorithm for returning all combinations of k elements from n

Answer 3

You can just use next_permutation . Here's a sample for playing your 2 out of 4 cases (the order changes a bit):

 #include <iostream> #include <algorithm> using namespace std; int main () { int bits[] = {0,0,1,1}; do { for (int i = 0; i < 4; ++i) cout << bits[i] << " "; cout << endl; } while ( next_permutation (bits,bits+4) ); return 0; } 

Answer 4

There is a very non-obvious way to do this efficiently: the Gosper method for finding the next higher integer with the same number of bits 1 , from HAKMEM , paragraph 175.

 lowest_1_bit = prev_combo & -prev_combo; tmp = prev_combo + lowest_1_bit; new_combo = (((prev_combo ^ tmp) >> 2) / lowest_1_bit) | tmp; 

• the first line finds the rightmost bit 1 ;
• the second causes the rightmost start 1 bit to 0 , and 0 only to the left of the run to 1 ;
• the third line replaces bits 1 that were lost by the second line, at the bottom of the word.

Now (if you are using a 64-bit integer type), you can start with 1023 and just reapply it (until the result exceeds 1<<40 ).

Answer 5

This is simpler if you rewrite this as a set of nested loops indicating bit positions:

 0011 = 0 1 0101 = 0 2 1001 = 0 3 0110 = 1 2 1010 = 1 3 1100 = 2 3 

That is, the position P1 of the first bit works from 0 to 3-1, and the position of the second bit P2 is repeated from P1 + 1 to 3. Inclusion of this in the general recursive function remains as an exercise.