Przesunięcie bitowe: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
m MalarzBOT: likwiduję Błędy składniowe: Przestarzałe znaczniki HTML |
|||
(Nie pokazano 4 wersji utworzonych przez 3 użytkowników) | |||
Linia 4: | Linia 4: | ||
W różnych [[język programowania|językach programowania]] istnieją funkcje bądź [[Operator (programowanie)|operatory]], realizujące przesunięcie: |
W różnych [[język programowania|językach programowania]] istnieją funkcje bądź [[Operator (programowanie)|operatory]], realizujące przesunięcie: |
||
* w [[C (język programowania)|C]]/[[C++]], [[PHP]], [[Java|Javie]], [[Python]]ie – < |
* w [[C (język programowania)|C]]/[[C++]], [[PHP]], [[Java|Javie]], [[Python]]ie – <code>>></code> (przesunięcie w prawo), <code><<</code> (przesunięcie w lewo); |
||
* w [[Pascal (język programowania)|Pascalu]] – < |
* w [[Pascal (język programowania)|Pascalu]] – <code>shr</code> (przesunięcie w prawo), <code>shl</code> (przesunięcie w lewo). |
||
== Przesunięcia o jedną pozycję == |
== Przesunięcia o jedną pozycję == |
||
[[Plik:Bit shift.svg| |
[[Plik:Bit shift.svg|400px|right]] |
||
=== |
=== Przesunięcie logiczne w lewo === |
||
Na najmłodszą pozycję dopisywany jest bit o wartości zero, natomiast najstarszy bit '''jest tracony''', np.: |
Na najmłodszą pozycję dopisywany jest bit o wartości zero, natomiast najstarszy bit '''jest tracony''', np.: |
||
: <math>01101000_2 \to 11010000_2</math> <math>(104_{10} \to 208_{10})</math> |
: <math>01101000_2 \to 11010000_2</math> <math>(104_{10} \to 208_{10})</math> |
||
Wartość liczby w naturalnym kodzie binarnym jest 2 razy większa. Większe przesunięcia są równoważne przemnożeniu przez [[potęga dwójki| |
Wartość liczby w naturalnym kodzie binarnym jest 2 razy większa. Większe przesunięcia są równoważne przemnożeniu przez kolejne [[potęga dwójki|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.: |
Na najstarszą pozycję dopisywany jest bit o wartości zero, natomiast najmłodszy bit '''jest tracony''', np.: |
||
: <math>10011101_2 \to 01001110_2</math> <math>(157_{10} \to 78_{10})</math> |
: <math>10011101_2 \to 01001110_2</math> <math>(157_{10} \to 78_{10})</math> |
||
Linia 29: | Linia 29: | ||
== Wykorzystanie przesunięcia bitowego w lewo do mnożenia przez stałe == |
== Wykorzystanie przesunięcia bitowego w lewo do mnożenia przez stałe == |
||
Mnożenie przez pewną określoną [[Liczby naturalne|liczbę naturalną]] można zastąpić ciągiem operacji przesunięć bitowych w lewo i dodawania. Jest to powszechnie wykorzystywane (także w [[kompilator]]ach) 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 pewną określoną [[Liczby naturalne|liczbę naturalną]] można zastąpić ciągiem operacji przesunięć bitowych w lewo i dodawania. Jest to powszechnie wykorzystywane (także w [[kompilator]]ach) 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 <math>2^n</math> jest równoważne przesunięciu w lewo o <math>n</math> pozycji. Z kolei stałą całkowitą można przedstawić jako sumę <math>2^{n_1} + 2^{n_2} + \ldots + 2^{n_k},</math> gdzie <math>n_i</math> to pozycja ustawionego bitu w reprezentacji binarnej liczby. Wykorzystując rozdzielność mnożenia względem dodawania można zapisać <math>x(2^{n_1} + 2^{n_2} + \ldots + 2^{n_k}) = x2^{n_1} + x2^{n_2} + \ldots + x2^{n_k}</math> – liczba przesunięć jest równa liczbie bitów o wartości 1 w stałej, liczba dodawań o jeden mniejsza. |
Mnożenie przez <math>2^n</math> jest równoważne przesunięciu w lewo o <math>n</math> pozycji. Z kolei stałą całkowitą można przedstawić jako sumę <math>2^{n_1} + 2^{n_2} + \ldots + 2^{n_k},</math> gdzie <math>n_i</math> to pozycja ustawionego bitu w reprezentacji binarnej liczby. Wykorzystując [[Rozdzielność działania|rozdzielność]] mnożenia względem dodawania można zapisać <math>x(2^{n_1} + 2^{n_2} + \ldots + 2^{n_k}) = x2^{n_1} + x2^{n_2} + \ldots + x2^{n_k}</math> – liczba przesunięć jest równa liczbie bitów o wartości 1 w stałej, liczba dodawań o jeden mniejsza. |
||
Np. dla stałej <math>18_{10} = 10010_2 = 2^1 + 2^4</math> mamy <math>x \cdot 18 = x \cdot (2^1 + 2^4) = x \cdot 2^1 + x \cdot 2^4</math> – wyliczenie tej wartości wymaga wykonania dwóch przesunięć bitowych o 1 i 4 miejsca w lewo, oraz jednego dodawania. |
Np. dla stałej <math>18_{10} = 10010_2 = 2^1 + 2^4</math> mamy <math>x \cdot 18 = x \cdot (2^1 + 2^4) = x \cdot 2^1 + x \cdot 2^4</math> – wyliczenie tej wartości wymaga wykonania dwóch przesunięć bitowych o 1 i 4 miejsca w lewo, oraz jednego dodawania. |
Wersja z 23:12, 13 cze 2024
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ę
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.