長さnのkビットセットのバイナリ文字列をすべて生成する 質問する

このメソッドは、正確に N 個の '1' ビットを持つすべての整数を生成します。

からhttps://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

辞書順で次のビット順列を計算する

整数に N ビットが 1 に設定されたパターンがあり、辞書式の意味での N 1 ビットの次の順列が必要であるとします。たとえば、N が 3 でビット パターンが の場合、次のパターンは、、、、、 、 など00010011になります。次の順列を計算する高速な方法を次に示します。000101010001011000011001000110100001110000100011

unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1
// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

x86 CPU 用のGNU __builtin_ctz(v)C コンパイラ組み込み関数は、末尾のゼロの数を返します。x86 用の Microsoft コンパイラを使用している場合、組み込み関数は です_BitScanForward。これらは両方ともbsf命令を発行しますが、他のアーキテクチャでも同等のものが利用できる場合があります。そうでない場合は、前述の連続するゼロ ビットをカウントする方法の 1 つを使用することを検討してください。除算演算子があるために遅くなる傾向がありますが、末尾のゼロをカウントする必要のない別のバージョンを次に示します。

unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

2009 年 11 月 28 日にこれを提供してくれたアルゼンチンの Dario Sneidermanis 氏に感謝します。