Algoritmo más eficiente para la inversión de bits (de MSB-> LSB a LSB-> MSB) en C

¿Cuál es el mejor algoritmo para lograr lo siguiente?

0010 0000 => 0000 0100

La conversión es de MSB-> LSB a LSB-> MSB. Todos los bits deben invertirse; es decir, esto no es intercambio de endianness.

NOTA : Todos los algoritmos que figuran a continuación están en C, pero deberían ser portátiles para el idioma de su elección (simplemente no me mires cuando no son tan rápidos 🙂

Opciones

Memoria baja (32 bits int , máquina de 32 bits) (desde aquí ):

 unsigned int reverse(register unsigned int x) { x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); } 

De la famosa página de Bit Twiddling Hacks :

Más rápido (tabla de búsqueda) :

 static const unsigned char BitReverseTable256[] = { 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA, 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF }; unsigned int v; // reverse 32-bit value, 8 bits at time unsigned int c; // c will get v reversed // Option 1: c = (BitReverseTable256[v & 0xff] << 24) | (BitReverseTable256[(v >> 8) & 0xff] << 16) | (BitReverseTable256[(v >> 16) & 0xff] << 8) | (BitReverseTable256[(v >> 24) & 0xff]); // Option 2: unsigned char * p = (unsigned char *) &v; unsigned char * q = (unsigned char *) &c; q[3] = BitReverseTable256[p[0]]; q[2] = BitReverseTable256[p[1]]; q[1] = BitReverseTable256[p[2]]; q[0] = BitReverseTable256[p[3]]; 

Puede extender esta idea a int 64 bits, o cambiar la velocidad de la memoria (suponiendo que su caché de datos L1 es lo suficientemente grande), y revertir 16 bits a la vez con una tabla de búsqueda de entrada de 64 K.


Otros

Sencillo

 unsigned int v; // input bits to be reversed unsigned int r = v & 1; // r will be reversed bits of v; first get LSB of v int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end for (v >>= 1; v; v >>= 1) { r <<= 1; r |= v & 1; s--; } r <<= s; // shift when v's highest bits are zero 

Más rápido (procesador de 32 bits)

 unsigned char b = x; b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16; 

Más rápido (procesador de 64 bits)

 unsigned char b; // reverse this (8-bit) byte b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023; 

