Obrót bitowy

Z Wikipedii

Obrót bitowy lub przesunięcie cykliczne — działanie na słowach bitowych polegająca na zmianie pozycji wszystkich bitów, w taki sposób, że bit o indeksie i po wykonaniu obrotu o n miejsc znajduje się na pozycji (i + n)mod k, gdzie k to liczba bitów w danym słowie. Ze względu na znak n rozróżnia się obroty w lewo (n > 0) i w prawo (n < 0).

Przykład obrotu dla słowa 8-bitowego o 3 miejsca w lewo:

  7   6   5   4   3   2   1   0   ← indeksy
+---+---+---+---+---+---+---+---+
| a | b | c | d | e | f | g | h | przed obrotem
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| d | e | f | g | h | a | b | c | po obrocie
+---+---+---+---+---+---+---+---+
  4   3   2   1   0   7   6   5   ← indeksy przed obrotem

Obroty bitowe są implementowane w wielu procesorach; niektóre pozwalają także na wykonywanie obrotów przez znacznik przeniesienia (jedną z flag ALU), tj. rozszerzenie słowa o ten bit i dopiero wówczas wykonywany jest obrót bitowy:

 CF       7   6   5   4   3   2   1   0   ←  indeksy
+---+   +---+---+---+---+---+---+---+---+
| X |   | a | b | c | d | e | f | g | h | przed obrotem
+---+   +---+---+---+---+---+---+---+---+
        
+---+   +---+---+---+---+---+---+---+---+
| c |   | d | e | f | g | h | X | a | b | po obrocie
+---+   +---+---+---+---+---+---+---+---+
  5       4   3   2   1   0  CF   7   6   ← indeksy przed obrotem

Np. w mikroprocesorach serii x86 istnieją instrukcje ROL oraz ROR wykonujące — odpowiednio — obrót w lewo i prawo, natomiast RCL/RCR wykonują obrót w lewo/prawo przez znacznik przeniesienia.

W popularnych językach programowania nie istnieją operatory, które wprost umożliwiałyby takie działanie. Mogą być jednak łatwo zrealizowane za pomocą dwóch przesunięć bitowych i jednej operacji sumy bitowej. Np. w języku C obrót w lewo 8-bitowego słowa można wykonać następująco:

y = (x << n) | (x >> (8-n));