Patrón de bits inverso en C

Estoy convirtiendo un número a binario y tengo que usar putchar para generar cada número.

El problema es que estoy recibiendo el pedido al revés.

¿Hay alguna forma de revertir un patrón de bits de números antes de hacer mi propio sufijo?

Como en int n tiene un patrón de bits específico, ¿cómo puedo revertir este patrón de bits?

Hay muchas maneras de hacer esto, algunas muy rápido. Tuve que buscarlo.

Invertir bits en un byte

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

Invierta una cantidad de N bits en paralelo en operaciones de 5 * lg (N):

 unsigned int v; // 32-bit word to reverse bit order // swap odd and even bits v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1); // swap consecutive pairs v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2); // swap nibbles ... v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4); // swap bytes v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8); // swap 2-byte long pairs v = ( v >> 16 ) | ( v << 16); 

Invertir bits en la palabra por tabla de búsqueda

 static const unsigned char BitReverseTable256[256] = { # define R2(n) n, n + 2*64, n + 1*64, n + 3*64 # define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16) # define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 ) R6(0), R6(2), R6(1), R6(3) }; 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]]; 

Para obtener más información y referencias, consulte http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel .

Pop bits fuera de su entrada y empujarlos en su salida. Multiplicar y dividir por 2 son las operaciones push y pop. En pseudocódigo:

 reverse_bits(x) { total = 0 repeat n times { total = total * 2 total += x % 2 // modulo operation x = x / 2 } return total } 

Consulte la operación de módulo en Wikipedia si no ha visto este operador.

Otros puntos:

  • ¿Qué pasaría si cambias 2 a 4? ¿O a 10?
  • ¿Cómo afecta esto el valor de n? ¿Qué es n?
  • ¿Cómo podrías usar operadores bitwise ( << , >> , & ) en lugar de divide y módulo? ¿Esto lo haría más rápido?
  • ¿Podríamos usar un algoritmo diferente para hacerlo más rápido? ¿Podrían ayudar las tablas de búsqueda?

Déjame adivinar: tienes un bucle que imprime el bit 0 (n & 1), luego cambia el número a la derecha. En su lugar, escriba un bucle que imprima el bit 31 (n & 0x80000000) y desplace el número a la izquierda. Antes de hacer ese bucle, haga otro bucle que desplace el número hacia la izquierda hasta que el bit 31 sea 1; a menos que hagas eso, obtendrás ceros iniciales.

También es posible revertir. Algo así:

 unsigned int n = 12345; //Source unsigned int m = 0; //Destination int i; for(i=0;i<32;i++) { m |= n&1; m <<= 1; n >>= 1; } 

Lo sé: eso no es exactamente C, pero creo que es una respuesta interesante:

 int reverse(int i) { int output; __asm__( "nextbit:" "rcll $1, %%eax;" "rcrl $1, %%ebx;" "loop nextbit;" : "=b" (output) : "a" (i), "c" (sizeof(i)*8) ); return output; } 

El código de operación rcl coloca el bit desplazado en el indicador de acarreo, luego rcr recupera ese bit en otro registro en el orden inverso.

Mi conjetura es que tienes un entero y estás intentando convertirlo a binario?

Y la “respuesta” es ABCDEFG, pero su “respuesta” es GFEDCBA?

Si es así, volvería a verificar el endian de la máquina en la que lo estás haciendo y de la máquina de la que provino la “respuesta”.

Aquí están las funciones que he usado para revertir bits en un byte y revertir bytes en un quad.

 inline unsigned char reverse(unsigned char b) { return (b&1 << 7) | (b&2 << 5) | (b&4 << 3) | (b&8 << 1) | (b&0x10 >> 1) | (b&0x20 >> 3) | (b&0x40 >> 5) | (b&0x80 >> 7); } inline unsigned long wreverse(unsigned long w) { return ( ( w &0xFF) << 24) | ( ((w>>8) &0xFF) << 16) | ( ((w>>16)&0xFF) << 8) | ( ((w>>24)&0xFF) ); }