Przesunięcie bitowe
Przesunięcie bitowe – operacja na liczbach w systemie dwójkowym polegająca na przesunięciu wszystkich cyfr binarnych o pozycji w lewo lub prawo. Jest to działanie powszechnie stosowane w elektronice i informatyce. Najczęściej przesunięcie wykorzystuje się do szybkiego mnożenia/dzielenia przez liczbę 2 i jej potęgi oraz do sekwencyjnego testowania wartości poszczególnych bitów.
W cyfrowych układach elektronicznych przesunięcie bitowe realizowane jest przez rejestry przesuwające.
W różnych językach programowania istnieją funkcje bądź operatory, realizujące przesunięcie:
- w C/C++, PHP, Javie, Pythonie –
>>
(przesunięcie w prawo),<<
(przesunięcie w lewo); - w Pascalu –
shr
(przesunięcie w prawo),shl
(przesunięcie w lewo).
Przesunięcia o jedną pozycję
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/63/Bit_shift.svg/400px-Bit_shift.svg.png)
Przesunięcie logiczne w lewo
Na najmłodszą pozycję dopisywany jest bit o wartości zero, natomiast najstarszy bit jest tracony, np.:
Wartość liczby w naturalnym kodzie binarnym jest 2 razy większa. Większe przesunięcia są równoważne przemnożeniu przez kolejne potęgi dwójki.
Przesunięcie logiczne w prawo
Na najstarszą pozycję dopisywany jest bit o wartości zero, natomiast najmłodszy bit jest tracony, np.:
Wartość liczby w naturalnym kodzie binarnym jest 2 razy mniejsza (dzielenie całkowitoliczbowe).
Przesunięcie arytmetyczne w prawo
Używane dla liczb zapisanych w powszechnie stosowanym kodzie uzupełnień do dwóch (U2). Bit z najstarszej pozycji jest powielany, natomiast najmłodszy bit jest tracony, np.:
Gdyby zastosować zwykłe przesunięcie bitowe wynikiem byłoby
Wykorzystanie przesunięcia bitowego w lewo do mnożenia przez stałe
Mnożenie przez pewną określoną liczbę naturalną można zastąpić ciągiem operacji przesunięć bitowych w lewo i dodawania. Jest to powszechnie wykorzystywane (także w kompilatorach) przy tworzeniu oprogramowania dla mikroprocesorów nie posiadających jednostki mnożącej, bądź wykonujących mnożenie wolniej niż przesunięcia.
Mnożenie przez jest równoważne przesunięciu w lewo o pozycji. Z kolei stałą całkowitą można przedstawić jako sumę gdzie to pozycja ustawionego bitu w reprezentacji binarnej liczby. Wykorzystując rozdzielność mnożenia względem dodawania można zapisać – liczba przesunięć jest równa liczbie bitów o wartości 1 w stałej, liczba dodawań o jeden mniejsza.
Np. dla stałej mamy – wyliczenie tej wartości wymaga wykonania dwóch przesunięć bitowych o 1 i 4 miejsca w lewo, oraz jednego dodawania.