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

243

¿Cuál es el algoritmo más eficiente 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.

green_t
fuente
1
Creo que el nombre apropiado es una operación bit a bit.
Kredns el
55
Creo que querías decir inversión, no rotación.
Juliano el
2
La mayoría de los procesadores ARM tienen una operación integrada para eso. El ARM Cortex-M0 no lo hace, y descubrí que usar una tabla por byte para intercambiar bits es el enfoque más rápido.
Starblue
2
También vea los trucos de Twiddling de Sean Eron Anderson .
jww
2
Defina "mejor"
Lee Taylor

Respuestas:

497

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

Opciones

Memoria baja ( intmáquina de 32 bits , 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 ampliar esta idea a 64 bits int, o cambiar la memoria por velocidad (suponiendo que su caché de datos L1 sea lo suficientemente grande) e invertir 16 bits a la vez con una tabla de búsqueda de 64K.


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 bit de 32 bits int, simplemente invierta los bits en cada byte e invierta 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 bit-AND (la primera). La máquina de prueba es una computadora portátil con 4GB de DDR2-800 y un Core 2 Duo T7500 @ 2.4GHz, 4MB L2 Cache; YMMV. Solía gcc 4.3.2 en Linux de 64 bits. OpenMP (y los enlaces GCC) se utilizaron para temporizadores de alta resolución.

reverse.c

#include <stdlib.h>
#include <stdio.h>
#include <omp.h>

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 <stdlib.h>
#include <stdio.h>
#include <omp.h>

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 con varias optimizaciones diferentes, ejecuté 3 ensayos en cada nivel y cada ensayo revirtió 100 millones al azar unsigned ints. Para la opción de tabla de búsqueda, probé ambos esquemas (opciones 1 y 2) que figuran 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 exprimir hasta el último byte de memoria de su sistema (y podría, si le preocupa el rendimiento de la inversión de bits), las versiones optimizadas del enfoque bit a bit Y tampoco son demasiado malas.

Consideración

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 sé sobre:

  • 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 microarquitecturas modernas con L1D grande.
  • -mtune = native no funcionó para -O2 / -O3 ( ldexplotó con algún error de redefinición de símbolo loco), por lo que no creo que el código generado esté ajustado para mi microarquitectura.
  • Puede haber una manera de hacerlo un poco más rápido con SSE. No tengo idea de cómo, pero con una replicación rápida, empaquetado a nivel de bits Y e instrucciones vertiginosas, debe haber algo allí.
  • Solo conozco suficiente ensamblaje x86 para ser peligroso; Aquí está el código que GCC generó 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_ttipos en mi máquina para ver si hubo algún aumento en el rendimiento. El rendimiento fue aproximadamente un 10% más rápido que el de 32 bits, y fue casi idéntico tanto si estaba utilizando tipos de 64 bits para invertir bits en dos inttipos de 32 bits a la vez, como si realmente estaba invirtiendo bits en la mitad de 64- valores de bit El código de ensamblaje se muestra a continuación (para el caso anterior, invirtiendo bits para dos inttipos 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
Matt J
fuente
2
-1 para publicaciones excesivamente detalladas y exhaustivas. j / k. +1.
mpen
8
Fue un ejercicio interesante, si no tan satisfactorio. Por lo menos, espero que el proceso sea constructivo para alguien más que quiera comparar algo más meritorio :)
Matt J
55
¡Dios mío! Creo que he encontrado ... lo que bien podría ser ... un VERDADERO espécimen. Tendré que consultar mis documentos e investigar más, pero algo me dice (Dios, ayúdame), que esta es, con mucho, la respuesta más grande, exhaustiva y útil que Stack Overflow ha tenido hasta ahora. ¡Incluso John Skeet estaría horrorizado e impresionado!
zeboidlund
3
Tenga en cuenta que un defecto particular de microbenchmarking (entre una lista de muchos otros) es que tiende a favorecer artificialmente las soluciones basadas en tablas de búsqueda. Dado que el punto de referencia está repitiendo la única operación en un bucle, a menudo encontrará que usar una tabla de búsqueda que solo se ajusta en L1 es lo más rápido, porque todo golpeará en L1 cada vez ya que no hay presión de caché en absoluto. En un caso de uso real, la operación generalmente se intercalará con otras operaciones que causen cierta presión de caché. Una falla en RAM podría tomar 10 o 100 veces más de lo habitual, pero esto se ignora en los puntos de referencia.
BeeOnRope
2
El resultado es que si dos soluciones están cerca, a menudo elijo la solución que no es LUT (o la que tiene una LUT más pequeña) porque el impacto real de una LUT puede ser grave. Aún mejor sería comparar cada solución "in situ", donde realmente se utiliza en la aplicación más grande, con aportes realistas. Por supuesto, no siempre tenemos tiempo para eso, y no siempre sabemos qué es una entrada realista.
BeeOnRope
80

Este hilo me llamó la atención ya que trata un problema simple que requiere mucho trabajo (ciclos de CPU) incluso para una CPU moderna. Y un día también estuve 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 extremo!

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

El bitflipping de búsqueda de Matt J 400 000 000 bytes: alrededor de 0.272 segundos.

Luego seguí adelante e intenté ver si el compilador ISPC de Intel podía vectorizar la aritmética en el reverso. C.

No voy a aburrirlos con mis hallazgos aquí, ya que intenté mucho para ayudar al compilador a encontrar cosas, de todos modos terminé con un rendimiento de alrededor de 0,15 segundos para bitflip 400 000 000 bytes. Es una gran reducción, pero para mi aplicación todavía es demasiado lenta.

Entonces, la gente me deja presentar el bitflipper basado en Intel más rápido del mundo. Reloj a:

Tiempo de 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 <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <omp.h>

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

Los printf son para depurar ...

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 desplazarme a la izquierda antes de ORar los mordiscos juntos nuevamente.

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

No haga comentarios sobre el uso de los comandos equivalentes intrínsecos del compilador Intel C / C ++ ...

Anders Cedronius
fuente
2
Te mereces MUCHO más votos a favor que esto. Sabía que esto debería ser factible pshub, porque después de todo, ¡la mejor cuenta también se hace con ella! Lo hubiera escrito aquí si no fuera por ti. Prestigio.
Iwillnotexist Idonotexist
3
¡Gracias! 'popcnt' es otro de mis temas favoritos;) Mira mi versión de BMI2: result = __ tzcnt_u64 (~ _pext_u64 (data [i], data [i]));
Anders Cedronius 01 de
3
Denomine el archivo asm: bitflip_asm.s luego: yasm -f elf64 bitflip_asm.s Denomine el archivo c: bitflip.c luego: g ++ -fopenmp bitflip.c bitflip_asm.o -o bitflip Eso es todo.
Anders Cedronius
44
Las CPU Intel tienen las unidades de ejecución para popcnt, tzcnty pexttodos en el puerto 1. Por lo tanto, cada uno pexto le tzcntcuesta un popcntrendimiento. Si sus datos están calientes en el caché L1D, la forma más rápida de contar una matriz en las CPU Intel es con AVX2 pshufb. (Ryzen tiene un popcntrendimiento de 4 por reloj, por lo que probablemente sea óptimo, pero la familia Bulldozer tiene un popcnt r64,r64rendimiento de cada 4 relojes ... agner.org/optimize ).
Peter Cordes
44
Estoy usando una versión intrínseca yo mismo. Sin embargo, cuando respondí, publiqué lo que tenía y supe por publicaciones anteriores que tan pronto como escribo ensamblador, un smart aleck siempre señala que debería haberlo hecho intrínsecamente. Cuando desarrollo, primero escribo el ensamblador, luego, cuando me gusta el resultado, paso a lo intrínseco ... Ese soy yo ... Acabo de publicar mi respuesta cuando solo tenía mi versión de ensamblador 'prueba'.
Anders Cedronius
16

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 llegue a 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);
}

