Come funziona questo codice per invertire i bit in numero?

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

come funziona?

Answer 1

Supponiamo che io abbia una mano di 8 carte:

7 8 9 10 J Q K A 

Come possiamo invertirli? Un modo è quello di scambiare coppie adiacenti:

8 7 10 9 Q J A K 

gruppi Poi, casse mobili adiacenti di 2: scambio 8 7 e 10 9, ecc:

10 9 8 7 A K Q J 

Infine, gruppi di scambio di quattro, che è metà misura 8:

A K Q J 10 9 8 7 

Fatto.

È possibile farlo in diversi ordini. Perché? Perché gli scambi sono stabili l'uno rispetto all'altro. Quando scambiamo la metà superiore delle carte con la metà inferiore, ad esempio, le coppie rimangono nello stesso ordine. O quando scambiamo le coppie, le metà rimangono nello stesso ordine.

Questo è ciò che il codice sta facendo con le operazioni di bit. Ad esempio per scambiare coppie possiamo utilizzare la maschera 01010101 per scegliere i bit pari e 10101010 di individuare i bit dispari, utilizzando il bit operazione AND:

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

Ricordare, la regola per ed è che dato un certo valore bit X, X & 1 = X e X & 0 = 0. I 1 bit nella maschera mantengono il valore e i 0 bit nella maschera producono 0. Si chiama mascheramento perché assomiglia esattamente a una maschera utilizzata in spray - pittura, ecc. I 1 bit "coprono" i luoghi che non vuoi "verniciare" con zero.

Successivamente, il risultato a sinistra viene spostato a sinistra di un bit e il risultato a destra viene spostato a destra.Ciò comporta lo scambio:

B0D0F0H0  0A0C0E0G 

Finalmente, i due sono combinati con OR logico. La regola per OR è che X o 0 è X. Le due parti hanno ciascuna 0 dove l'altro ha zero, e quindi i bit semplicemente unire:

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

E ora le coppie vengono scambiati.

Answer 2

Lasciate b[0], b[1], b[2], ..., b[31] bit di input a partire dal bit meno significativo. Poi b[1], b[0], b[3], b[2], ..., b[31], b[30] saranno bit

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

Fondamentalmente, scambia bit adiacenti di input. Simili, altre 4 righe scambiano coppie vicine, gruppi di 4, gruppi di 8 e infine gruppi di 16 bit.

Answer 3

Può essere compreso per induzione.

Inizia con il caso base, un numero a due po

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

Ora progredire ad un numero di quattro po

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

Progress ad un numero a 8 bit

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 

e così sopra.

Answer 4

Il codice scambia prima singoli bit adiacenti, quindi coppie di bit adiacenti, e così via, raddoppiando la dimensione dello swap ogni volta finché alla metà si scambiano metà delle dimensioni del numero intero. Lo swapping viene eseguito mascherando i bit da spostare con AND, spostandoli e quindi OR facendo i risultati insieme.

L'animazione di seguito è utile per visualizzare cosa sta succedendo, ricordando che mentre le dimensioni dello scambio aumentano in sequenza, tutti gli scambi di ogni dimensione si verificano in parallelo. metà

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