- Kod uzupełnień do dwóch w Javie (reprezentacja binarna liczb całkowitych)
- O kodzie uzupełnień do dwóch w Javie raz jeszcze
Dla przypomnienia:
& (AND) zwraca 1, wyłącznie jeśli oba bity są 1.
^ (XOR) zwraca 0, jeśli oba bity są jednocześnie 0 lub 1.
| (OR) zwraca 0, wyłącznie jeśli oba bity są 0.
Kolejność działań: &, ^, |
Wstępniak
Java definiuje 3 operatory przesunięcia - w lewo ze znakiem <<, w prawo ze znakiem >> i w prawo bez znaku >>>. Wszystkie działają wyłącznie na typach całkowitych long (64 bity) lub int (32 bity) i typ lewego argumentu wyznacza typ prawego. W przypadku węższych typów - short, byte, char - są one promowane do int i to po obu stronach niezależnie.Jeśli typem lewego argumentu jest int, jedynie 5 najmłodszych bitów jest branych pod uwagę. Dlaczego? Taka jest długość bitowej reprezentacji int, tzn. 5 bitów pozwala na określenie zakresu przesunięcia od 0 do 31 włącznie, a tylko takie ma sens w przypadku 32 bitowej reprezentacji liczby całkowitej. W myśl tej zasady prawy argument jest zawsze pomniejszany przez zastosowanie operatora logicznego AND z maską 0x1F (0b11111), aby nie wyjść poza zakres [0, 31].
Jeśli jednak typem lewego argumentu jest long, wtedy jedynie 6 najmłodszych bitów jest branych pod uwagę. Ponownie, tylko tyle bitów - 2^6 - służy do reprezentacji bitowej dowolnej liczby long. Tym razem stosujemy logiczny AND z maską 0x3F (= 0b111111) i przesunięcie jest wykonane w zakresie 0 do 63 włącznie.
Lewy argument typu long nie wymusza promocji argumentu prawego do long, gdyż i tak int jest wystarczający, aby określić zakres przesunięcia [0-63] (przez zastosowanie maski 0x3F).
35 00000000 00000000 00000000 00100011
31 -> 0x1f 00000000 00000000 00000000 00011111
& -----------------------------------
00000000 00000000 00000000 00000011 -> 3
-29 11111111 11111111 11111111 11100011
31 -> 0x1f 00000000 00000000 00000000 00011111
& -----------------------------------
00000000 00000000 00000000 00000011 -> 3
Interesujący wydał mi się ten drugi przykład, gdzie prawy operand -29 daje ostatecznie przesunięcie 3 bitów (!) Z takim pytaniem na egzaminie znajomości Javy można łatwo polec.Operator lewego przesunięcia ze znakiem <<
Działanie n << s to przesunięcie s bitów w n z uwzględnieniem bitu znaku, czyli zakres działania to 31 bitów dla lewego operandu typu int lub 63 dla long (odpowiednio maskowane jak opisałem wyżej). Nowe bity po prawej, które pojawią się przy przesunięciu, są wypełniane zerami.Przesunięcie w lewo ze znakiem jest równoważne iloczynowi lewego operandu przez 2 do potęgi s, tj. n * 2^s.
Przykład: 11 << 3 = 11 * 2^3 = 11 * 8 = 88
11 (binarnie) 0000 0000 0000 0000 0000 0000 0000 1011 przesunięcie o 3 0000 0000 0000 0000 0000 0000 0101 1000 wynik: 88 (dziesiętnie)Podobnie z liczbami ujemnymi.
Operator prawego przesunięcia ze znakiem >>
Działanie n >> s to przesunięcie s bitów w n z uwzględnieniem bitu znaku, czyli zakres działania to 31 bitów dla lewego operandu typu int lub 63 dla long (odpowiednio maskowane). Przy przesunięciu w prawo ze znakiem "wypełniaczem" miejsc pustych jest najważniejszy bit - bit znaku, tj. 0 dla dodatnich i 1 dla ujemnych.Dla liczb nieujemnych, przesunięcie w prawo ze znakiem jest równoważne z obliczeniem ilorazu (bez reszty) lewego operandu przez 2 do potęgi s, tj. n / 2^s.
Przykład: 11 >> 3 = 11 / 2^3 = 11 / 8 = 1
11 (binarnie) 0000 0000 0000 0000 0000 0000 0000 1011 przesunięcie o 3 0000 0000 0000 0000 0000 0000 0000 0001 wynik: 1 (dziesiętnie)Przykład: -17 >> 3 = -3
-17 (binarnie) 1111 1111 1111 1111 1111 1111 1110 1111 przesunięcie o 3 1111 1111 1111 1111 1111 1111 1111 1101 wynik: -3 (dziesiętnie)
Operator prawego przesunięcia bez znaku >>>
Działanie n >>> s to przesunięcie s bitów w n wliczając bit znaku (bit znaku traci swoją wyjątkowość i jest traktowany jak każdy inny bit).Z przesunięciem bez znaku "wypełniaczem" staje się 0, co może zamazać bit znaku i zmienić znak wyniku, który zawsze będzie dodatni.
Próbując wyrazić działanie >>> wzorem stosuje się następującą zasadę - jeśli lewy operand jest dodatni, wtedy wynik jest identyczny z prawym przesunięciem ze znakiem. Jeśli jednak lewy operand jest ujemy, wtedy wynik równa się (n >> s) + (2 << ~s). I właśnie ten wzór mnie zmroził najbardziej. Aż mnie do tej pory ciarki przechodzą :)
Przykład: 11 >>> 3 = 11 >> 3 = 11 / 2^3 = 1
11 (binarnie) 0000 0000 0000 0000 0000 0000 0000 1011 przesunięcie o 3 0000 0000 0000 0000 0000 0000 0000 0001 wynik: 1 (dziesiętnie)Przykład: -17 >>> 3 = 536870909
-17 (binarnie) 1111 1111 1111 1111 1111 1111 1110 1111 przesunięcie o 3 0001 1111 1111 1111 1111 1111 1111 1101 wynik: 536870909 (dziesiętnie)
Zastosowanie przesunięć
Operatory ze znakiem to odpowiednio mnożenie i dzielenie lewego operanda przez s-tą potęgę dwójki.Tylko skąd pomysł na >>>?! Na pewno nie zamierzam zapamiętać wzoru na wynik (chociaż przy przeglądaniu Sieci i spisywaniu wiedzy już zagnieździło się w głowie). Musi być tego jakieś sensowne uzasadnienie.
Dopiero w The Unsigned Right Shift olśniło mnie, kiedy trafiłem na możliwe zastosowanie operatora prawego przesunięcia bez znaku "shifting bits that does not represent a numeric value, e.g. pixel-based values and graphics."
I uzupełniając, w Bit twiddling in Java: The Unsigned Right Shift Operator:
Mimo, że każdy ciąg bitów o długości mniejszej niż 64 (najdłuższy typ w Javie - long) reprezentuje pewną liczbę całkowitą, to jedynie przesunięcia ze znakiem szanują reprezentację ciągu w postaci liczby - zachowują znak, a on ma znaczenie przy liczbach. W przypadku przesunięcia w prawo bez znaku >>> reprezentacja liczbowa nie ma znaczenia, a jedynie ciąg bitów - właśnie przez brak dbałości o znak liczby.
Innymi słowy, główne zastosowanie prawego przesunięcia bez znaku to sterowniki urządzeń, niskopoziomowa obsługa grafiki i formatów graficznych, pakiety komunikacyjne, kryptografia. W mojej karierze z Javą nigdy jednak nie spotkałem się z takimi zadaniami, ani chociażby minimalnego użycia operatorów przesunięcia. Zdają się być zbyt magiczne, aby miały zastosowanie nad chociażby java.lang.Math.pow(double, double). Mówi się również, że maksymalna liczba możliwych pytań z operatorów przesunięć na egzaminie z SCJP nie przekracza...jednego (!)
Zagadka: Jaki będzie wynik dowolnego przesunięcia liczby 0xFFFFFFFF (8 znaków F, tj. 32 jedynki) dla operatorów prawego przesunięcia ze znakiem?
W artykule Bitwise operation znalazłem bardzo intrygujące zachowanie przesunięć.
Zacznijmy od zagadki: Jaki będzie wynik odpowiednich przesunięć - (-12 >> 2) << 2, (-12 << 2) >> 2, (-12 >>> 2) << 2, (-12 << 2) >>> 2?
UWAGA: Przesunięcia typów mniej pojemnych, które będą rozszerzane do int - do 32 bitów, np. 8-bitowy byte rozszerzany jest do 32 bitowego int, więc przesunięcie >>> może nie mieć żadnego wpływu i należy maskować liczbę przed przesunięciem, np. (b & 0xFF) >>> 2.
Przesunięcie w prawo zawsze skutkuje "wypadaniem" liczb poza koniec (jakby wpadały w przepaść i były tracone na zawsze).
W The SCJP Tip Line Bit Shifting by Corey McGlone trafiłem na ciekawą zagadkę, która wynika bezpośrednio z powyższych reguł przesunięcia liczb całkowitych (szczególnie maskowaniem prawego operandu).
Zagadka: Jaki będzie wynik 3 >>> 32?
Na odpowiedź masz jedynie sekundę :)
Pamiętasz maskowanie prawego operandu przed wykonaniem przesunięcia? Dla int będzie to maska 0x1F, czyli 32. Czy teraz łatwiej odpowiedzieć na powyższe pytanie? To jaki będzie wynik?
Wystarczy zastosować mod 32 i masz gotową odpowiedź.
3 >>> 32 = 3 >>> (32 % 32) = 3 >>> 0 = 3
Fajne, co?! Właśnie takie cuda w Javie i w ogóle w językach programowania nakręcają mnie na dalsze ich zgłębianie. Czego i Tobie życzę w Nowym Roku 2012! :)
Brak komentarzy:
Prześlij komentarz