Bit hack para generar todos los enteros con un número dado de 1s

Olvidé un poco de hack para generar todos los enteros con un número dado de 1s. ¿Alguien lo recuerda (y probablemente también puede explicarlo)?

De Bit Twiddling Hacks

Actualizar el progtwig de prueba Live On Coliru

#include  #include  #include  using I = uint8_t; auto dump(I v) { return std::bitset(v); } I bit_twiddle_permute(I v) { I 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. I w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1)); return w; } int main() { I p = 0b001001; std::cout << dump(p) << "\n"; for (I n = bit_twiddle_permute(p); n>p; p = n, n = bit_twiddle_permute(p)) { std::cout << dump(n) << "\n"; } } 

Huellas dactilares

 00001001 00001010 00001100 00010001 00010010 00010100 00011000 00100001 00100010 00100100 00101000 00110000 01000001 01000010 01000100 01001000 01010000 01100000 10000001 10000010 10000100 10001000 10010000 10100000 11000000 

Calcule lexicográficamente la siguiente permutación de bit

Supongamos que tenemos un patrón de N bits establecido en 1 en un entero y queremos la siguiente permutación de N 1 bits en un sentido lexicográfico. Por ejemplo, si N es 3 y el patrón de bits es 00010011, los siguientes patrones serían 00010101, 00010110, 00011001,00011010, 00011100, 00100011, y así sucesivamente. La siguiente es una forma rápida de calcular la siguiente permutación.

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

El __builtin_ctz(v) GNU C intrínseco para CPU x86 devuelve el número de ceros finales. Si está utilizando comstackdores de Microsoft para x86, el intrínseco es _BitScanForward . Ambos emiten una instrucción bsf, pero los equivalentes pueden estar disponibles para otras architectures. De lo contrario, considere usar uno de los métodos para contar los bits cero consecutivos mencionados anteriormente.

Aquí hay otra versión que tiende a ser más lenta debido a su operador de división, pero no requiere contar los ceros finales.

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

Gracias a Dario Sneidermanis de Argentina, quien brindó esto el 28 de noviembre de 2009.

Para hacks de bits, me gustaría referirme a esta página: Bit Twiddling Hacks .

Con respecto a su pregunta específica, lea la parte titulada Calcular la siguiente permutación de lexicografía .


Calcule lexicográficamente la siguiente permutación de bit

Supongamos que tenemos un patrón de N bits establecido en 1 en un entero y queremos la siguiente permutación de N 1 bits en un sentido lexicográfico. Por ejemplo, si N es 3 y el patrón de bits es 00010011, los siguientes patrones serían 00010101, 00010110, 00011001,00011010, 00011100, 00100011, y así sucesivamente. La siguiente es una forma rápida de calcular la siguiente permutación.

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

El comstackdor __builtin_ctz (v) GNU C intrínseco para CPU x86 devuelve el número de ceros finales. Si está utilizando comstackdores de Microsoft para x86, el intrínseco es _BitScanForward. Ambos emiten una instrucción bsf, pero los equivalentes pueden estar disponibles para otras architectures. De lo contrario, considere usar uno de los métodos para contar los bits cero consecutivos mencionados anteriormente. Aquí hay otra versión que tiende a ser más lenta debido a su operador de división, pero no requiere contar los ceros finales.

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

Gracias a Dario Sneidermanis de Argentina, quien brindó esto el 28 de noviembre de 2009.

Para agregar a la respuesta de @ sehe incluida a continuación (originalmente de Dario Sneidermanis también en http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation ).

 #include  #include  #include  using I = uint8_t; auto dump(I v) { return std::bitset(v); } I bit_twiddle_permute(I v) { I 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. I w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1)); return w; } int main() { I p = 0b001001; std::cout << dump(p) << "\n"; for (I n = bit_twiddle_permute(p); n>p; p = n, n = bit_twiddle_permute(p)) { std::cout << dump(n) << "\n"; } } 

Hay problemas de límites con bit_twiddle_permute (I v). Siempre que v sea la última permutación, t es todo 1 (p. Ej. 2 ^ 8 - 1), (~t & -~t) = 0 , y w es la primera permutación de bits con 1 menos 1 que v, excepto cuando v = 000000000 en cuyo caso w = 01111111 . En particular, si configura p en 0; el loop en main producirá todas las permutaciones con siete 1's, y la siguiente ligera modificación del ciclo for, recorrerá todas las permutaciones con 0, 7, 6, ..., 1 bit set -

 for (I n = bit_twiddle_permute(p); n>p; n = bit_twiddle_permute(n)) 

Si esta es la intención, tal vez valga un comentario. Si no es trivial para arreglar, por ejemplo

 if (t == (I)(-1)) { return v >> __builtin_ctz(v); } 

Entonces, con una pequeña simplificación adicional

 I bit_twiddle_permute2(I v) { I t = (v | (v - 1)) + 1; if (t == 0) { return v >> __builtin_ctz(v); } I w = t | ((~t & v) >> (__builtin_ctz(v) + 1)); return w; } int main() { I p = 0b1; cout << dump(p) << "\n"; for (I n = bit_twiddle_permute2(p); n>p; n = bit_twiddle_permute2(n)) { cout << dump(n) << "\n"; } } 

La siguiente adaptación de la idea de Darío Sneidermanis puede ser un poco más fácil de seguir

 I bit_twiddle_permute3(I v) { int n = __builtin_ctz(v); I s = v >> n; I t = s + 1; I w = (t << n) | ((~t & s) >> 1); return w; } 

o con una solución similar al problema que mencioné al comienzo de esta publicación

 I bit_twiddle_permute3(I v) { int n = __builtin_ctz(v); I s = v >> n; I t = s + 1; if (v == 0 || t << n == 0) { return s; } I w = (t << n) | ((~t & s) >> 1); return w; }