Fastest way to loop every number with conditions

Question

Given a 64 bit integer, where the last 52 bits to be evaluated and the leading 12 bits are to be ignored, what is the fastest way to loop every single combination of 7 bits on and all other bits off?

Example:

First permutation:

0[x57]1111111

Last permutation

00000000000011111110[x45]

Where 0[xn] means n off (zero) bits.

Speed is absolutely crucial, we are looking to save every clock cycle we can as it is part of a greater solution that needs to evaluate billions of states in a reasonable amount of time.

A working solution is not required, but some pseudo code would do just fine :)

Answer 1

What you need is a good algorithm that will take you from one permutation to the next in minimal time.

Now, the first algorithm that comes to mind is to go through all combinations with seven loops.

• The first loop goes through the 52 bits, setting one for the next loop.
• The second loop goes through the bits after the set one, setting one for the third loop.
• ...ect

This will give you the fastest iteration. Here is some pseudo C++ code:

__int64 deck;
int bit1, bit2, bit3, ...;
for (bit1=0;bit1<52-6;bit1++) {
  for (bit2=bit1+1;bit2<52-5;bit2++) {
    ...
      for (bit7=bit6+1;bit7<52;bit7++) {
        deck = (1<<bit1)+(1<<bit2)+(1<<bit3)+...;  // this could be optimized.
        // do whatever with deck
      }
    ...
  }
}

// note: the 52-6, 52-5, will be pre-calculated by the compiler and are there for convenience. You don't have to worry about optimizing this.

There is your solution right there. If you want to check that it works, I always downscale it. For example, following that algorithm on a 4bit number where you need to set 2 bits would go like this:

1100
1010
1001
0110
0101
0011

Answer 2

I think you'll be interested in this article: http://realtimecollisiondetection.net/blog/?p=78

It solves your problem in very efficient way.

Answer 3

I think there is a relationship between each permutation.

We can see the number increases with permutation # with a pattern.

This maths isn't correct for all solutions, but works for some, hopefully indicating what I mean:

Permutation 3 difference = ((3%7+1)^2) * (roundUp(3/7) = 16
Permutation 10 difference = ((10%7+1)^2) * (roundUp(10/7) = 32

So we would loop from the absolute values:

int perm = 1;
for int64 i = 127; perm < totalPermutations
{
    i = i + ((perm%7+1)^2) * (roundUp(perm/7);
    perm++;
}

Again the maths is wrong, but gives an idea, I am sure it is possible to come up with a formula for this. As to whether it outperforms bitwise operations would have to be tested.