Przesunięcie bitowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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ę[edytuj | edytuj kod]

Bit shift.svg

W lewo[edytuj | edytuj kod]

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

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

Wartość liczby w naturalnym kodzie binarnym jest 2 razy większa. Większe przesunięcia są równoważne przemnożeniu przez potęgę dwójki.

W prawo[edytuj | edytuj kod]

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

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

Wartość liczby w naturalnym kodzie binarnym jest 2 razy mniejsza (dzielenie całkowitoliczbowe).

Przesunięcie arytmetyczne w prawo[edytuj | edytuj kod]

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} \rightarrow 11001110_{U2} (-100_{10} \rightarrow -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[edytuj | edytuj kod]

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} + \ldots + 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} + \ldots + 2^{n_k}) = x2^{n_1} + x2^{n_2} + \ldots + x2^{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ż[edytuj | edytuj kod]