Operatory bitowe nie takie straszne

W dzisiejszym wpisie poruszymy temat operatorów bitowych w JavaScript, których często wielu początkujących programistów unika jak ognia. Operatory te można jednak ciekawie wykorzystać w prostych, praktycznych przykładach.

Nie będziemy w tym artykule omawiać złożonych procesów realizowanych w systemie binarnym, lecz skupimy się na kwestiach podstawowych.

Generalnie w języku JavaScript liczby całkowite reprezentowane są jako 32 bitowe ze znakiem, przy czym programista nie ma bezpośredniego dostępu do 31-go bitu (bity liczone są od zera).

Podstawy systemy dwójkowego

Ponieważ jest to blog poświęcony podstawom JavaScript to zaczniemy od ogólnego omówienia systemu dwójkowego w JavaScript. Ograniczymy się jednak w tej chwili wyłącznie do liczb całkowitych, gdyż analiza liczb zmiennoprzecinkowych jest nieco bardziej złożonym zagadnieniem i wymagałoby to m.in. omówienia standardu IEEE 754 i rozkładu liczby binarnej na fragmenty.

Na początek weźmy liczbę 25. W JavaScript istnieje metoda Number.prototype.toString(n), gdzie n to podstawa w jakiej ma zostać zaprezentowana liczba (domyślnie jest to podstawa 10 czyli system dziesiętny).

Spróbujmy zatem zobaczyć, jak wygląda liczba 25 w zapisie dwójkowym:

(25).toString(2); //'11001'

Co ten zapis oznacza? Otóż nic innego jak kolejne potęgi liczby dwa mnożone przez zero lub jeden.

Należy pamiętać o ważnej zasadzie, że bity liczymy od strony prawej do lewej. Bit zerowy to bit skrajnie na prawo i oznacza liczbę dwa (czyli podstawę systemu) podniesioną do potęgi zerowej (czyli „1”) mnożoną przez bit zero lub jeden.

Uważny czytelnik zwróci w tym miejscu uwagę, że przecież mówiłem, że w JavaScript liczby reprezentowane są jako 32 bitowe, a my otrzymaliśmy tylko pięć bitów. Taki wynik wywołania metody toString() jest związany z celowym „odcinaniem” z liczby części wypełnienia (lub uzupełnienia), czyli w uproszczeniu można powiedzieć, że zawsze otrzymamy reprezentację liczby jako string, zaczynający się od „1”. Pamiętajmy, że na razie poruszamy się w zakresie liczb dodatnich, dla których bit 31 (oznaczający znak) jest równy zero, więc prawidłowo jest on „ucinany”. Słowa ucinany czy odcinany piszę w cudzysłowie, gdyż jest to bardzo duże uproszczenie i odnosi się wyłącznie do kwestii przedstawienia postaci binarnej liczby. Nadal liczba 25 jest przechowywana jest w zapisie pełnym, 32 bitowym.

Kolorem czerwonym zaznaczyłem bit 31 oznaczający „kod” znaku, czyli zero dla liczb dodatnich i jeden dla liczb ujemnych (choć nie do końca jest to prawidłowe stwierdzenie).

Na niebiesko zaznaczono część postaci binarnej, zwróconej metodą toString(2), natomiast na zielono oznaczono tzw. wypełnienie, które nie jest zwracane w wynikowej wartości typu string. Łącznie mamy zatem 32 bity (liczone od zera!).

No dobrze, a co z całkowitymi liczbami ujemnymi?

Omówiliśmy kwestie najważniejsze i jednocześnie najprostsze, czyli sposób konwersji liczby dziesiętnej do jej postaci binarnej i odwrotnie. Przyjrzyjmy się jednak teraz liczbą ujemnym. W tym przypadku istnieje pewna rozbieżność między tym jak faktycznie liczba jest przechowywana w systemie binarnym, a jej reprezentacją binarną zwracaną przez metodę toString().

Na początek spróbujmy zobaczyć, co zwróci nam metoda toString wywołana na ujemnej liczbie -25:

//Wartość ujemna:
(-25).toString(2); //'-11001'

//Wartość dodatnia:
(25).toString(2); //'11001'

