Developers Club geek daily blog

1 year, 10 months ago

Introduction


Let's allow we have some set which consists of N elements. Let's consider that elements are numbered from zero to N-1. The set of k-element subsets of this set (combinations) can be presented or in the form of an array of indexes of length of k. Or in the form of sequence from N bits in which k from them is set exactly. At Donald Cnut in its TAoCP the algorithm of generation of combinations is given in dictionary order when combinations are set in the form of an array of indexes. We will try to transfer this algorithm to a case of bit masks.

Algorithm


The algorithm of generation of the following lexicographic combination is rather simple and consists of two steps. On the first step we should find such smallest index m of an element following which an element does not enter a combination. Or that too most which we can increase per unit of. It is an element we replace with following. On the second step all elements of which it is less our selected m-go of an element to replace with the smallest of possible. For example, and we are a combination {8, 5, 4, 3, 2}. The smallest element which can be increased per unit of is 5. We replace it with the six: {8, 6, 4, 3, 2}. Now we delete three elements which less than six: {8, 6}. Also we add the smallest three elements. It is received {8, 6, 2, 1, 0} — the following combination in dictionary order.

Now we will translate this algorithm into language of bits. The first step is a search of such lowest bit, directly at the left before which zero is located. The second step — to exchange the received unit and zero in places. Third step: we shift all bits which are younger than found to a zero position. Let's review our example? 100111100 → 100111100 101011100 →101011100 →101000111 → 101000111.

Bit trick x &-x


I love different bit tricks. But many programmers are familiar with them rather poorly, and they drive them in a stupor. For example, not all know that expression x &-x will turn all bits of number into zero, except for the youngest set unit. How it works?

By determination, - x = ~ (x-1). The elementary illustration:-1 = ~ (1-1) = ~ 0. It is admissible now that the number x has nnnn1000 appearance where n — bits which can be set both in zero, and in unit. Our purpose consists in showing that (nnnn1000 &-nnnn1000) = 00001000. We receive such chain: nnnn1000 &-nnnn1000 = nnnn1000 &~ (nnnn1000 — 1) = nnnn1000 &~(nnnn0111) = nnnn1000 &сссс1000 = 00001000, where ñ — the corresponding inverted n bit.

Receipt of a bit mask of the following lexicographic combination


Now we will illustrate as the thought has to work to receive bit expression for the following lexicographic combination. If to add number in which only one low bit is left then as a result of transfer to our number the lowest bit which faces zero, will move to the place of this zero. All other low bits will be nullified:

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

As a result, if x = 100111100, then a = 000000100, and b = 101000000. Half-affairs it is made. It was necessary only to select low bits and to transfer them to the right. To set not used bits in zero, the operation AND is most often used. Taking into account a trick x&-x, the option arises at once:

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

As a result of which we will receive sequence of bits which can be shifted to the right. The truth number of bits will be one more than the necessary quantity that it is easy to correct moving on one bit to the right.

However, for zeroing of coinciding bits it is possible to use also the operation XOR. Let's try also it:

    int c = x ^ b;

Generally at us x it is possible to provide as x = nn... n011... 100..., at this b = nn. n100... 000.... Then operation x ^ will kill with b nnn matching in the beginning, having left only 00... 0111... 100.... For our example c = 001111100. Unlike the previous case, this sequence of bits is two longer, than it is required. The option with XOR demands the smaller number of operations. Let's leave it:

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

Now the sequence of bits which is kept in with should be shifted to the lowest bit to the right, and on two "excess" discharges. It is possible to make it "in a forehead":

    c /= a;
    c <<= 2;

Division operation is rather expensive and if the processor supports receipt of an index of low bit, then it will be possible to use it quicker. For example, for GCC case the corresponding embedded function is called __ builtin_ctz, as a result we will receive:

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

If there is no such instruction, then it is possible to consider option of receipt of an index through de Brioyn's sequence, then our code will look approximately so:

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

As a result division and shift was replaced with multiplication, two shifts and taking of value from the table.

Summing up


So, as a result we received 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 from six elementary operations with integral numbers, and one division. Without cycles and conditions. Which has to be executed quickly enough. How it can be used in the ready project? For example, we want to list all possible combinations of hands which can be received to Omaha. Them will be C (52,4) = 270725. It is possible to make it 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);

This article is a translation of the original post at habrahabr.ru/post/272707/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus