用位掩码选择K位置换

Question

我试图找到/创建一个位旋转算法，该算法在n-bit-count位掩码中生成1s的所有k 位掩码中的 k-bit-count排列。排列数为 (N choose K)=N！/（K！（N-K）！）。

这两个算法，从比特旋转黑客，是接近的。

unsigned int v; // current permutation of bits where bitCount(v) == K
unsigned int w; // next permutation where bitCount(w) == bitCount(v)

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

unsigned int v; // current permutation of bits where bitCount(v) == K
unsigned int w; // next permutation where bitCount(w) == bitCount(v)

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

这些算法以词典顺序生成排列，我不一定需要。但是，我确实需要一个包含位掩码M的算法。

unsigned int m; // bitmask from which next permutation is chosen
                // where bitCount(m) == N
unsigned int v; // current permutation of bits where (v & m) == v
                // and bitCount(v) == K
unsigned int w; // next permutation of bits where (w & m) == w
                // and bitCount(w) == bitCount(v)
...




Answer 1

一种选择是使用CPU指令，如Intel Haswell和更新版本中的PEXT，将结果从您提到的位旋转解决方案扩展到掩码。如果您没有这样的指令可用，您可能需要一个循环。我在这个答案中给出了两种可能性。