Przesunięcie bitowe


Przesunięcie bitowe w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Przesunięcie bitowe – operacja na liczbach w systemie dwójkowym polegająca na przesunięciu wszystkich cyfr binarnych o n {\displaystyle 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 Pascalushr (przesunięcie w prawo), shl (przesunięcie w lewo).

Spis treści

Przesunięcia o jedną pozycję | edytuj kod

W lewo | edytuj kod

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

01101000 2 11010000 2 {\displaystyle 01101000_{2}\to 11010000_{2}} ( 104 10 208 10 ) {\displaystyle (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 potęgę dwójki.

W prawo | edytuj kod

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

10011101 2 01001110 2 {\displaystyle 10011101_{2}\to 01001110_{2}} ( 157 10 78 10 ) {\displaystyle (157_{10}\to 78_{10})}

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

Przesunięcie arytmetyczne w prawo | 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 U 2 11001110 U 2 {\displaystyle 10011100_{U2}\to 11001110_{U2}} ( 100 10 50 10 ) {\displaystyle (-100_{10}\to -50_{10})}

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

Wykorzystanie przesunięcia bitowego w lewo do mnożenia przez stałe | 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 {\displaystyle 2^{n}} jest równoważne przesunięciu w lewo o n {\displaystyle n} pozycji. Z kolei stałą całkowitą można przedstawić jako sumę 2 n 1 + 2 n 2 + + 2 n k , {\displaystyle 2^{n_{1}}+2^{n_{2}}+\ldots +2^{n_{k}},} gdzie n i {\displaystyle 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 + + 2 n k ) = x 2 n 1 + x 2 n 2 + + x 2 n k {\displaystyle 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 {\displaystyle 18_{10}=10010_{2}=2^{1}+2^{4}} mamy x 18 = x ( 2 1 + 2 4 ) = x 2 1 + x 2 4 {\displaystyle 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 kod

Na podstawie artykułu: "Przesunięcie bitowe" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy