wtorek, 9 lutego 2016

Inwersja bitowa.

 
Niedawno stanąłem przed problemem w jaki sposób ustawić bity w bajcie w odwrotnej kolejności w języku C/C++ to znaczy mając na przykład bajt 10110110 odwrócić go do postaci 01101101. Pokombinowałem i znalazłem metodę. Nie jest ona może elegancka ale skuteczna.

Należy zastosować sekwencję instrukcji:

i=((i&0x0F)<<4)|((i&0xF0)>>4);
i=((i&0x33)<<2)|((i&0xCC)>>2);
i=((i&0x55)<<1)|((i&0xAA)>>1);


Dowód:

Załóżmy że i=10110110. Zauważmy, że: 0x0F=00001111 oraz 0xF0=11110000
wtedy z pierwszej instrukcji mamy:

10110110                       10110110    
00001111 &                   11110000&
------------                   -------------
00000110<<4                  10110000>>4
------------                   -------------
01100000        |            00001011
       
             i=01101011

Wartości 0x33=00100001 oraz 0xCC=11001100. Druga instrukcja da:

01101011                               01101011
    00110011&                          11001100&
------------                           ------------- 
00100011<<2                             01001000>>2
------------                          -------------
                  10001100                                00010010                  
10001100
00010010|
 --------------
10011110

Wartości 0x55=01010101, 0xAA=10101010. Trzecia instrukcja da:

10011110           10011110
01010101&        10101010&
---------------      ----------------
00010100<<1    10001010>>1
---------------      ----------------
00101000           01000101

               00101000
               01000101 |
             -----------------
               01101101

i(rev)=01101101

Brak komentarzy:

Prześlij komentarz