Przesunięcie bitowe

Przesunięcie bitowe – operacja na liczbach w systemie dwójkowym polegająca na przesunięciu wszystkich cyfr binarnych o $n$ 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ę

Przesunięcie logiczne w lewo

Na najmłodszą pozycję dopisywany jest bit o wartości zero, natomiast najstarszy bit jest tracony, np.:

$01101000_2\to 11010000_2$ $(104_{10}\to 208_{10})$

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.:

$10011101_2\to 01001110_2$ $(157_{10}\to 78_{10})$

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.:

$10011100_{U2}\to 11001110_{U2}$ $(-100_{10}\to -50_{10})$

Gdyby zastosować zwykłe przesunięcie bitowe wynikiem byłoby $78_{10}.$

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 $2^n$ jest równoważne przesunięciu w lewo o $n$ pozycji. Z kolei stałą całkowitą można przedstawić jako sumę $2^{n_1}+2^{n_2}+\dots +2^{n_k},$ gdzie $n_i$ to pozycja ustawionego bitu w reprezentacji binarnej liczby. Wykorzystując rozdzielność mnożenia względem dodawania można zapisać $x(2^{n_1}+2^{n_2}+\dots +2^{n_k})=x{2}^{n_1}+x{2}^{n_2}+\dots +x{2}^{n_k}$ – liczba przesunięć jest równa liczbie bitów o wartości 1 w stałej, liczba dodawań o jeden mniejsza.

Np. dla stałej $18_{10}=10010_2=2^1+2^4$ mamy $x\cdot 18=x\cdot (2^1+2^4)=x\cdot 2^1+x\cdot 2^4$ – wyliczenie tej wartości wymaga wykonania dwóch przesunięć bitowych o 1 i 4 miejsca w lewo, oraz jednego dodawania.

Zobacz też

• obrót bitowy