Esta es la salida:

Bit Reversal Input = 0x55 Output = 0xaa
Bit Reversal Input = 0xabcd Output = 0xb3d5
Bit Reversal Input = 0x123456 Output = 0x651690
Bit Reversal Input = 0x11223344 Output = 0x22cc4488
Dennis Mathews
fuente
¿Este enfoque no funciona en el ejemplo de 24 bits (3er)? No estoy muy familiarizado con los operadores C y bit a bit, pero por su explicación del enfoque supongo que 24-> 12-> 6-> 3 (3 bits desiguales para dividir). Como numBitses int, cuando divide 3 por 2 para la función param se redondeará a 1?
Brennan
13

Bueno, esto ciertamente no será una respuesta como la de Matt J, pero espero que siga siendo ú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 intercambio de bytes hacia abajo 32 bits. ¡Esto nos deja con la tarea de intercambiar los 8 bits de cada byte que está hecho y listo! Ya hemos terminado.

Tiempo: en mi máquina, el algoritmo de Matt se ejecutó en ~ 0.52 segundos por prueba. La mía corrió en aproximadamente 0,42 segundos por prueba. 20% más rápido no está mal, creo.

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

Este método funcionará igualmente bien para cualquier tipo de datos integral, por lo que el método puede generalizarse trivialmente pasando el número de bytes deseado:

    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 como:

    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 compilador debería poder optimizar el parámetro adicional (suponiendo que el compilador incorpore la función) y para el sizeof(size_t)caso, el desplazamiento a la derecha se eliminaría por completo. Tenga en cuenta que GCC al menos no puede eliminar el BSWAP y el desplazamiento a la derecha si se aprueba sizeof(char).

