O kodzie uzupełnień do dwóch w Javie raz jeszcze

W Kod uzupełnień do dwóch w Javie (reprezentacja binarna liczb całkowitych) zaprezentowałem moją dotychczasową wiedzę na temat reprezentacji binarnej liczb całkowitych w Javie. Uważam to za mój początek w dokładniejszym rozpoznaniu tematu i nie ukrywam, że wciągnął mnie. Przypomnę tylko, że zaczęło się od zmian w Javie 7 z Fork/Join (nowe podejście do współbieżności w Javie z konstrukcjami wyższego poziomu), aby przez operator przesunięcia w prawo bez znaku >>> przejść do kodu uzupełnień do dwóch dla liczb całkowitych w Javie. Właśnie takie przejścia z jednego tematu na drugi w krótkim czasie lubię najbardziej. Nie pozwalają człowiekowi na dłuższy bezruch.

Przez ostatni tydzień dalej zgłębiałem temat i przesiedziałem sporo czasu czytając różnej maści artykuły. O większości pisałem na swoim kanale @jaceklaskowski na twitterze, więc wielu już miało przedsmak tego, o czym teraz będę pisał.

Prawie.

Liczby całkowite w Javie

Specyfikacja The Java Language Specification, Third Edition w rozdziale 4.2.1 Integral Types and Values wymienia typy całkowite z ich zakresami. W kolejności ich długości wyróżniamy: byte na 8 bitach, short na 16 bitach, int na 32 bitach i najdłuższy long na 64 bitach. Jest jeszcze całkowite char, które reprezentowane jest na 16 bitach, z tą różnicą, w porównaniu do poprzednich, że bez bitu znaku (najstarszy bit, pierwszy od lewej strony, albo ostatni z prawej).

I już przy omawianiu dostępnych typów dostrzec można ich różną reprezentację wewnętrzną - byte, short, int i long są z bitem znaku, w przeciwieństwie do char, któremu dano wszystkie dostępne bity do dyspozycji.

Dodawanie i liczba przeciwna w kodzie uzupełnień do dwóch

W artykule na Wikipedii Two's complement trafiłem na zdanie, które wywarło na mnie niesamowite wrażenie i sprawiło, że zrozumiałem sens istnienia tego systemu kodowania. Uważam, że mogłoby stanowić świetne wprowadzenie dla całego artykułu, albo jedyne:

"Two's complement numbers is a way to encode negative numbers into ordinary binary, such that addition still works."

Tylko o jakie dodawanie chodzi?!

Właśnie o zwykłe dodawanie binarne się rozchodzi. Jak mogłem się zorientować przeszukując materiały w Sieci, istnieje wiele systemów reprezentowania liczb całkowitych, ale czy to podwójne zero, czy konieczność rozróżniania znaku dodawanych liczb, sprawiają, że kod uzupełnienia do dwóch wydaje się być najbardziej trafnym. I taki zastosowano w Javie.

W Signed Int: Two's Complement mogłem dalej zgłębiać niuanse kodu uzupełnień do dwóch, który od tej pory będę zapisywał jako 2C (od angielskiego two's complement). Tam dowiedziałem się, że w 2C występuje jedno zero i dodawanie jest spójne dla reprezentacji bitowej z i bez znaku korzystając ze sprzętowej realizacji dodawania bitów (bez względu, czy reprezentują liczbę ze znakiem, czy bez - obie reprezentacje sprowadzane są do reprezentacji bez znaku). Ta cecha 2C jest związana z działaniem sprzętowym dodawania, a tutaj moja wiedza kończy się niezwykle szybko i na tym poprzestanę. I czuję, że więcej nie jest mi potrzebne o maszynowych rozwiązaniach.

Zadanie dla dociekliwych: wykonaj bitowe dodawanie liczb całkowitych, np. 1 i 2.

Najdłuższa liczba całkowita - typu long - ma do dyspozycji 64 bity. Pierwszy bit zarezerwowany jest dla bitu znaku (poza char).

Do uzyskania liczby ujemnej w 2C mamy 3 różne sposoby, z których najczęściej brany jest ten, który polega na odwróceniu wszystkich bitów i dodaniu jedynki, tj. -B = ~B + 1, przy założeniu, że B to dowolna liczba całkowita.

Zadanie dla dociekliwych: znajdź liczbę przeciwną do 1 korzystając z powyższego algorytmu.

I właśnie w tym momencie dociera do mnie jak interesującym jest rozpoznawanie tematu reprezentacji 2C. Dodaj 1 do liczby, której reprezentacja bitowa zawiera wyłącznie 1ki (czyli -1).

