¿Cómo funciona este código para invertir bits en número?

Question

unsigned reverse_bits(unsigned input) 
{ 
    //works on 32-bit machine 
    input = (input & 0x55555555) << 1 | (input & 0xAAAAAAAA) >> 1; 
    input = (input & 0x33333333) << 2 | (input & 0xCCCCCCCC) >> 2; 
    input = (input & 0x0F0F0F0F) << 4 | (input & 0xF0F0F0F0) >> 4; 
    input = (input & 0x00FF00FF) << 8 | (input & 0xFF00FF00) >> 8; 
    input = (input & 0x0000FFFF) << 16 | (input & 0xFFFF0000) >> 16; 

     return input; 
} 

cómo funciona esto?

Answer 1

Supongamos que tengo una mano de 8 cartas:

7 8 9 10 J Q K A 

¿Cómo podemos revertir? Una manera es cambiar pares adyacentes:

8 7 10 9 Q J A K 

grupos Entonces, intercambio adyacentes de 2: intercambio 8 7 y 10 9, etc:

10 9 8 7 A K Q J 

Finalmente, grupos de intercambio de cuatro, que es la mitad de la tamaño de 8:

A K Q J 10 9 8 7 

Listo.

Puede hacer esto en diferentes órdenes. ¿Por qué? Porque los intercambios son estables entre sí. Cuando intercambiamos la mitad superior de las tarjetas con la mitad inferior, por ejemplo, las parejas permanecen en el mismo orden. O cuando intercambiamos pares, las mitades permanecen en el mismo orden.

Esto es lo que el código está haciendo con las operaciones de bits. Por ejemplo para intercambiar pares podemos usar la máscara 01010101 de seleccionar los bits pares, y 10101010 de seleccionar los bits impares, utilizando el bit a bit y funcionamiento:

ABCDEFGH  ABCDEFGH 
& 01010101 & 10101010 
---------- ---------- 
= 0B0D0F0H  A0C0E0G0 

Recuerde, la regla para y es la que da cierta valor de bit X, X & 1 = X y X & 0 = 0. Los 1 bits en la máscara conservan el valor, y los 0 bits en la máscara producen 0. Esto se denomina enmascaramiento porque se ve exactamente como una máscara utilizada en aerosol -pintura, etc. Los 1 bits "cubren" los lugares que no desea "pintar" con cero.

A continuación, el resultado de la izquierda se desplaza un bit a la izquierda y el resultado de la derecha se desplaza a la derecha.Esto provoca el cambio:

B0D0F0H0  0A0C0E0G 

Finalmente, los dos se combinan con OR lógico. La regla para O es que X o 0 es X. Las dos partes tienen cada uno 0, donde el otro tiene distinto de cero, y así los bits simplemente Merge:

B0D0F0H0 
| 0A0C0E0G 
---------- 
= BADCFEHG 

Y ahora se intercambian los pares.

Answer 2

Deje b[0], b[1], b[2], ..., b[31] son bits de input a partir del bit menos significativo. Entonces b[1], b[0], b[3], b[2], ..., b[31], b[30] habrá trozos de

input = (input & 0x55555555) << 1 | (input & 0xAAAAAAAA) >> 1; 

Básicamente, se intercambia bits de vecinos de input. Similarmente, otras 4 líneas intercambian pares vecinos, grupos de 4, grupos de 8 y finalmente grupos de 16 bits.

Answer 3

Se puede entender por inducción.

Start con el caso base, un número de dos bits

input = (input & 0x1) << 1 | (input & 0x2) >> 1; 

Ahora progresar a un número de cuatro bits

input = (input & 0x5) << 1 | (input & 0xA) >> 1; // swap bits 
input = (input & 0x3) << 2 | (input & 0xc) >> 2; // swap bit pairs 

Progreso a un número de 8 bits

input = (input & 0x55) << 1 | (input & 0xAA) >> 1; // swap bits 
input = (input & 0x33) << 2 | (input & 0xCC) >> 2; // swap bit pairs 
input = (input & 0x0F) << 4 | (input & 0xF0) >> 4; // swap bit nibbles 

y así en.

Answer 4

El código intercambia primero los bits individuales adyacentes, entonces los pares adyacentes de bits, y así sucesivamente, duplicando el tamaño de la permuta cada vez hasta trozos mitad del tamaño del entero se intercambian al final. El intercambio se realiza enmascarando los bits que se van a mover con AND, desplazándolos y luego OR 'a los resultados juntos.

La siguiente animación es útil para visualizar lo que está sucediendo, recordando que mientras los tamaños de intercambio se incrementan secuencialmente, todos los intercambios en cada tamaño ocurren en paralelo. mitades

Answer 5

unsigned reverse_bits(unsigned input) 
{ 
    //works on 32-bit machine 
    input = (input & 0x55555555) << 1 | (input & 0xAAAAAAAA) >> 1; 
    input = (input & 0x33333333) << 2 | (input & 0xCCCCCCCC) >> 2; 
    input = (input & 0x0F0F0F0F) << 4 | (input & 0xF0F0F0F0) >> 4; 
    input = (input & 0x00FF00FF) << 8 | (input & 0xFF00FF00) >> 8; 
    input = (input & 0x0000FFFF) << 16 | (input & 0xFFFF0000) >> 16; 
    printf("\nvalue = %x",input); 
    return input; 
} 

int _tmain() 
{ 
    // TODO: Please replace the sample code below with your own. 

    int value; 
    signed int res,bit; 
    signed int stPos, len; 
    value = 0x12345678; 

    reverse_bits(value); 
    printf("\nvalue = %x",value); 
    char buffer [33]; 
    itoa (value,buffer,2); 
    printf ("\nbinary: %s\n",buffer); 

    return 0; 
}