Si desea hacer esto en un int 32 bits, simplemente invierta los bits en cada byte y revertir el orden de los bytes. Es decir:

 unsigned int toReverse; unsigned int reversed; unsigned char inByte0 = (toReverse & 0xFF); unsigned char inByte1 = (toReverse & 0xFF00) >> 8; unsigned char inByte2 = (toReverse & 0xFF0000) >> 16; unsigned char inByte3 = (toReverse & 0xFF000000) >> 24; reversed = (reverseBits(inByte0) << 24) | (reverseBits(inByte1) << 16) | (reverseBits(inByte2) << 8) | (reverseBits(inByte3); 

Resultados

Hice una evaluación comparativa de las dos soluciones más prometedoras, la tabla de búsqueda, y bitwise-AND (la primera). La máquina de prueba es una computadora portátil con 4 GB de DDR2-800 y Core 2 Duo T7500 a 2,4 GHz, 4 MB de caché L2; YMMV. Usé gcc 4.3.2 en Linux de 64 bits. OpenMP (y los enlaces GCC) se usaron para temporizadores de alta resolución.

reverse.c

 #include  #include  #include  unsigned int reverse(register unsigned int x) { x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); } int main() { unsigned int *ints = malloc(100000000*sizeof(unsigned int)); unsigned int *ints2 = malloc(100000000*sizeof(unsigned int)); for(unsigned int i = 0; i < 100000000; i++) ints[i] = rand(); unsigned int *inptr = ints; unsigned int *outptr = ints2; unsigned int *endptr = ints + 100000000; // Starting the time measurement double start = omp_get_wtime(); // Computations to be measured while(inptr != endptr) { (*outptr) = reverse(*inptr); inptr++; outptr++; } // Measuring the elapsed time double end = omp_get_wtime(); // Time calculation (in seconds) printf("Time: %f seconds\n", end-start); free(ints); free(ints2); return 0; } 

reverse_lookup.c

 #include  #include  #include  static const unsigned char BitReverseTable256[] = { 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA, 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF }; int main() { unsigned int *ints = malloc(100000000*sizeof(unsigned int)); unsigned int *ints2 = malloc(100000000*sizeof(unsigned int)); for(unsigned int i = 0; i < 100000000; i++) ints[i] = rand(); unsigned int *inptr = ints; unsigned int *outptr = ints2; unsigned int *endptr = ints + 100000000; // Starting the time measurement double start = omp_get_wtime(); // Computations to be measured while(inptr != endptr) { unsigned int in = *inptr; // Option 1: //*outptr = (BitReverseTable256[in & 0xff] << 24) | // (BitReverseTable256[(in >> 8) & 0xff] << 16) | // (BitReverseTable256[(in >> 16) & 0xff] << 8) | // (BitReverseTable256[(in >> 24) & 0xff]); // Option 2: unsigned char * p = (unsigned char *) &(*inptr); unsigned char * q = (unsigned char *) &(*outptr); q[3] = BitReverseTable256[p[0]]; q[2] = BitReverseTable256[p[1]]; q[1] = BitReverseTable256[p[2]]; q[0] = BitReverseTable256[p[3]]; inptr++; outptr++; } // Measuring the elapsed time double end = omp_get_wtime(); // Time calculation (in seconds) printf("Time: %f seconds\n", end-start); free(ints); free(ints2); return 0; } 

Probé ambos enfoques en varias optimizaciones diferentes, ejecuté 3 ensayos en cada nivel, y cada ensayo invirtió 100 millones de entradas sin firmar al azar. Para la opción de tabla de búsqueda, probé ambos esquemas (opciones 1 y 2) en la página de hacks bit a bit. Los resultados se muestran a continuación.

Bitwise Y

 mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -o reverse reverse.c mrj10@mjlap:~/code$ ./reverse Time: 2.000593 seconds mrj10@mjlap:~/code$ ./reverse Time: 1.938893 seconds mrj10@mjlap:~/code$ ./reverse Time: 1.936365 seconds mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O2 -o reverse reverse.c mrj10@mjlap:~/code$ ./reverse Time: 0.942709 seconds mrj10@mjlap:~/code$ ./reverse Time: 0.991104 seconds mrj10@mjlap:~/code$ ./reverse Time: 0.947203 seconds mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O3 -o reverse reverse.c mrj10@mjlap:~/code$ ./reverse Time: 0.922639 seconds mrj10@mjlap:~/code$ ./reverse Time: 0.892372 seconds mrj10@mjlap:~/code$ ./reverse Time: 0.891688 seconds 

Tabla de búsqueda (opción 1)

 mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -o reverse_lookup reverse_lookup.c mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.201127 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.196129 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.235972 seconds mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O2 -o reverse_lookup reverse_lookup.c mrj10@mjlap:~/code$ ./reverse_lookup Time: 0.633042 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 0.655880 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 0.633390 seconds mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O3 -o reverse_lookup reverse_lookup.c mrj10@mjlap:~/code$ ./reverse_lookup Time: 0.652322 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 0.631739 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 0.652431 seconds 

Tabla de búsqueda (opción 2)

 mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -o reverse_lookup reverse_lookup.c mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.671537 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.688173 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.664662 seconds mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O2 -o reverse_lookup reverse_lookup.c mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.049851 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.048403 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.085086 seconds mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O3 -o reverse_lookup reverse_lookup.c mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.082223 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.053431 seconds mrj10@mjlap:~/code$ ./reverse_lookup Time: 1.081224 seconds 

Conclusión

Use la tabla de búsqueda, con la opción 1 (el direccionamiento de bytes es sorprendentemente lento) si le preocupa el rendimiento. Si necesita extraer hasta el último byte de memoria de su sistema (y puede que, si le preocupa el rendimiento de la inversión de bit), las versiones optimizadas del enfoque Y a nivel de bits tampoco son muy malas.

Advertencia

Sí, sé que el código de referencia es un truco completo. Las sugerencias sobre cómo mejorarlo son más que bienvenidas. Cosas que conozco:

  • No tengo acceso a ICC. Esto puede ser más rápido (responda en un comentario si puede probar esto).
  • Una tabla de búsqueda de 64K puede funcionar bien en algunas microarchitectures modernas con L1D grande.
  • -mtune = native no funcionó para -O2 / -O3 ( ld explotó con algún error de redefinición de símbolos loco), así que no creo que el código generado esté sintonizado para mi microarchitecture.
  • Puede haber una forma de hacerlo un poco más rápido con SSE. No tengo idea de cómo, pero con la rápida replicación, el paquete de bitácora Y, y las rápidas instrucciones, debe haber algo allí.
  • Sé que solo el ensamblaje x86 es peligroso; aquí está el código GCC generado en -O3 para la opción 1, para que alguien más conocedor que yo pueda verificarlo:

32 bits

 .L3: movl (%r12,%rsi), %ecx movzbl %cl, %eax movzbl BitReverseTable256(%rax), %edx movl %ecx, %eax shrl $24, %eax mov %eax, %eax movzbl BitReverseTable256(%rax), %eax sall $24, %edx orl %eax, %edx movzbl %ch, %eax shrl $16, %ecx movzbl BitReverseTable256(%rax), %eax movzbl %cl, %ecx sall $16, %eax orl %eax, %edx movzbl BitReverseTable256(%rcx), %eax sall $8, %eax orl %eax, %edx movl %edx, (%r13,%rsi) addq $4, %rsi cmpq $400000000, %rsi jne .L3 

EDITAR: También intenté usar uint64_t en mi máquina para ver si había algún aumento de rendimiento. El rendimiento era aproximadamente un 10% más rápido que 32 bits, y era casi idéntico si solo usaba tipos de 64 bits para revertir bits en dos entradas de 32 bits a la vez, o si realmente estaba invirtiendo bits a la mitad como tantos 64- valores de bit. El código de ensamblado se muestra a continuación (para el primer caso, invertir bits para 2 entradas de 32 bits a la vez):

 .L3: movq (%r12,%rsi), %rdx movq %rdx, %rax shrq $24, %rax andl $255, %eax movzbl BitReverseTable256(%rax), %ecx movzbq %dl,%rax movzbl BitReverseTable256(%rax), %eax salq $24, %rax orq %rax, %rcx movq %rdx, %rax shrq $56, %rax movzbl BitReverseTable256(%rax), %eax salq $32, %rax orq %rax, %rcx movzbl %dh, %eax shrq $16, %rdx movzbl BitReverseTable256(%rax), %eax salq $16, %rax orq %rax, %rcx movzbq %dl,%rax shrq $16, %rdx movzbl BitReverseTable256(%rax), %eax salq $8, %rax orq %rax, %rcx movzbq %dl,%rax shrq $8, %rdx movzbl BitReverseTable256(%rax), %eax salq $56, %rax orq %rax, %rcx movzbq %dl,%rax shrq $8, %rdx movzbl BitReverseTable256(%rax), %eax andl $255, %edx salq $48, %rax orq %rax, %rcx movzbl BitReverseTable256(%rdx), %eax salq $40, %rax orq %rax, %rcx movq %rcx, (%r13,%rsi) addq $8, %rsi cmpq $400000000, %rsi jne .L3 

Este hilo llamó mi atención ya que se trata de un problema simple que requiere mucho trabajo (ciclos de CPU) incluso para una CPU moderna. Y un día también me quedé allí con el mismo problema ¤ #% “#”. Tuve que voltear millones de bytes. Sin embargo, sé que todos mis sistemas de destino son modernos basados ​​en Intel, así que ¡comencemos a optimizar al máximo!

Así que utilicé el código de búsqueda de Matt J como base. el sistema en el que estoy evaluando es un i7 haswell 4700eq.

La búsqueda de Matt J haciendo un movimiento de bits de 400 000 000 bytes: alrededor de 0,272 segundos.

Luego seguí adelante y traté de ver si el comstackdor de Intels ISPC podía vectorizar las aritméticas en reverse.c.

No voy a aburrirlo con mis hallazgos aquí, ya que intenté mucho para ayudar al comstackdor a encontrar cosas, de todos modos terminé con un rendimiento de alrededor de 0,15 segundos a una cifra de 400 000 000 bytes. es una gran reducción, pero para mi aplicación eso todavía es mucho más lento …

Así que la gente me permite presentar el bitflipper basado en Intel más rápido del mundo. Registrado en:

Es hora de hacer bitflip 400000000 bytes: 0.050082 segundos !!!!!

 // Bitflip using AVX2 - The fastest Intel based bitflip in the world!! // Made by Anders Cedronius 2014 (anders.cedronius (you know what) gmail.com) #include  #include  #include  #include  using namespace std; #define DISPLAY_HEIGHT 4 #define DISPLAY_WIDTH 32 #define NUM_DATA_BYTES 400000000 // Constants (first we got the mask, then the high order nibble look up table and last we got the low order nibble lookup table) __attribute__ ((aligned(32))) static unsigned char k1[32*3]={ 0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f, 0x00,0x08,0x04,0x0c,0x02,0x0a,0x06,0x0e,0x01,0x09,0x05,0x0d,0x03,0x0b,0x07,0x0f,0x00,0x08,0x04,0x0c,0x02,0x0a,0x06,0x0e,0x01,0x09,0x05,0x0d,0x03,0x0b,0x07,0x0f, 0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0,0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0 }; // The data to be bitflipped (+32 to avoid the quantization out of memory problem) __attribute__ ((aligned(32))) static unsigned char data[NUM_DATA_BYTES+32]={}; extern "C" { void bitflipbyte(unsigned char[],unsigned int,unsigned char[]); } int main() { for(unsigned int i = 0; i < NUM_DATA_BYTES; i++) { data[i] = rand(); } printf ("\r\nData in(start):\r\n"); for (unsigned int j = 0; j < 4; j++) { for (unsigned int i = 0; i < DISPLAY_WIDTH; i++) { printf ("0x%02x,",data[i+(j*DISPLAY_WIDTH)]); } printf ("\r\n"); } printf ("\r\nNumber of 32-byte chunks to convert: %d\r\n",(unsigned int)ceil(NUM_DATA_BYTES/32.0)); double start_time = omp_get_wtime(); bitflipbyte(data,(unsigned int)ceil(NUM_DATA_BYTES/32.0),k1); double end_time = omp_get_wtime(); printf ("\r\nData out:\r\n"); for (unsigned int j = 0; j < 4; j++) { for (unsigned int i = 0; i < DISPLAY_WIDTH; i++) { printf ("0x%02x,",data[i+(j*DISPLAY_WIDTH)]); } printf ("\r\n"); } printf("\r\n\r\nTime to bitflip %d bytes: %f seconds\r\n\r\n",NUM_DATA_BYTES, end_time-start_time); // return with no errors return 0; } 

El pritf es para la depuración ..

Aquí está el caballo de batalla:

 bits 64 global bitflipbyte bitflipbyte: vmovdqa ymm2, [rdx] add rdx, 20h vmovdqa ymm3, [rdx] add rdx, 20h vmovdqa ymm4, [rdx] bitflipp_loop: vmovdqa ymm0, [rdi] vpand ymm1, ymm2, ymm0 vpandn ymm0, ymm2, ymm0 vpsrld ymm0, ymm0, 4h vpshufb ymm1, ymm4, ymm1 vpshufb ymm0, ymm3, ymm0 vpor ymm0, ymm0, ymm1 vmovdqa [rdi], ymm0 add rdi, 20h dec rsi jnz bitflipp_loop ret 

El código toma 32 bytes y luego enmascara los nibbles. El mordisco alto se desplaza a la derecha por 4. luego uso vpshufb y ymm4 / ymm3 como tablas de búsqueda. Podría usar una sola tabla de búsqueda, pero luego tendría que cambiar a la izquierda antes de volver a unir los bocados juntos.

Hay formas incluso más rápidas de voltear los bits. Pero estoy obligado a un solo hilo y CPU, así que este fue el más rápido que pude lograr. ¿Puedes hacer una versión más rápida?

No haga ningún comentario sobre el uso de los comandos equivalentes intrínsecos del comstackdor Intel C / C ++ ...

Esta es otra solución para las personas que aman la recursividad.

La idea es simple Divida la entrada por la mitad e intercambie las dos mitades, continúe hasta que scope un solo bit.

 Illustrated in the example below. Ex : If Input is 00101010 ==> Expected output is 01010100 1. Divide the input into 2 halves 0010 --- 1010 2. Swap the 2 Halves 1010 0010 3. Repeat the same for each half. 10 -- 10 --- 00 -- 10 10 10 10 00 1-0 -- 1-0 --- 1-0 -- 0-0 0 1 0 1 0 1 0 0 Done! Output is 01010100 

Aquí hay una función recursiva para resolverlo. (Tenga en cuenta que he usado ints sin signo, por lo que puede funcionar para entradas de hasta sizeof (unsigned int) * 8 bits.

La función recursiva toma 2 parámetros: el valor cuyos bits deben invertirse y el número de bits en el valor.

 int reverse_bits_recursive(unsigned int num, unsigned int numBits) { unsigned int reversedNum;; unsigned int mask = 0; mask = (0x1 << (numBits/2)) - 1; if (numBits == 1) return num; reversedNum = reverse_bits_recursive(num >> numBits/2, numBits/2) | reverse_bits_recursive((num & mask), numBits/2) << numBits/2; return reversedNum; } int main() { unsigned int reversedNum; unsigned int num; num = 0x55; reversedNum = reverse_bits_recursive(num, 8); printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum); num = 0xabcd; reversedNum = reverse_bits_recursive(num, 16); printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum); num = 0x123456; reversedNum = reverse_bits_recursive(num, 24); printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum); num = 0x11223344; reversedNum = reverse_bits_recursive(num,32); printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum); } 