Początkujący programista może w tym momencie stwierdzić, że wszystko jest w porządku i wartość z minusem jest jak najbardziej oczekiwana. W praktyce jednak metoda toString() wywołana na liczbie ujemnej nie operuje bezpośrednio na jej postaci binarnej, lecz na wartości bezwzględnej i dla niej zwraca reprezentację dwójkową, poprzedzając wartość wynikową znakiem minusa.

Przeanalizujmy zatem dokładnie jak tak na prawdę przechowywane są liczby ujemne w systemie dwójkowym przez co wyjaśni się to co napisałem przed chwilą (pamiętaj jednak, że cały czas operujemy wyłącznie na liczbach całkowitych!).

Obecnie najbardziej popularnym sposobem zapisu liczb całkowitych w systemie binarnym jest U2 („kod uzupełnień do dwóch”). Zamiana liczby dodatniej na ujemną odbywa się w trzech krokach:

  1. Konwersja wartości bezwzględnej z liczby dziesiętnej N do jej postaci binarnej.
  2. Negacja bitowa, czyli odwrócenie poszczególnych bitów (zera przechodzą w jedynki, a jedynki przechodzą w zera) – w JavaScript istnieje bitowy operator NOT (tylda „~”) realizujący takie zadanie.
  3. Do otrzymanej postaci po negacji należy dodać binarnie jedynkę.

Zwróćmy uwagę na bit 31 (skrajny lewy). W liczbie dodatniej ma on wartość zero, co oznacza, że przy zamianie na postać dziesiętną wartość 2^31 mnożymy przez zero. Jeśli liczba jest wartością ujemną, to pierwszy bit dostaje wartość jeden (w kroku 2 gdy następuje bitowa negacja), więc 2^31 mnożymy przez 1 lecz dodatkowo wartość tę uwzględniamy jako ujemną (z minusem). Oznacza to, że w praktyce przy konwersji ujemnej liczby binarnej do postaci dziesiętnej do liczby -(2^31) dodajemy kolejne, następne potęgi dwójki mnożone przez jeden lub zero. W rezultacie otrzymujemy właśnie liczbę -25.

Powróćmy jednak do naszego przykładu:

//Wartość ujemna:
(-25).toString(2); //'-11001'

//Wartość dodatnia:
(25).toString(2); //'11001'

Teoretycznie, na podstawie tego co napisałem wcześniej o systemie U2 powinnyśmy otrzymać:

(-25).toString(2) === '11111111111111111111111111100111'; //false

Otrzymujemy jednak postać identyczną jak dla liczby dodatniej (+25) z dodatkowym znakiem minusa z przodu. Dzieje się tak dlatego, że w JavaScript jeśli wywołamy metodę Number.prototype.toString(2) na wartości ujemnej, to w pierwszej kolejności liczba zamieniana jest na jej wartość bezwzględną (nasz krok 1), lecz następnie zamiast dalszej procedury U2 zwracana jest po prostu wartość binarna liczby dodatniej z dodatkowym znakiem myślnika.

Jeśli z jakiś względów potrzebujemy rzeczywistej reprezentacji ujemnej wartości binarnej w systemie U2 to łatwo możemy posłużyć się operatorem „>>>” czyli tzw. przesunięciem bitowym ze znakiem, co omówimy dokładniej w dalszej części artykułu.

(-25).toString(2); //'-11001'
(-25 >>> 0).toString(2);'11111111111111111111111111100111'

Operator bitowy OR

w JavaScript mamy do dyspozycji siedem operatorów bitowych. Zaczniemy od jednego z najprostszych operatorów, a mianowicie operator OR, oznaczanego jako pojedynczy znak „|”.  Analizuje on postać binarną dwóch wartości i zwraca jedynkę, jeśli na danej pozycji bitowej w którejkolwiek z liczb znajduje się jedynka. W przeciwnym razie dla danej pozycji zwraca zero.

Stosując operatory bitowe należy jednak pamiętać, że zawsze odnoszą się one do postaci binarnej, a nie dziesiętnej liczb! Na przykład zapis 5|10 zwróci wartość 15, co początkowo może być zaskakujące, tym bardziej, że 5|0 zwróci wartość 5. Przeanalizujmy więc dokładniej co się dzieje w czasie „pracy” operatora 5|10:

(5).toString(2); //'101'
(10).toString(2); //'1010'

Stosując operator bitowy OR należy szczególnie uważać, aby przypadkowo nie zastosować go w miejsce operatora „||” oznaczającego alternatywę logiczną w JavaScript, co stosuje się np. przy deklarowaniu zmiennych:

var x = 1 | 5; //Zwróci 5
var y = 1 || 5 //Zwróci 1

Osobiście zalecam jednak unikanie tego typu deklarowania zmiennych, np. w celu stworzenia domyślnych parametrów dla argumentów funkcji. Lepszym rozwiązaniem jest np. jawne przyrównanie wartości zmiennej to wartości undefined.

Operator bitowy AND

Operator and, oznaczany jako pojedynczy znak „&” zwraca jedynkę tylko wtedy, gdy w obu analizowanych wartościach na danej pozycji bitowej znajdują się jedynki. Każda inna sytuacja powoduje zwrócenia bitu zerowego.

Operator ten można w ciekawy sposób wykorzystać w praktyce. Załóżmy na przykład, że chcemy sprawdzić, czy liczba N jest liczbą nieparzystą i zwrócić wartość true lub false (dla liczby parzystej). Najczęściej spotykanym sposobem rozwiązania tego problemu jest sprawdzanie podzielności przez 2:

const odd = n => n%2 !== 0

odd(3); //true
odd(4); //false

Zadanie to można jednak wykonać również z użyciem operatora bitowego AND:

const odd = n => !!(n&1)

odd(3); //true
odd(7); //true
odd(4); //false

Zastosowaliśmy tutaj podwójny wykrzyknik aby jawnie przekonwertować uzyskaną wartość do true/false. Jak zaraz zobaczymy, wyrażenie n&1 zawsze zwróci tylko jedną z dwóch wartości: zero albo jeden.

Kolejny ciekawy przykład wykorzystania operatora AND to sprawdzenie, czy liczba N jest potęgą liczby 2.

const pow2 = n => !(n&(n-1));

pow2(8); //true
pow2(10); //false
pow2(5); //false

Na początek sprawdźmy co się dzieje w momencie przekazania jako parametru funkcji wartości 8. Następuje wtedy wywołanie 8&7:

Dla liczby 8 uzyskujemy w wyniku operacji AND wartość zero, co jest w JavaScript konwertowane do false, dlatego musimy odwrócić wynik logiczny poprzez zastosowanie pojedynczego znaku „!”. W efekcie dla liczby 8 uzyskujemy zwrotnie wartość true.

Analogicznie dla wartości 5 wywołujemy zwrócenie wartości wyrażenia 5&4, które zwraca jedynką, co w JavaScript konwerowane jest na true. Ponownie więc odwracamy wynik logiczny uzyskując zwrotną wartość false.

Operator bitowy NOT

Operator bitowy NOT jest jednym z moich ulubionych operatorów, który często można wykorzystać w zastosowaniach praktycznych. Operator ten odnosi się do jednej wartości i powoduje odwrócenie wszystkich jej bitów, łącznie z bitem 31 związanym ze znakiem liczby.

Widzimy zatem, że dla wartości „1” w wyniku bitowej negacji (NOT) uzyskujemy wartość „-2”. Istnieje również nieco inny opis zachowania operatora NOT wyrażony w zapisie liczb dziesiętnych:

//~x === -(x+1)

~1;    // -(1+1) = -2
~(-2); // -(-2+1) = -(-1) = 1 

~~1;   //1
~~3.5; //3

Jeśli dokładnie przeanalizujemy powyższe przykłady to zauważysz, że zastosowanie podwójnego operatora negacji NOT można porównać do funkcji zwracającej część całkowitą z liczby, czyli np. do metody Math.trunc, Math.floor (zaokrąglenie w dół, czyli de facto pominięcie części ułamkowej) czy parseInt(n,10). Jest to jednak prawdą tylko w zakresie liczb dodatnich. W przypadku liczb ujemnych sprawa nieco się komplikuje, lecz nie będziemy tutaj już tego omawiać. Osobiście jeśli mam pewność, że poruszam się wyłącznie w zakresie liczb dodatnich to wolę stosować „~~” jako skróconą formę metody Math.floor. Mimo, iż de facto uzyskujemy w tym momencie identyczne wyniki to tak na prawdę operator NOT oraz metoda floor() działają w różny sposób.

Drugim praktycznym zastosowaniem operatora negacji jest problem przeszukiwania ciągów znakowych metodą indexOf, lastIndexOf czy search. Jak wiemy metody te w przypadku braku dopasowania (czyli nie znalezienia szukanego ciągu) zwracają wartość „-1”. Najczęściej stosowana jest więc forma zapisu z przyrównaniem do wartości „-1”:

if ('text'.indexOf('t') !== -1) {
    //wykonaj operacje gdy znaleziono
    //'t' w ciągu znakowym 'text'
}

Jest to zapis całkowicie poprawny i co więcej, zalecany przez praktycznie większość poradników, książek, kursów itp. Można to jednak skrócić do bardziej zwięzłej i moim zdaniem bardziej eleganckiej formy:

if (~'text'.indexOf('t') {
    //wykonaj operacje gdy znaleziono
    //'t' w ciągu znakowym 'text'
}

Zastosowaliśmy tutaj znak tyldy, czyli bitowy operator negacji NOT. Przeanalizujmy co się dzieje, gdy wyszukujemy różne znaki w analizowanym ciągu ‚text’:

//indexOf() zwraca pozycję wystąpienia szukanego znaku
~'text'.indexOf('t'); // -(0+1) = -1, czyli TRUE
~'text'.indexOf('e'); //-(1+1) = -2, czyli TRUE
~'text'.indexOf('b'); //-(-1+1) = -0, czyli FALSE

Stosując metody indexOf, lastIndexOf czy search zawsze musimy pamiętać, że szukany znak może wystąpić na początku analizowanego ciągu i metoda zwróci wartość zero. Jeśli w żaden sposób nie obsłużymy tej wartości, np. operatorem NOT lub przyrównaniem  „!== -1” to zero zostanie niejawnie przekonwertowane do false co nie jest wynikiem oczekiwanym.

Operator NOT zabezpiecza nas przed tym problemem, gdyż wyłącznie dla braku dopasowania, czyli wartości „-1” zwróci wynikowo wartość zero (false). W każdej innej sytuacji zwróci liczbę ujemną, co zawsze zostanie niejawnie przekonwertowane do true (z liczb jedynie -0 i +0 konwertowane są do false).

Operatory przesunięcia bitowego w lewo i w prawo bez zmiany znaku

Operatory bitowe „>>” i „<<” powodują przesunięcie o zadaną ilość bitów w lewą lub prawą stronę. Brakujące bity po przesunięciu wypełniane są zerami. w większości przypadków aplikacji JavaScript raczej nie korzysta się z tych operatorów bitowych. Spróbujmy jednak zobaczyć jak one działają na dwóch przykładach.

Zaczniemy od przesunięcia bitowego w lewo. Przeanalizuj dokładnie poniższy rysunek, a powinieneś zauważyć pewną zależność, mianowicie przesunięcie bitowe w lewo „<<” o jeden bit jest tożsame z pomnożeniem wartości dziesiętnej liczby przez dwa.

(7 << 1) === (7 * 2); //true

Programiści języków niskopoziomowych częściej korzystają z operacji bitowych, gdyż są one znacznie szybsze. W JavaScript najczęściej jednak tego typu działania wykonujemy małą ilość razy więc nie odczujemy różnicy w szybkości działania operatora „<<” i tradycyjnego operatora mnożenia „*”.

Spójrzmy więc jeszcze na operator przesunięcia bitowego w prawo:

W tym wypadku przesunięcie bitowe o jeden bit odpowiada działaniu dzielenia liczby N przez dwa:

(12 >> 1) === (12 / 2); //true

Operatory przesunięcia w lewo i w prawo można także wykorzystać jako zamiennik metody parseInt(10) czy Math.trunc. Wynika to z faktu, że operatory bitowe działają na części całkowitej liczby, więc przy zastosowaniu przesunięcia bitowego o zerową ilość bitów dokonamy w pewnym sensie po prostu operacji N * 1.

(5.6) >> 0; //5
(5.6) << 0; //5

Przesunięcie bitowe w prawo z możliwą zmianą znaku

Istnieje odmiana operatora przesunięcia oznaczana przez trzy znaki: „>>>”. Generalnie działa ona podobnie jak operator „>>” z tymże brakujące bity wypełnia nie zerami, lecz bitami odpowiadającymi bitowi 31, czyli bitowi, który określa znak liczby.

W przypadku liczb dodatnich uzyskamy identyczny wynik zarówno przy użyciu operatora „>>” jak i „>>>”:

12 >> 1;  //6
12 >>> 1; //6

Inaczej jednak jest w przypadku liczb ujemnych. W tym wypadku bit 31 ma wartość „1”, a więc brakujące bity po przesunięciu zostaną wypełnione jedynkami. Operator „>>>” wykorzystałem już raz w tym artykule przy omawianiu rzeczywistego zapisu binarnego liczb ujemnych (system U2).

Operator ten można łatwo wykorzystać aby uzyskać rzeczywistą binarną reprezentację liczby ujemnej, gdyż jak już pisałem, samo wywołanie metody toString(2) na liczbie ujemnej i tak zwróci jej reprezentację jak dla liczby dodatniej, gdyż metoda toString(2) tak na prawdę operuje na wartości bezwzględnej z liczby N.

Problem ten można rozwiązać stosując następujący zapis:

(12).toString(2); //'1100'
(-12).toString(2); //'-1100'

(-12 >>> 0).toString(2); //'11111111111111111111111111110100'

W praktyce przy programowaniu aplikacji JavaScript raczej rzadko potrzebna jest rzeczywista reprezentacja binarna liczby ujemnej zgodnej z systemem U2. Warto jednak znać tę „sztuczkę” aby w razie potrzeby móc łatwo zwrócić ciąg, reprezentujący liczbę binarną ze znakiem ujemnym, o czym świadczy jedynka na bicie 31.

Operator bitowy XOR

Na koniec zostawiłem jeszcze jeden operator bitowy, a mianowicie operator XOR. Jest to w pewnym sensie odmiana operatora OR. Różnica polega na tym, że OR zwraca true gdy jeden z operandów lub oba jednocześnie spełniają dany warunek, natomiast operator XOR zwróci prawdę tylko wtedy, gdy albo jeden albo drugi spełnia warunek. Gdy oba operandy jednocześnie mają wartość zero lub jeden to operator XOR zwróci false (natomiast OR zwróciłby w tym wypadku true).

Dłuższe zapisy ciągów operatorów XOR należy grupować od lewej do prawej, dlatego w naszym przykładzie najpierw realizowane jest działanie 5^5 co daje wartość zero, a następnie ta wartość jest porównywana z liczbą 3, czyli 0^3 co w efekcie zwraca wartość 3.

Jeśli chcesz dokładniej zrozumieć i poćwiczyć zasadę działania operatora XOR to możesz spróbować krok po kroku udowodnić poniższe wyniki:

5 ^ 5 ^ 3 ^ 3; //0
5 ^ 2 ^ 5 ^ 3 ^ 3; //2

Na koniec jeszcze jednak ciekawostka, związana z zamianą wartości dwóch zmiennych, co można wykonać na co najmniej trzy sposoby:

var a = 5, b = 10;

//Metoda 1 - wymaga dodatkowej zmiennej
var t = a;
a = b;
b = t;

//Przywracamy nasze zmienne:
a = 5; b = 10;

//Metoda 2 - operator XOR bez dodatkowej zmiennej
a ^= b; //a = 15
b ^= a; //b = 5
a ^= b; //a = 10

//Przywracamy nasze zmienne:
a = 5; b = 10;

//Metoda 3 - destrukturyzacja
[a,b] = [b,a]; //a = 10, b = 5

Osobiście polecam metodę trzecią, gdyż jest ona najbardziej zwięzła. Destrukturyzacja została jednak wprowadzona do składni języka dopiero w standardzie ECMA Script 6, więc jeśli chcesz uruchamiać swój kod w starszych środowiskach to musisz zastosować transpilator (np. Babel) lub pozostać przy metodzie 1 lub 2.

I to byłoby na tyle jeśli chodzi o podstawowe wg mnie zagadnienia związane z operatorami bitowymi w JavaScript. Pamiętaj jednak, że wszystko o czym tutaj mówimy dotyczy operacji na liczbach całkowitych. Analiza operacji binarnych liczb zmiennoprzecinkowych to temat na oddzielny, równie długi (jeśli nie dłuższy) artykuł, który myślę, że również omówię w najbliższej przyszłości.