N mit bitmask

Question

ich zu finden bin versucht,/erstellen ein wenig twiddling Algorithmus, erzeugt alle K-Bit-count Permutationen der 1 s in einem N -Bit-count Bitmaske, wobei K < N K Bitpermutation wählen. Die Anzahl der Permutationen ist (N choose K) = N!/(K!(N-K)!).

These two algorithms, from Bit Twiddling Hacks, sind in der Nähe.

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

Ähnlich.

Diese Algorithmen erzeugen Permutationen in lexikographischer Ordnung, die ich nicht unbedingt benötige. Allerdings brauche ich einen Algorithmus, der eine Bitmaske m enthält.

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

Eine Möglichkeit ist es, eine CPU-Anweisung wie PEXT in Intel Haswell und neuer verwenden, um das Ergebnis aus der Bit twiddling Lösung, die Sie auf die Maske erwähnen zu erweitern. Wenn Sie keine solche Anweisung zur Verfügung haben, benötigen Sie wahrscheinlich eine Schleife. Ich gebe zwei Möglichkeiten in this answer.