はじめに
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
そのような命令がない場合
、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);