位操作 – N用位掩码选择K位置换

我试图找到/创建一个小的twiddling算法,该算法在N位计数位掩码中生成1的所有K位计数排列,其中K <1. N.排列数是(N选择K)= N!/(K!(N-K)!).
These two algorithms, from Bit Twiddling Hacks,很接近.

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)
...

最佳答案 一种选择是在Intel Haswell中使用诸如PEXT之类的CPU指令,并将其更新,以便将您提到的位错误解决方案的结果扩展到掩码.如果您没有这样的指令,您可能需要一个循环.我在
this answer中给出了两种可能性.

点赞