1111 1111 1111 1111 1111 1111 1111 1111     // -1
+ 0000 0000 0000 0000 0000 0000 0000 0001     //  1
-------------------------------------------------------------------
 10000 0000 0000 0000 0000 0000 0000 0000     //  0 (na 33 bitach = przepełnienie!)

Obie liczby są typu int. Obie mają do dyspozycji 32 bity z ostatnim bitem (licząc od lewej) zarezerwowanym na znak. Wynik również musi mieścić się w 32 bitach, ale cóż to?! Dodawanie 1 i -1 kończy się przepełnieniem - wynik wymusza 33 bity. W Javie taka sytuacja jest ukrywana przez usunięcie dodatkowego 33 bitu, aby w ten sposób otrzymać liczbę 32-bitową, która składa się wyłącznie z samych 0, a to po prostu 0 w systemie dziesiętnym. Jakież to piękne!

Idąc dalej, możnaby zastanowić się, co stanie się przy wyznaczaniu liczby przeciwnej dwukrotnie? Czy zachodzi zasada wyznaczania liczby przeciwnej podwójnie, która powinna wyznaczyć liczbę początkową, czyli -(-x) = x, w 2C?

Krok 1. Reprezentacja liczby całkowitej w postaci 32 bitów (dla int) lub 64 bitów (dla long). Ja pozostanę przy 32 bitach.

int n0 = 1111 1111 1111 1111 1111 1111 1111 1111 // -1

Krok 2. Odwracamy wszystkie bity

int n1 = 0000 0000 0000 0000 0000 0000 0000 0000 // 0

Krok 3. Dodajemy jedynkę

int n2 = 0000 0000 0000 0000 0000 0000 0000 0001 // 1

Zakończyłem pierwsze wyliczenie liczby przeciwnej do zadanej, czyli -1. Czy kontynuując odwracanie wyliczę wyjściową, czyli -1?

Krok 4 Reprezentacja bitowa liczby 1

int n00 = 0000 0000 0000 0000 0000 0000 0000 0001 // 1

Krok 5 Odwrócenie bitów

int n10 = 1111 1111 1111 1111 1111 1111 1111 1110 // nieistotne

Krok 6 Dodajemy jedynkę

int n20 = 1111 1111 1111 1111 1111 1111 1111 1111 // -1

I jak łatwo zauważyć n20 == n0, czyli parzyste wykonanie wyznaczania liczby odwrotnej do zadanej zawsze zwróci liczbę początkową.

Z Why computers represent signed integers using two’s complement tylko upewniłem się, że 2C jest warte poświęconego czasu i jego zrozumienie uważam od tej pory za obowiązkowe (ja już mam za sobą, więc tym łatwiej jest mi rzucać takie stwierdzenia :)).

"The representation of signed integers is the representation used by modern processors. It is called "two's complement" because to negate an integer, you subtract it from 2N. For example, to get the representation of –2 in 3-bit arithmetic, you can compute 8 – 2 = 6, and so –2 is represented in two’s complement as 6 in binary: 110."

W tym zdaniu znajduje się kolejny sposób na wyznaczanie liczb przeciwnych w 2C. Po prostu odejmujemy liczbę dodanią od 2^N, czyli dla 32 bitowych liczb typu int będzie to 1 + 32 zera w binarnej reprezentacji (wyznaczenie, a co ważniejsze, zapamiętanie tej liczby stanowi nie lada wyzwanie umysłowe, więc pozostańmy przy takim opisie).

Z Kod uzupełnień do dwóch w Javie (reprezentacja binarna liczb całkowitych) wiemy, że mnożenie

package pl.japila.java7;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import org.junit.Test;

public class TwoCDemo {

    @Test
    public void test() {

        long oneAnd32Zeros = (long)1 << 32; // 0x1_FFFF_FFFF - int overflow!
        int three = 3;  // 0b11
       
        int minusThree = (int)(oneAnd32Zeros - three);
       
        assertThat(minusThree, is(-3));
    }

}

Jako podsumowanie, warto zwrócić uwagę na użycie operatora przesunięcia w lewo, aby uzyskać liczbę podwójnie większą od największej w zakresie int. Nie chciałem pisać tej liczby dziesiętnie, a (czego nie wiedziałem wcześniej) jej reprezentacja w notacji bitowej (z 0b), ósemkowej (z wiodącym 0), albo szesnastkowo (z 0x) nie jest możliwa - są one zarezerwowane wyłącznie dla typów int i mniejszych.