SirGuy
fuente
2
De acuerdo con el Volumen de referencia del conjunto de instrucciones Intel 2A ( intel.com/content/www/us/en/processors/… ) hay dos instrucciones BSWAP: BSWAP r32 (trabajando en registros de 32 bits), que está codificada como 0F C8 + rd y BSWAP r64 (trabajando en registros de 64 bits), que está codificado como REX.W + 0F C8 + rd.
Nubok
Dices que se puede usar así: "n = reverse (n, sizeof (size_t)); // reverse 64 bits", sin embargo, esto dará solo 32 bits de resultado a menos que todas las constantes se extiendan a 64 bits, entonces funciona.
rajkosto
@rajkosto a partir de C ++ 11, los tipos permitidos de literales enteros incluyen los unsigned long long intque deben tener al menos 64 bits, según aquí y aquí
SirGuy
¿De acuerdo? Solo digo que si quiere que esto funcione en valores de 64 bits, debe extender sus literales (por lo que son 0xf0f0f0f0f0f0f0f0ull, por ejemplo), de lo contrario, los 32 bits altos del resultado serán todos 0s.
rajkosto
@rajkosto Ah, había entendido mal su primer comentario, lo he solucionado ahora
SirGuy
13

La respuesta de Anders Cedronius ofrece 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 método clásico de particionamiento binario, codificado para maximizar el uso de la expresión shift-plus-logic útil en varios procesadores ARM. Además, utiliza la generación de máscaras sobre la marcha que podría ser beneficiosa para los procesadores RISC que, de lo contrario, requieren múltiples instrucciones para cargar cada valor de máscara de 32 bits. Los compiladores para plataformas x86 deben usar propagación constante para calcular todas las máscaras en tiempo de compilació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 programación de computadoras", D. Knuth muestra formas inteligentes de revertir bits que sorprendentemente 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 compilador Intel C / C ++ 13.1.3.198, ambas funciones anteriores auto-vectorizan bien los XMMregistros de destino . También se pueden vectorizar manualmente sin mucho esfuerzo.

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

njuffa
fuente
2
@JoelSnyder Supongo que por "muchos números mágicos" te refieres principalmente brev_knuth()? La atribución en el PDF de Hacker's Delight parece indicar que estos números son directamente del propio Knuth. No puedo afirmar que he entendido la descripción de Knuth de los principios de diseño subyacentes en TAOCP lo suficiente como para explicar cómo se derivaron las constantes, o cómo se abordarían las constantes derivadas y los factores de cambio para tamaños de palabras arbitrarios.
njuffa
8

Suponiendo que tiene una matriz de bits, ¿qué tal esto? 1. Comenzando desde MSB, inserte los bits en una pila uno por uno. 2. Haga estallar los bits de esta pila 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();
}
Federico el tonto
fuente
3
Éste me hizo sonreír :) Me gustaría ver un punto de referencia de esta solución # C contra uno de los que he descrito en C. optimizado
Matt J
LOL ... Pero oye! el adjetivo 'mejor' en el 'mejor algoritmo' es algo bastante subjetivo: D
Frederick The Fool el
7

La instrucción ARM nativa "rbit" puede hacerlo con 1 ciclo de CPU y 1 registro de CPU adicional, imposible de superar.

metalogico
fuente
6

¡Esto no es trabajo para un humano! ... pero perfecto para una máquina

Esto es 2015, 6 años después de que se hizo esta pregunta por primera vez. Los compiladores se han convertido en nuestros maestros y nuestro trabajo como humanos es solo 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 del x86 no incluye instrucciones para hacerlo de una vez.

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

#include <inttypes.h>
#include <stdio.h>

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

