はじめに

N個の要素で構成されるセットがあるとします。 要素には0からN-1までの番号が付けられていると仮定します。 所定のセット（組み合わせ）のk要素サブセットのセットは、長さkのインデックスの配列として表すことができます。 または、それらの正確にkが設定されるNビットのシーケンスの形式で。 TAoCPの Donald Knuthは、組み合わせがインデックスの配列として指定されている場合に、辞書編集順に組み合わせを生成するアルゴリズムを提供しています。 このアルゴリズムをビットマスクの場合に転送しようとします。

アルゴリズム

次の辞書式組み合わせを生成するアルゴリズムは非常に単純で、2つのステップで構成されています。 最初のステップでは、要素の最小のインデックスmを見つける必要があります。次のインデックスmの後、要素は組み合わせに含まれません。 または、これは1つずつ増やすことができるのと同じことです。 この要素を次のものに置き換えます。 2番目のステップでは、選択したm番目の要素よりも小さいすべての要素を可能な限り小さいものに置き換えます。 たとえば、 {8、5、4、3、2}の組み合わせがあります。 1ずつ増やすことができる最小の要素は5です。 6に置き換えます： {8、6、4、3、2} 。 次に、6未満の3つの要素{8、6}を削除します。 そして、少なくとも3つの要素を追加します。 受け取った{ 8、6、2、1、0 } -辞書式順序での次の組み合わせ。



次に、このアルゴリズムをビットの言語に翻訳します。 最初のステップは、ゼロが配置される直前に、そのような最下位ビットを検索することです。 2番目のステップは、受信したユニットとゼロ位を交換することです。 3番目のステップ：検出されたビットよりも若いすべてのビットがゼロ位置にシフトされます。 私たちの例を考えますか？ 100111100→10 0 1 11100→10 1 0 11100→1010 111 00 →1010 00 111 →101000111

X＆-xビットトリック

ちょっとしたトリックが大好きです。 しかし、多くのプログラマーはそれらにあまり精通しておらず、彼らをst迷に追い込みます。 たとえば、式x＆-xが最小単位セットを除き、数値のすべてのビットをゼロに設定することを誰もが知っているわけではありません。 彼はどのように働いていますか？



定義により、 -x =〜（x-1） 。 最も簡単な図： -1 =〜（1-1）=〜0 。 ここで、数値xの形式がnnnn1000であるとします。ここで、 nは0または1に設定できるビットです。 私たちの目標は、 （nnnn1000＆-nnnn1000）= 00001000を示すことです。 次のチェーンを取得します： nnnn1000＆-nnnn1000 = nnnn1000＆〜（nnnn1000-1）= nnnn1000＆〜（nnnn0111）= nnnn1000＆ñññññ10001000= 00001000 、ここでñは対応する反転ビットnです。

次の辞書式組み合わせのビットマスクを取得する

次に、次の辞書式組み合わせのビット式を取得するために、思考がどのように機能するかを示します。 最下位ビットが1つだけ残っている数値を数値に追加すると、転送の結果、その前の最下位ビットがゼロになり、このゼロの位置に移動します。 他のすべての下位ビットはゼロにリセットされます。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

その結果、 x = 100111100の場合、 a = 000000100 、およびb = 101000000です。 仕事の半分が完了しました。 最下位ビットを選択して右に移動するだけです。 未使用ビットをゼロに設定するには、AND演算が最もよく使用されます。 トリックxと-xを考えると、オプションはすぐに頼みます：

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

その結果、右にシフトできるビットのシーケンスを取得します。 確かに、ビット数は必要な数よりも1つ多くなります。これは、もう1ビット右にシフトすることで簡単に修正できます。



ただし、一致するビットをリセットするには、XOR演算を使用することもできます。 それも試してみましょう：

  int c = x ^ b;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一般的な場合、 xはx = nn ... n011 ... 100 ...として表すことができ、 b = nn..n100 ... 000 .... 次に、操作x ^ bは、最初に一致したnnnを強制終了し 、 00 ... 0111 ... 100 ...のみを残します。 この例では、 c = 001111100です。 前の場合とは異なり、このビットシーケンスは必要な長さよりも2倍長くなります。 バリアントc XORでは、必要な操作が少なくなります。 そのままにしましょう：

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

sに格納されているビットシーケンスは、最下位ビットとさらに2つの「余分な」ビットの右にシフトする必要があります。 この「額」を実行できます。

  c /= a; c <<= 2;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

除算操作は非常に高価であり、プロセッサが低ビットインデックスの取得をサポートしている場合、おそらくそれを使用する方が高速です。 たとえば、GCCの場合、対応する組み込み関数は__builtin_ctzと呼ばれ、結果として次のようになります。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そのような命令がない場合、de Bruyneシーケンスを介してインデックスを取得するオプションを検討できます。その場合、コードは次のようになります。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

その結果、除算とシフトは乗算、2つのシフト、およびテーブルからの値の取得に置き換えられました。

まとめ

その結果、次のコードが得られました。

 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; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

整数を含む6つの基本演算と1つの除算で構成されます。 サイクルと条件はありません。 これは十分に高速に実行されるはずです。 完成したプロジェクトでどのように使用できますか？ たとえば、オマハで取得できるすべての手の組み合わせを一覧表示します。 C（52,4）= 270725です。これは、次のサイクルで実行できます。

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