Bit manipulation, permutate bits

Question

I am trying to make a loop that loops through all different integers where exactly 10 of the last 40 bits are set high, the rest set low. The reason is that I have a map with 40 different values, and I want to sum all different ways ten of these values can be multiplied. (This is just out of curiosity, so it's really the "bitmanip"-loop that is of interest, not the sum as such.)

If I were to do this with e.g. 2 out of 4 bits, it would be easy to set all manually,

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

but with 10 out of 40 I can't seem to find a method to generate these effectively. I tried, starting with 1023 ( = 1111111111 in binary), finding a good way to manipulate this, but with no success. I've been trying to do this in C++, but it's really the general method(if any) that is of interest. I did some googling, but with little success, if anyone has a good link, that would of course be appreciated too. :)

Answer 1

You can use any standard implementation of a choose/combination algorithm. Basically you want to choose 10 bits, out of 40, that will be set to 1.

That said, 40 choose 10 is 847,660,528. And that number will be multiplied by however many possible "tail" bits that aren't in the top 40. Presumably the tail bits aren't subject to any rules, so if there are k bits, that would be another 2^k factor.

This algorithm, even once you implement it, will be very slow. It may be a good idea to think of a better approach to solve whatever problem you have.

Related questions

• Algorithm to return all combinations of k elements from n