Compilar este programa de muestra con la versión Clang> = 3.6, -O3, -march = native (probado con Haswell), proporciona un código de calidad de diseño utilizando las nuevas instrucciones AVX2, con un tiempo de ejecución de 11 segundos procesando ~ 1 billón de reverse () s. Eso es ~ 10 ns por marcha atrás (), con un ciclo de CPU de .5 ns, suponiendo que 2 GHz nos coloca en los 20 ciclos de CPU.

  • ¡Puede ajustar 10 reverse () s en el tiempo que toma acceder a RAM una vez para una sola matriz grande!
  • Puede ajustar 1 reverse () en el tiempo que toma acceder a una LUT de caché L2 dos veces.

Advertencia: este código de muestra debería ser un punto de referencia decente durante algunos años, pero eventualmente comenzará a mostrar su antigüedad una vez que los compiladores sean lo suficientemente inteligentes como para optimizar main () para simplemente imprimir el resultado final en lugar de calcular realmente nada. Pero por ahora funciona en mostrar reverse ().

Samuel Liew
fuente
Bit-reversal is so common...No se sobre eso. Trabajo con código que maneja datos a nivel de bits prácticamente todos los días, y no recuerdo haber tenido esta necesidad específica. ¿En qué escenarios lo necesitas? - No es que no sea un problema interesante de resolver por derecho propio.
500 - Error interno del servidor
@ 500-InternalServerError Termino necesitando esta función muchas veces en inferencia gramatical con estructuras de datos rápidas y concisas. Un árbol binario normal codificado como un bitarray termina infiriendo la gramática en orden "big endian". Pero para una mejor generalización si construyes un árbol (bitarray) con nodos intercambiados por la permutación de inversión de bits, las cadenas de la gramática aprendida están en "little endian". Ese cambio le permite inferir cadenas de longitud variable en lugar de tamaños enteros fijos. Esta situación también aparece mucho en FFT eficiente: ver en.wikipedia.org/wiki/Bit-reversal_permutation
1
Gracias, de alguna manera logré intuir que FFT podría estar involucrado en su respuesta :)
500 - Error interno del servidor
¿Por qué solo 20 ciclos? Cual arquitectura ¿Es esto cierto para todas las arquitecturas VLIW súper amplias del futuro hasta que la humanidad y nuestros descendientes se extingan? Solo preguntas, sin respuestas ... Voto al infierno de nuevo
Quonux
5

Sé que no es C pero asm:

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

Esto funciona con el bit de transporte, por lo que también puede guardar banderas

Coco
fuente
1
Supongo que podría usar la palabra clave asm , que sería bastante rápida.
tom
Esto ni siquiera funciona. Creo que quieres rclcambiar CF a var1, en lugar de solo shllo que no lee las banderas. (O adc dx,dx). Incluso con esa solución, ¡esto es ridículamente lento, usando las loopinstrucciones lentas y guardando var1en la memoria! En realidad, creo que se supone que esto está produciendo la salida en AX, pero guarda / restaura el valor anterior de AX por encima del resultado.
Peter Cordes
4

Implementación con poca memoria y más rápida.

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;
    }
Aung
fuente
4

Bueno, esto es básicamente lo mismo que el primer "reverse ()" pero es de 64 bits y solo necesita una máscara inmediata para cargarse desde el flujo de instrucciones. GCC crea código sin saltos, por lo que esto debería ser bastante rápido.

#include <stdio.h>

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;
}
wildplasser
fuente
4

Tenía curiosidad por lo rápido que sería la rotación cruda obvia. En mi máquina (i7 @ 2600), el promedio de 1,500,150,000 iteraciones fue 27.28 ns(sobre un conjunto aleatorio de 131,071 enteros de 64 bits).

Ventajas: la cantidad de memoria necesaria es pequeña y el código es simple. Yo diría que tampoco es tan grande. El tiempo requerido es predecible y constante para cualquier entrada (128 operaciones SHIFT aritméticas + 64 operaciones lógicas AND + 64 operaciones lógicas OR).

Comparé el mejor momento obtenido por @Matt J, quien tiene la respuesta aceptada. Si leí su respuesta correctamente, lo mejor que obtuvo fue 0.631739segundos para 1,000,000iteraciones, lo que lleva a un promedio de 631 nspor rotación.

El fragmento de código que utilicé es el siguiente:

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);
}
marian adam
fuente
@greybeard No estoy seguro de entender tu pregunta.
marian adam
gracias por notar el error, arreglé el código de muestra proporcionado.
marian adam
3

