Kawałek Kodu

Na chwilę przenosimy się do podstawówki. Wyjmuj z tornistra zeszyt i coś do pisania. Powtórzymy tabliczkę mnożenia, ale dla tych, którzy mieli z nią kłopoty, mam małe pocieszenie. Nie będziemy powtarzać jej całej, lecz tylko jej fragment. Ale będzie też o dzieleniu...

Po kawałku.

Aby łatwiej zrozumieć zasadę działania mnożenia i dzielenia bitowego (bo to właśnie przesunięcia bitowe), musimy na chwilę wrócić do reprezentacji dwójkowej (binarnej) liczb. Widząc poszczególne kawałeczki zerojedynkowe liczby dziesiętnej, wszystko stanie się jasne. Jako, że taka reprezentacja może zajmować dużo miejsca dla dużych liczb, zajmiemy się tylko liczbami w zakresie 0-255, czyli bajtami. Bajt to 8 bitów.

Weźmy za przykład liczbę 5. Jej postać binarna wygląda tak:

W pierwszym wierszu mamy numerację poszczególnych bitów od najbardziej znaczącego. Jednocześnie numer bitu oznacza, że cyfra w drugim wierszu, jeśli jest jedynką (bit zapalony), to stanowi składnik liczby o wartości 2^^numer_bitu. Czyli w przykładzie mamy bity o wartości 4 oraz 1. Dla bitu numer 4 jedynka będzie oznaczać wartość 16. Warto też zauważyć, że suma zapalonych bitów stojących na lewo od danego bitu, stanowi wartość tego bitu pomniejszoną o 1. Jeśli wspomniany bit ma wartość 16, to suma bitów od 3-0 ma wartość 15 (8+4+2+1).

Bajt (zresztą inne rozmiary również) może reprezentować też liczby ujemne. Przy czym ze względu na to, że najbardziej znaczący bit przeznaczamy na znak liczby (0 liczba dodatnia, 1 liczba ujemna), to wtedy maksymalną wartość może stanowić liczba 7 bitowa, a więc o połowę mniejsza od liczby bez znaku. Dla bajtu maksymalną wartością będzie 127, a minimalną -128. O ile łatwo zrozumiec skąd wzięła się maksymalna wartość, to nie do końca wiadomo jak to jest z tymi ujemnymi liczbami.

Istnieje kilka reprezentacji bitowych liczb ujemnych, ale najpopularniejsza jest reprezentacja z uzupełnieniem do 2 (U2). Bit znaku oprócz swojego przeznaczenia ma wartość -2^^numer_bitu. Czyli w przypadku bajtu będzie mieć wartość -(2^⁷) = -128. Pozostałe bity reprezentują części liczby w standardowy sposób. Np. -123 możemy zapisać jako -128+5, czyli:

A -1 to -128+127, czyli:

Innym sposobem na konwersję jest odjęcie od wartości o 1 większej od maksymalnej beznakowej liczby reprezentowanej przez bajt, szukanej wartości. Oczywiście będzie to wartość dodania, ale jej reprezentacja bitowa będzie odpowiednikiem szukanej wartości ujemnej. Skoro maksymalna wartość bajtu to 255, więc 256-123=133, a 133, to 128 (tu bit znaku) oraz bity 2 i 0 (wartości 4 i 1).

Najważniejszej abyś w przypadku liczb ujemnych zapamiętał to, że znak zapisujemy na najbardziej znaczącym bicie i w przypadku działań artytmetycznych uwzględniających znak liczby, musimy ten bit uwzględniać.

Bezpieczny zakręt w lewo i w prawo.

Skoro już wiesz jak wygląda liczba 5 w postaci binarnej, to zobaczmy jak wygląda pomnożona przez 2 i 8.

5*2=10:

5*8=40:

Nie wiem czy to widzisz, ale skoro 5 w postaci binarnej to 101, to przy mnożeniu przez 2 bity przesunęły się o 1 w lewo, a w przypadku mnożenia przez 8, przesunęły się o 3 w lewo.

Jeśli będzie to liczba ujemna np. -5, to pomnożona przez 2 i 8 powinna dać odpowiednio: -10 oraz - 40. Zobaczmy:

-10:

-40:

Tu wszystko wygląda analogicznie, tj. bity również przesuwają się w lewo. Pamiętając jednak o tym, że minimalna wartość ujemna jaka może być zapisana na bajcie to -128, otrzymamy błąd przy mnożeniu wartości, który wynik przekracza wspomnianą wartość. Tzn. nie stricte błąd, ale stracimy znak i liczba stanie się wartością dodatnią (ale nie tą wynikającą z pomnożenia i usunięcia znaku). Nie wnikajmy, bo nie w tym rzecz. To co dla nas jest ważne, to fakt, że mnożąc liczbę przez wartości o potędze dwójki przesuwamy tak naprawdę jej bity w lewo. W JavaScript odpowiednikiem tej operacji jest operator << (przesunięcie w lewo, czasem zwane arytmetycznym przesunięciem w lewo ze względu na to, że zachowuje znak). Jeśli chcemy uzyskać wyniki -5*8, to możemy zapisać jako:

let a = -5 << 3;

Analogicznie do przesunięcia w lewo istnieje przesunięcie w prawo i będzie odpowiadało operacji... dzielenia! Wystarczy, że przeanalizujesz powyższe przykłady od końca i dostrzesz jak uzyskać wynik 5 dzieląc 40 przez 8. O ile w przypadku przesunięcia w lewo nie istnieje w JavaScript operator beznakowy, to w prawo istnieje zarówno znakowe (>>) jak i bezznakowe (>>>) przesunięcie (czasem zwane odpowiednio: arytmetyczne przesunięcie w prawo i logiczne przesunięcie w prawo). W przypadku znakowego przesunięcia w prawo bit znaku jest kopiowany na miejsce pustego/pustych bitów z lewej strony.

Weźmy za przykład wartość -112:

jej połowa to wartość -56:

a ćwiartka to -28, czyli:

Binarne zakończenie.

Dwie ważne rzeczy. Liczby zmiennoprzecinkowe nie są reprezentowane w postaci binarnej, którą pokazałem wyżej. Operatory przesunięcia bitowego w JS działają na liczbach 32-bitowych, albo znakowych albo bez, niezależnie od "bitowości" procesora czy systemu operacyjnego.

Dwie ciekawostki. Przy dzieleniu liczb dodatnich najmniej znaczący bit wypada z puli, stąd 1/2=0, a nie 0.5. Choć gdyby dodać bity odpowiadające za wartości ułamkowe, tj. 1/2, 1/4, 1/8, itd., to tam by wpadały te bity. Ale jak już wspomniałem tej postaci nie używa się dla wartośc zmiennoprzecinkowych, lecz tylko dla liczb całkowitych. Przy dzieleniu liczb ujemnych najmniejszą wartością będzie -1, a nie 0. Wynik to z zasady, że bitu znaku propaguje się na dziurę po przesuwanych w prawo bitach, tak więc w przypadku bajtu zawsze otrzymamy 8 zapalonych bitów, co odpowiada właśnie wartości -1.

Podsumowując, to co nam jest potrzebne na przyszłość, to dwie tabele:

Skąd w ogóle pomysł na ten wpis? Są dwa powody. Po pierwsze już w kilku artykułach używałem tych operatorów i postanowiłem napisać o nich jeszcze raz, trochę szerzej. Po drugiej będziemy ich jeszcze używać właśnie w zastępstwie standardowego mnożenia i dzielenia w kolejnych wpisach. A to dlatego, że jest to po prostu szybsze, bo w każdym języku programowania są (a przynajmniej powinny być) kompilowane lub interpretowane do postaci odpowiednich operacji języka maszynowego (właśnie operacji przesunięć bitowych).

Po szkole widzimy się w nastepnym wpisie! Do przeczytania!

Przydatne linki:
Operatory przesunięć bitowych.
Operatory przesunięć bitowych według ECMAScript 5.
Typowo męska logika, czyli fraktal Sierpińskiego (przykład użycia operatora przesunięcia bitowego).
The Fast & The Canvas, czyli szybki dostęp do pikseli na Canvas (drugi przykład użycia).