Introduction

Suppose we have some set that consists of N elements. We assume that the elements are numbered from zero to N-1 . A set of k -element subsets of a given set (combinations) can be represented either as an array of indices of length k . Or in the form of a sequence of N bits in which exactly k of them are set. In Donald Knuth, his TAoCP provides an algorithm for generating combinations in a lexicographical order, when the combinations are specified as an array of indices. We will try to transfer this algorithm in case of bit masks.

Algorithm

The algorithm for generating the following lexicographic combination is quite simple and consists of two steps. In the first step, we need to find the smallest index m of the element, the element after which the element is not included in the combination. Or, which is the same thing that we can increase by one. This item is replaced by the following. In the second step, all elements that are smaller than our selected m -th element should be replaced with the smallest possible one. For example, and we have a combination {8, 5, 4, 3, 2} . The smallest element that can be incremented by one is 5 . We replace it with a six: {8, 6, 4, 3, 2} . Now remove the three elements that are less than six: {8, 6} . And add the smallest three elements. Received {8, 6, 2, 1, 0} - the following combination in lexicographical order.

Now we translate this algorithm into the language of bits. The first step is to search for the lowest bit, immediately to the left of which is a zero. The second step is to exchange the received unit and zero places. The third step: all the bits that are younger than that found, we shift to the zero position. Consider our example? 100111100 → 10 0 1 11100 → 10 1 0 11100 → 1010 111 00 → 1010 00 111 → 101000111.

Bit trick x & -x

I love different bit tricks. But many programmers are familiar with them rather weakly, and they drive them into a stupor. For example, not everyone knows that the expression x & -x will turn all bits of a number to zero, with the exception of the youngest unit set. How does he work?
')
By definition, -x = ~ (x-1) . The simplest illustration: -1 = ~ (1-1) = ~ 0 . Suppose now that the number x has the form nnnn1000 , where n are bits that can be set to both zero and one. Our goal is to show that (nnnn1000 & -nnnn1000) = 00001000 . We get the following chain: nnnn1000 & -nnnn1000 = nnnn1000 & ~ (nnnn1000 - 1) = nnnn1000 & ~ (nnnn0111) = nnnn1000 & ññññ1000 = 00001000 , where ñ is the corresponding inverted bit n .

Getting the bitmask of the next lexicographic combination

Now we illustrate how thought should work in order to get a bit expression for the next lexicographic combination. If we add a number to our number, in which only one low bit is left, then as a result of the transfer, the least significant bit before which stands for zero will move to the place of this zero. All other low bits will be reset to zero:

int a = x & -x; int b = x + a; 

As a result, if x = 100111100 , then a = 000000100 , and b = 101000000 . Half done. It remains only to select the low bits and move them to the right. In order to set unused bits to zero, the AND operation is most often used. Taking into account the trick x & -x, the option immediately suggests itself:

  int c = b & -b; // 001000000 int c = c - 1; // 000111111 int d = c & x; // 000111100 

As a result, we get a sequence of bits that can be shifted to the right. True, the number of bits will be one more than the required number, which is easy to correct by moving another bit to the right.

However, you can also use the XOR operation to zero off the matching bits. Let's try it too:

  int c = x ^ b; 

In the general case, for us x can be represented as x = nn ... n011 ... 100 ... , with b = nn..n100 ... 000 .... Then the operation x ^ b will kill the nnn coinciding at the beginning, leaving only 00 ... 0111 ... 100 .... For our example, c = 001111100 . Unlike the previous case, this sequence of bits is two times longer than required. Option c XOR requires fewer operations. Leave it:

  int a = x & -x; int b = x + a; int c = x ^ b; 

Now the sequence of bits, which is stored in s , must be shifted to the right to the lowest bit, and another two "extra" bits. You can do this "in the forehead":

  c /= a; c <<= 2; 

The division operation is quite expensive, and if the processor supports getting the index of the low-order bit, then it will be possible to use it as quickly as possible. For example, for the case of GCC, the corresponding built-in function is called __builtin_ctz , as a result we get:

  int d = __builtin_ctz(x) + 2; c <<= d; 

If there is no such instruction, then we can consider the option of obtaining the index through the de Bruin sequence , then our code will look something like this:

  int d = magic_table[(magic_factor * a) >> magic_shift]; c <<= d; 

As a result, division and shift were replaced by multiplication, two shifts and taking values ​​from the table.

Summarizing

So, as a result, we got the following code:

 static inline uint64_t next_combination_mask(uint64_t x) { uint64_t a = x & -x; uint64_t b = x + a; uint64_t c = b ^ x; a <<= 2; c /= a; return b | c; } 

consisting of six elementary operations with integers, and one division. Without cycles and conditions. Which should be performed fairly quickly. How can it be used in the finished project? For example, we want to list all the possible combinations of hands that can be obtained in Omaha. They will be C (52.4) = 270725. This can be done in the following cycle:

  uint64_t current = 0x0F; //   ; uint64_t last = 1 << 52; // 52-          52 ,    53- do { process_mask(current); // - ... current = next_combination_mask(current); //     } while (current < last);