Es posible que desee utilizar la biblioteca de plantillas estándar. Puede ser más lento que el código mencionado anteriormente. Sin embargo, me parece más claro y más fácil de entender.

 #include<bitset>
 #include<iostream>


 template<size_t N>
 const std::bitset<N> reverse(const std::bitset<N>& ordered)
 {
      std::bitset<N> 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<N>(num).to_ulong()  << std::endl;
      std::cout << "double_reversed = " << reverse<N>(reverse<N>(num)).to_ulong() << std::endl;  
 }
Cem
fuente
2

Genérico

Código C. Usando 1 byte de datos de entrada num como ejemplo.

    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);
vjangus
fuente
La pregunta pedía "más eficiente", no "simple / directo".
Peter Cordes
1

¿Qué tal lo siguiente:

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

Pequeño y fácil (aunque solo de 32 bits).

BlueAutumn
fuente
La pregunta pedida "más eficiente"; podemos descartar bucles 32 veces. (Y especialmente no cambiar la máscara, así como tener que cambiar el resultado al LSB)
Peter Cordes
1

Pensé que esta es una de las formas más simples de revertir el bit. por favor avíseme si hay algún defecto en esta lógica. Básicamente, en esta lógica, verificamos el valor del bit en posición. establezca el bit si el valor es 1 en posición invertida.

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;    
}    
Arun Nagendran
fuente
La pregunta pedía "más eficiente", no "simple / directo".
Peter Cordes
0
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;
}
usuario3615967
fuente
Interesante, pero la división por una variable de tiempo de ejecución es lenta. ksiempre es una potencia de 2, pero los compiladores probablemente no lo prueben y lo conviertan en bit-scan / shift.
Peter Cordes
0

Creo que el método más simple que conozco sigue. MSBes entrada y LSBes salida 'invertida':

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.
usuario7726695
fuente
0
// 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<num_bits> bitset_a(a);          

     // declare and initialize bitset representation of integer b (0000000000000000)
     bitset<num_bits> bitset_b(0);                  

     // declare and initialize bitset representation of mask (0000000000000001)
     bitset<num_bits> 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<sizeof(a) * CHAR_BIT> 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
MikhailJacques
fuente
0

Otra solución basada en bucles que sale rápidamente cuando el número es bajo (en C ++ para múltiples tipos)

template<class T>
T reverse_bits(T in) {
    T bit = static_cast<T>(1) << (sizeof(T) * 8 - 1);
    T out;

    for (out = 0; bit && in; bit >>= 1, in >>= 1) {
        if (in & 1) {
            out |= bit;
        }
    }
    return out;
}

o en C para un int sin firmar

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;
}
Daniel Santos
fuente
0

Parece que muchas otras publicaciones están preocupadas por la velocidad (es decir, mejor = más rápido). ¿Qué pasa con la simplicidad? 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;
}

y espero que ese compilador inteligente se optimice para usted.

Si desea invertir una lista más larga de bits (que contiene sizeof(char) * nbits), puede usar esta función para obtener:

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

Esto revertiría [10000000, 10101010] en [01010101, 00000001].

mercurio0114
fuente
Tienes 3 turnos en el circuito interno. Ahorre uno con ith_bit = (c >> i) & 1. También guarde un SUB desplazando en reversed_charlugar de desplazar el bit, a menos que espere que se compile en x86 a sub something/ bts reg,regpara establecer el enésimo bit en el registro de destino.
Peter Cordes
-1

Inversión de bits en pseudocódigo

fuente -> byte para revertir b00101100 destino -> revertir, también debe ser de tipo sin signo para que el bit de signo no se propague hacia abajo

copiar en temp para que el original no se vea afectado, también debe ser de tipo sin signo para que el bit de signo no se cambie automáticamente

bytecopy = b0010110

LOOP8: // realiza esta prueba 8 veces si la bytecopy es <0 (negativa)

    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.
Peter Sikora
fuente
-1

Mi simple solucion

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;
Ivan Hionidi
fuente
1
¿Qué es i? Además, ¿qué es esa constante mágica * 4? Es CHAR_BIT / 2?
Peter Cordes
-1

Esto es para 32 bits, necesitamos cambiar el tamaño si consideramos 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<<j));
            }
        }
        printf("\n rev num = %d\n",num_reverse);
    }

Lectura del entero de entrada "num" en orden LSB-> MSB y almacenamiento en num_reverse en orden MSB-> LSB.

karthik kalakodimi
fuente
1
Debe agregar una explicación al código para que se entienda más fácilmente.
Tunaki
-3
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;
}
Shihao Xu
fuente
3
En general, las respuestas son mucho más útiles si incluyen una explicación de lo que el código pretende hacer y por qué eso resuelve el problema.
IKavanagh