Este es el resultado:

 Bit Reversal Input = 0x55 Output = 0xaa Bit Reversal Input = 0xabcd Output = 0xb3d5 Bit Reversal Input = 0x123456 Output = 0x651690 Bit Reversal Input = 0x11223344 Output = 0x22cc4488 

La respuesta de Anders Cedronius proporciona una gran solución para las personas que tienen una CPU x86 con soporte AVX2. Para plataformas x86 sin soporte AVX o plataformas que no sean x86, cualquiera de las siguientes implementaciones debería funcionar bien.

El primer código es una variante del clásico método de partición binario, codificado para maximizar el uso del modismo shift-plus-logic útil en varios procesadores ARM. Además, usa la generación de máscara sobre la marcha que podría ser beneficiosa para los procesadores RISC que de otro modo requieren múltiples instrucciones para cargar cada valor de máscara de 32 bits. Los comstackdores para plataformas x86 deben usar la propagación constante para calcular todas las máscaras en tiempo de comstackción en lugar de tiempo de ejecución.

 /* Classic binary partitioning algorithm */ inline uint32_t brev_classic (uint32_t a) { uint32_t m; a = (a >> 16) | (a << 16); // swap halfwords m = 0x00ff00ff; a = ((a >> 8) & m) | ((a << 8) & ~m); // swap bytes m = m^(m << 4); a = ((a >> 4) & m) | ((a << 4) & ~m); // swap nibbles m = m^(m << 2); a = ((a >> 2) & m) | ((a << 2) & ~m); m = m^(m << 1); a = ((a >> 1) & m) | ((a << 1) & ~m); return a; } 

En el volumen 4A de "El arte de la progtwigción de computadoras", D. Knuth muestra formas ingeniosas de invertir bits que de manera algo sorprendente requieren menos operaciones que los algoritmos clásicos de partición binaria. Uno de estos algoritmos para operandos de 32 bits, que no puedo encontrar en TAOCP, se muestra en este documento en el sitio web de Hacker's Delight.

 /* Knuth's algorithm from http://www.hackersdelight.org/revisions.pdf. Retrieved 8/19/2015 */ inline uint32_t brev_knuth (uint32_t a) { uint32_t t; a = (a << 15) | (a >> 17); t = (a ^ (a >> 10)) & 0x003f801f; a = (t + (t << 10)) ^ a; t = (a ^ (a >> 4)) & 0x0e038421; a = (t + (t << 4)) ^ a; t = (a ^ (a >> 2)) & 0x22488842; a = (t + (t << 2)) ^ a; return a; } 

Usando el comstackdor C / C ++ del comstackdor de Intel 13.1.3.198, las dos funciones anteriores auto-vectorizan muy bien los registros XMM . También se pueden vectorizar manualmente sin mucho esfuerzo.

En mi IvyBridge Xeon E3 1270v2, con el código auto-vectorizado, se uin32_t 100 millones de uin32_t palabras en 0.070 segundos con brev_classic() y brev_knuth() segundos con brev_knuth() . Me aseguré de que mi punto de referencia no estuviera limitado por el ancho de banda de la memoria del sistema.

Bueno, esto ciertamente no será una respuesta como la de Matt J, pero espero que aún sea útil.

 size_t reverse(size_t n, unsigned int bytes) { __asm__("BSWAP %0" : "=r"(n) : "0"(n)); n >>= ((sizeof(size_t) - bytes) * 8); n = ((n & 0xaaaaaaaaaaaaaaaa) >> 1) | ((n & 0x5555555555555555) << 1); n = ((n & 0xcccccccccccccccc) >> 2) | ((n & 0x3333333333333333) << 2); n = ((n & 0xf0f0f0f0f0f0f0f0) >> 4) | ((n & 0x0f0f0f0f0f0f0f0f) << 4); return n; } 

Esta es exactamente la misma idea que el mejor algoritmo de Matt, excepto que hay una pequeña instrucción llamada BSWAP que intercambia los bytes (no los bits) de un número de 64 bits. Entonces b7, b6, b5, b4, b3, b2, b1, b0 se convierte en b0, b1, b2, b3, b4, b5, b6, b7. Dado que estamos trabajando con un número de 32 bits, necesitamos cambiar nuestro número de bytes intercambiados por 32 bits. Esto simplemente nos deja con la tarea de intercambiar los 8 bits de cada byte que está hecho y listo. hemos terminado.

Tiempo: en mi máquina, el algoritmo de Matt funcionó en ~ 0.52 segundos por prueba. El mío corrió en aproximadamente 0,42 segundos por prueba. Un 20% más rápido no es malo, creo.

Si le preocupa la disponibilidad de la instrucción, BSWAP Wikipedia enumera la instrucción BSWAP como agregada con 80846, que apareció en 1989. Cabe señalar que Wikipedia también afirma que esta instrucción solo funciona en registros de 32 bits que claramente no es el caso en mi máquina, funciona mucho solo en registros de 64 bits.

Este método funcionará igual de bien para cualquier tipo de datos integrales, por lo que el método se puede generalizar trivialmente al pasar la cantidad de bytes deseados:

  size_t reverse(size_t n, unsigned int bytes) { __asm__("BSWAP %0" : "=r"(n) : "0"(n)); n >>= ((sizeof(size_t) - bytes) * 8); n = ((n & 0xaaaaaaaaaaaaaaaa) >> 1) | ((n & 0x5555555555555555) << 1); n = ((n & 0xcccccccccccccccc) >> 2) | ((n & 0x3333333333333333) << 2); n = ((n & 0xf0f0f0f0f0f0f0f0) >> 4) | ((n & 0x0f0f0f0f0f0f0f0f) << 4); return n; } 

que luego se puede llamar así:

  n = reverse(n, sizeof(char));//only reverse 8 bits n = reverse(n, sizeof(short));//reverse 16 bits n = reverse(n, sizeof(int));//reverse 32 bits n = reverse(n, sizeof(size_t));//reverse 64 bits 

El comstackdor debería poder optimizar el parámetro adicional (suponiendo que el comstackdor lo refiera) y para el tamaño del caso sizeof(size_t) el desplazamiento a la derecha se eliminaría por completo. Tenga en cuenta que, al menos, GCC no puede eliminar el BSWAP y el desplazamiento a la derecha si pasa el sizeof(char) .

Suponiendo que tiene una matriz de bits, qué tal esto: 1. Comenzando desde MSB, inserte bits en una stack uno por uno. 2. Inserte los bits de esta stack en otra matriz (o la misma matriz si desea ahorrar espacio), colocando el primer bit reventado en MSB y pasando a bits menos significativos desde allí.

 Stack stack = new Stack(); Bit[] bits = new Bit[] { 0, 0, 1, 0, 0, 0, 0, 0 }; for (int i = 0; i < bits.Length; i++) { stack.push(bits[i]); } for (int i = 0; i < bits.Length; i++) { bits[i] = stack.pop(); } 

¡Este no es un trabajo para un humano! … pero perfecto para una máquina

Esto es 2015, 6 años desde que se hizo esta pregunta por primera vez. Los comstackdores se han convertido en nuestros maestros, y nuestro trabajo como humanos es solo para ayudarlos. Entonces, ¿cuál es la mejor manera de dar nuestras intenciones a la máquina?

La inversión de bits es tan común que debe preguntarse por qué el ISA cada vez mayor de x86 no incluye instrucciones para hacerlo de una vez.

La razón: si le das tu verdadero bash conciso al comstackdor, la inversión de bits solo debería tomar ~ 20 ciclos de CPU . Déjame mostrarte cómo crear reverse () y usarlo:

 #include  #include  uint64_t reverse(const uint64_t n, const uint64_t k) { uint64_t r, i; for (r = 0, i = 0; i < k; ++i) r |= ((n >> i) & 1) << (k - i - 1); return r; } int main() { const uint64_t size = 64; uint64_t sum = 0; uint64_t a; for (a = 0; a < (uint64_t)1 << 30; ++a) sum += reverse(a, size); printf("%" PRIu64 "\n", sum); return 0; } 

Al comstackr este progtwig de ejemplo con la versión de Clang> = 3.6, -O3, -march = native (probado con Haswell), se proporciona un código de calidad de ilustraciones usando las nuevas instrucciones AVX2, con un tiempo de ejecución de 11 segundos procesando ~ 1 mil millones reverse () s. Eso es ~ 10 ns por reversa (), con un ciclo de CPU de .5 ns suponiendo que 2 GHz nos pone en los dulces 20 ciclos de CPU.

  • Puede ajustar 10 reverse () s en el tiempo que lleva acceder a la RAM una vez para una única matriz grande.
  • You can fit 1 reverse() in the time it takes to access an L2 cache LUT twice.

Caveat: this sample code should hold as a decent benchmark for a few years, but it will eventually start to show its age once compilers are smart enough to optimize main() to just printf the final result instead of really computing anything. But for now it works in showcasing reverse().

Of course the obvious source of bit-twiddling hacks is here: http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

Native ARM instruction “rbit” can do it with 1 cpu cycle and 1 extra cpu register, impossible to beat.

I know it isn’t C but asm:

 var1 dw 0f0f0 clc push ax push cx mov cx 16 loop1: shl var1 shr ax loop loop1 pop ax pop cx 

This works with the carry bit, so you may save flags too

Implementation with low memory and fastest.

 private Byte BitReverse(Byte bData) { Byte[] lookup = { 0, 8, 4, 12, 2, 10, 6, 14 , 1, 9, 5, 13, 3, 11, 7, 15 }; Byte ret_val = (Byte)(((lookup[(bData & 0x0F)]) << 4) + lookup[((bData & 0xF0) >> 4)]); return ret_val; } 

I was curious how fast would be the obvious raw rotation. On my machine (i7@2600), the average for 1,500,150,000 iterations was 27.28 ns (over aa random set of 131,071 64-bit integers).

Advantages: the amount of memory needed is little and the code is simple. I would say it is not that large, either. The time required is predictable and constant for any input (128 arithmetic SHIFT operations + 64 logical AND operations + 64 logical OR operations).

I compared to the best time obtained by @Matt J – who has the accepted answer. If I read his answer correctly, the best he has got was 0.631739 seconds for 1,000,000 iterations, which leads to an average of 631 ns per rotation.

The code snippet I used is this one below:

 unsigned long long reverse_long(unsigned long long x) { return (((x >> 0) & 1) << 63) | (((x >> 1) & 1) << 62) | (((x >> 2) & 1) << 61) | (((x >> 3) & 1) << 60) | (((x >> 4) & 1) << 59) | (((x >> 5) & 1) << 58) | (((x >> 6) & 1) << 57) | (((x >> 7) & 1) << 56) | (((x >> 8) & 1) << 55) | (((x >> 9) & 1) << 54) | (((x >> 10) & 1) << 53) | (((x >> 11) & 1) << 52) | (((x >> 12) & 1) << 51) | (((x >> 13) & 1) << 50) | (((x >> 14) & 1) << 49) | (((x >> 15) & 1) << 48) | (((x >> 16) & 1) << 47) | (((x >> 17) & 1) << 46) | (((x >> 18) & 1) << 45) | (((x >> 19) & 1) << 44) | (((x >> 20) & 1) << 43) | (((x >> 21) & 1) << 42) | (((x >> 22) & 1) << 41) | (((x >> 23) & 1) << 40) | (((x >> 24) & 1) << 39) | (((x >> 25) & 1) << 38) | (((x >> 26) & 1) << 37) | (((x >> 27) & 1) << 36) | (((x >> 28) & 1) << 35) | (((x >> 29) & 1) << 34) | (((x >> 30) & 1) << 33) | (((x >> 31) & 1) << 32) | (((x >> 32) & 1) << 31) | (((x >> 33) & 1) << 30) | (((x >> 34) & 1) << 29) | (((x >> 35) & 1) << 28) | (((x >> 36) & 1) << 27) | (((x >> 37) & 1) << 26) | (((x >> 38) & 1) << 25) | (((x >> 39) & 1) << 24) | (((x >> 40) & 1) << 23) | (((x >> 41) & 1) << 22) | (((x >> 42) & 1) << 21) | (((x >> 43) & 1) << 20) | (((x >> 44) & 1) << 19) | (((x >> 45) & 1) << 18) | (((x >> 46) & 1) << 17) | (((x >> 47) & 1) << 16) | (((x >> 48) & 1) << 15) | (((x >> 49) & 1) << 14) | (((x >> 50) & 1) << 13) | (((x >> 51) & 1) << 12) | (((x >> 52) & 1) << 11) | (((x >> 53) & 1) << 10) | (((x >> 54) & 1) << 9) | (((x >> 55) & 1) << 8) | (((x >> 56) & 1) << 7) | (((x >> 57) & 1) << 6) | (((x >> 58) & 1) << 5) | (((x >> 59) & 1) << 4) | (((x >> 60) & 1) << 3) | (((x >> 61) & 1) << 2) | (((x >> 62) & 1) << 1) | (((x >> 63) & 1) << 0); } 

Well, this is basically the same as the first “reverse()” but it is 64 bit and only needs one immediate mask to be loaded from the instruction stream. GCC creates code without jumps, so this should be pretty fast.

 #include  static unsigned long long swap64(unsigned long long val) { #define ZZZZ(x,s,m) (((x) >>(s)) & (m)) | (((x) & (m))<<(s)); /* val = (((val) >>16) & 0xFFFF0000FFFF) | (((val) & 0xFFFF0000FFFF)<<16); */ val = ZZZZ(val,32, 0x00000000FFFFFFFFull ); val = ZZZZ(val,16, 0x0000FFFF0000FFFFull ); val = ZZZZ(val,8, 0x00FF00FF00FF00FFull ); val = ZZZZ(val,4, 0x0F0F0F0F0F0F0F0Full ); val = ZZZZ(val,2, 0x3333333333333333ull ); val = ZZZZ(val,1, 0x5555555555555555ull ); return val; #undef ZZZZ } int main(void) { unsigned long long val, aaaa[16] = { 0xfedcba9876543210,0xedcba9876543210f,0xdcba9876543210fe,0xcba9876543210fed , 0xba9876543210fedc,0xa9876543210fedcb,0x9876543210fedcba,0x876543210fedcba9 , 0x76543210fedcba98,0x6543210fedcba987,0x543210fedcba9876,0x43210fedcba98765 , 0x3210fedcba987654,0x210fedcba9876543,0x10fedcba98765432,0x0fedcba987654321 }; unsigned iii; for (iii=0; iii < 16; iii++) { val = swap64 (aaaa[iii]); printf("A[]=%016llX Sw=%016llx\n", aaaa[iii], val); } return 0; } 

You might want to use the standard template library. It might be slower than the above mentioned code. However, it seems to me clearer and easier to understand.

  #include #include template const std::bitset reverse(const std::bitset& ordered) { std::bitset reversed; for(size_t i = 0, j = N - 1; i < N; ++i, --j) reversed[j] = ordered[i]; return reversed; }; // test the function int main() { unsigned long num; const size_t N = sizeof(num)*8; std::cin >> num; std::cout << std::showbase << std::hex; std::cout << "ordered = " << num << std::endl; std::cout << "reversed = " << reverse(num).to_ulong() << std::endl; std::cout << "double_reversed = " << reverse(reverse(num)).to_ulong() << std::endl; } 

Genérico

C code. Using 1 byte input data num as example.

  unsigned char num = 0xaa; // 1010 1010 (aa) -> 0101 0101 (55) int s = sizeof(num) * 8; // get number of bits int i, x, y, p; int var = 0; // make var data type to be equal or larger than num for (i = 0; i < (s / 2); i++) { // extract bit on the left, from MSB p = s - i - 1; x = num & (1 << p); x = x >> p; printf("x: %d\n", x); // extract bit on the right, from LSB y = num & (1 << i); y = y >> i; printf("y: %d\n", y); var = var | (x << i); // apply x var = var | (y << p); // apply y } printf("new: 0x%x\n", new); 

How about the following:

  uint reverseMSBToLSB32ui(uint input) { uint output = 0x00000000; uint toANDVar = 0; int places = 0; for (int i = 1; i < 32; i++) { places = (32 - i); toANDVar = (uint)(1 << places); output |= (uint)(input & (toANDVar)) >> places; } return output; } 

Small and easy (though, 32 bit only).

I thought this is one of the simplest way to reverse the bit. please let me know if there is any flaw in this logic. basically in this logic, we check the value of the bit in position. set the bit if value is 1 on reversed position.

 void bit_reverse(ui32 *data) { ui32 temp = 0; ui32 i, bit_len; { for(i = 0, bit_len = 31; i <= bit_len; i++) { temp |= (*data & 1 << i)? (1 << bit_len-i) : 0; } *data = temp; } return; } 
 unsigned char ReverseBits(unsigned char data) { unsigned char k = 0, rev = 0; unsigned char n = data; while(n) { k = n & (~(n - 1)); n &= (n - 1); rev |= (128 / k); } return rev; } 

I think the simplest method I know follows. MSB is input and LSB is ‘reversed’ output:

 unsigned char rev(char MSB) { unsigned char LSB=0; // for output _FOR(i,0,8) { LSB= LSB << 1; if(MSB&1) LSB = LSB | 1; MSB= MSB >> 1; } return LSB; } // It works by rotating bytes in opposite directions. // Just repeat for each byte. 
 // Purpose: to reverse bits in an unsigned short integer // Input: an unsigned short integer whose bits are to be reversed // Output: an unsigned short integer with the reversed bits of the input one unsigned short ReverseBits( unsigned short a ) { // declare and initialize number of bits in the unsigned short integer const char num_bits = sizeof(a) * CHAR_BIT; // declare and initialize bitset representation of integer a bitset bitset_a(a); // declare and initialize bitset representation of integer b (0000000000000000) bitset bitset_b(0); // declare and initialize bitset representation of mask (0000000000000001) bitset mask(1); for ( char i = 0; i < num_bits; ++i ) { bitset_b = (bitset_b << 1) | bitset_a & mask; bitset_a >>= 1; } return (unsigned short) bitset_b.to_ulong(); } void PrintBits( unsigned short a ) { // declare and initialize bitset representation of a bitset bitset(a); // print out bits cout << bitset << endl; } // Testing the functionality of the code int main () { unsigned short a = 17, b; cout << "Original: "; PrintBits(a); b = ReverseBits( a ); cout << "Reversed: "; PrintBits(b); } // Output: Original: 0000000000010001 Reversed: 1000100000000000 

Another loop-based solution that exits quickly when the number is low (in C++ for multiple types)

 template T reverse_bits(T in) { T bit = static_cast(1) << (sizeof(T) * 8 - 1); T out; for (out = 0; bit && in; bit >>= 1, in >>= 1) { if (in & 1) { out |= bit; } } return out; } 

or in C for an unsigned int

 unsigned int reverse_bits(unsigned int in) { unsigned int bit = 1u << (sizeof(T) * 8 - 1); unsigned int out; for (out = 0; bit && in; bit >>= 1, in >>= 1) { if (in & 1) out |= bit; } return out; } 

It seems that many other posts are concerned about speed (ie best = fastest). What about simplicity? Considerar:

 char ReverseBits(char character) { char reversed_character = 0; for (int i = 0; i < 8; i++) { char ith_bit = (c >> i) & 1; reversed_character |= (ith_bit << (sizeof(char) - 1 - i)); } return reversed_character; } 

and hope that clever compiler will optimise for you.

If you want to reverse a longer list of bits (containing sizeof(char) * n bits), you can use this function to get:

 void ReverseNumber(char* number, int bit_count_in_number) { int bytes_occupied = bit_count_in_number / sizeof(char); // first reverse bytes for (int i = 0; i <= (bytes_occupied / 2); i++) { swap(long_number[i], long_number[n - i]); } // then reverse bits of each individual byte for (int i = 0; i < bytes_occupied; i++) { long_number[i] = ReverseBits(long_number[i]); } } 

This would reverse [10000000, 10101010] into [01010101, 00000001].

Bit reversal in pseudo code

source -> byte to be reversed b00101100 destination -> reversed, also needs to be of unsigned type so sign bit is not propogated down

copy into temp so original is unaffected, also needs to be of unsigned type so that sign bit is not shifted in automaticaly

 bytecopy = b0010110 

LOOP8: //do this 8 times test if bytecopy is < 0 (negative)

  set bit8 (msb) of reversed = reversed | b10000000 else do not set bit8 shift bytecopy left 1 place bytecopy = bytecopy << 1 = b0101100 result shift result right 1 place reversed = reversed >> 1 = b00000000 8 times no then up^ LOOP8 8 times yes then done. 

My simple solution

 BitReverse(IN) OUT = 0x00; R = 1; // Right mask ...0000.0001 L = 0; // Left mask 1000.0000... L = ~0; L = ~(i >> 1); int size = sizeof(IN) * 4; // bit size while(size--){ if(IN & L) OUT = OUT | R; // start from MSB 1000.xxxx if(IN & R) OUT = OUT | L; // start from LSB xxxx.0001 L = L >> 1; R = R << 1; } return OUT; 

This is for 32 bit, we need to change the size if we consider 8 bits.

  void bitReverse(int num) { int num_reverse = 0; int size = (sizeof(int)*8) -1; int i=0,j=0; for(i=0,j=size;i<=size,j>=0;i++,j--) { if((num >> i)&1) { num_reverse = (num_reverse | (1< 

Reading the input integer "num" in LSB->MSB order and storing in num_reverse in MSB->LSB order.

 int bit_reverse(int w, int bits) { int r = 0; for (int i = 0; i < bits; i++) { int bit = (w & (1 << i)) >> i; r |= bit << (bits - i - 1); } return r; }