Kod uzupełnień do dwóch w Javie (reprezentacja binarna liczb całkowitych)

Wszystko zaczęło się od mojego przedstawienia zmian w Javie 7, w pakiecie java.util.concurrent podczas 84 spotkania Warszawa JUG - Warszawski Eclipse DemoCamp 2011 - Java 7, JavaFX i Eclipse (prezentacja do pobrania jako JacekLaskowski-EclipseDemoCamp2011-ConcurrencyUtilitiesJava7-2011.11.08.pdf).

Wtedy zaczęła się moja przygoda ze szkieletem Fork/Join. Rozwiązywanie problemu przez zrównoleglanie jego mniejszych składowych wymaga właściwego sposobu podziału (zwykle po połowie) i tak do ustalonego, minimalnego poziomu jego złożoności, a właściwie braku, po którym rozwiązanie można obliczyć "siłowo" (element po elemencie, liniowo).

Kwestią, z którym zwykle zmagają się programiści korzystający z Fork/Join (czy dowolnego problemu rozwiązywanego przez algorytmy typu "dziel i zwycieżaj") to, w jaki sposób dzielić, aby samo dzielenie nie było na tyle skomplikowane, że zysk ze zrównoleglenia zostanie przez niego skonsumowany i ostatecznie wyjdziemy na przysłowiowe "zero".

I tu pojawia się przyczynek do tego wpisu - operator przesunięcia bez znaku w prawo >>> (ang. unsigned right shift) w Javie.

Nie jest to niczym odkrywczym w Javie 7, ale przy Fork/Join nabrał większego znaczenia. Mówiąc wprost, ja na niego zwróciłem uwagę właśnie przy Fork/Join. I tak kończy się w zasadzie rola Fork/Join, które nie będzie już przywoływane, bo posłużył wyłącznie jako tło do rozpoznania operatora przesunięcia i jak się później okazało reprezentacji liczb całkowitych w Javie.

Weźmy następujący problem: W jaki sposób wyznaczyć połowę pewnej liczby nieujemnej x?

Liczba dowolna, acz ustalona, x (teraz dopiero dojrzałem, aby dostrzec piękno tych słów) może być liczbą elementów w tablicy, w którym znajdują się elementy do przetworzenia.

Operator przesunięcia w prawo bez znaku >>> jest złożeniem << i >> w zależności od znaku lewego argumentu - dodatni to >>, a ujemny...cóż...tu sprawa się komplikuje i wygląda (n>>s)+(2<<~s) przy założeniu, że rozważamy n>>>s.

Pamiętam, kiedy dostrzegłem (a właściwie pokazano mi palcem), że n << 1 to po prostu n * 2. Innych zastosowań przesunięcia w lewo jeszcze nie odkryłem, ale pewnie są równie zabójcze dla mojego serca :)

Wtedy zacząłem zgłębiać reprezentację liczb całkowitych w Javie, bo w końcu działanie tych operatorów polega na przesunięciach binarnych.

Zadanie wprowadzające: Czy znasz zapis binarny ujemnej liczby całkowitej w Javie? Niech to będzie -1 lub Integer.MIN_VALUE.

Właśnie wtedy zreflektowałem się, jak niewiele wiem na ten temat. Niewiele?! Delikatnie powiedziane. Nic nie wiem! Zabrałem się za lekturę specyfikacji języka Java (tutaj niewiele znalazłem poza ogólnikami), aby skończyć na pojęciach reprezentacjach liczb ze znakiem i bez oraz kod uzupełnień do dwóch (ang. two's complement).

I tak od rozpoznawania Fork/Join przeszedłem do operatora przesunięcia, aby skończyć na reprezentacji liczb całkowitych w Javie.

W ten sposób powstała moja implementacja zamiany binarnego ciągu znaków (bez wiodącego 0b, które doszło w Javie 7) do postaci liczby całkowitej w zapisie dziesiętnym. Klasa nie jest krótka, ale starałem się dobierać nazwy do ich przeznaczenia, więc sądzę, że stosunkowo łatwo będzie zorientować się, co miałem na myśli.

Przede mną analiza kodów źródłowych java.lang.Integer, która dostarcza większości z poniższych metod. Niedługo więcej w temacie, bo nie czuję, abym go wyczerpał (a mam wrażenie, że jedynie zdrapałem wierzchnią warstwę). Oczekuję uwag i wskazówek od życzliwego czytelnika (w czasie świąt niegodnym nie podzielić się miłym słówkiem).

Gdybyśmy już się nie widzieli, życzę najlepszego z okazji nadchodzących Świąt Bożego Narodzenia. Baw się i świętuj, aby wypoczęty wrócić do dalszych prac poznawczych.

package pl.japila.java7;

public class BinaryToDecimalIntDemo {

    static final char ZERO = '0';
    static final char ONE = '1';

    public static void main(String[] args) {
        for (int number = Integer.MIN_VALUE; number <= Integer.MIN_VALUE + 0xFFFF; number++) {
            String negativeNumber = Integer.toBinaryString(number);
            int intInDecimal = BinaryToDecimalIntDemo.getIntInDecimal(negativeNumber);
            assert number == intInDecimal;
        }
        for (int number = Integer.MAX_VALUE; number >= Integer.MAX_VALUE - 0xFFFF; number--) {
            String negativeNumber = Integer.toBinaryString(number);
            int intInDecimal = BinaryToDecimalIntDemo.getIntInDecimal(negativeNumber);
            assert number == intInDecimal;
        }
    }

    static int getIntInDecimal(String binary) {
        int sum = 0;
        boolean negative = false;
        char[] bits = binary.toCharArray();
        if (bits.length == Integer.SIZE) {
            if (isNegative(bits)) {
                negative = true;
                bits = subtractOne(invertBits(removeSignBit(bits)));
            }
        }
        for (int i = bits.length - 1, j = 0; i >= 0; i--, j++) {
            sum += calculateValueInBinaryRepAt(j, bits[i]);
        }
        return negative ? (sum == 0 ? Integer.MIN_VALUE : -sum) : sum;
    }

    private static char[] subtractOne(final char[] bits) {
        char[] newBits = new char[bits.length];
        System.arraycopy(bits, 0, newBits, 0, newBits.length);
        int i = newBits.length - 1;
        if (newBits[i] == ONE) {
            newBits[i] = ZERO;
        } else {
            newBits[i] = ONE;
            for (int j = i - 1; j >= 0; j--) {
                if (newBits[j] == ZERO) {
                    newBits[j] = ONE;
                } else {
                    newBits[j] = ZERO;
                    break;
                }
            }
        }
        return newBits;
    }

    private static char[] invertBits(char[] bits) {
        char[] newBits = new char[bits.length];
        System.arraycopy(bits, 0, newBits, 0, newBits.length);
        for (int i = 0; i < newBits.length; i++) {
            newBits[i] = (newBits[i] == ZERO ? ONE : ZERO);
        }
        return newBits;
    }

    private static char[] removeSignBit(char[] bits) {
        char[] newBits = new char[bits.length - 1];
        System.arraycopy(bits, 1, newBits, 0, newBits.length);
        return newBits;
    }

    private static boolean isNegative(char[] bits) {
        return bits.length == Integer.SIZE && bits[0] == ONE;
    }

    private static double calculateValueInBinaryRepAt(int i, char c) {
        return Math.pow(2, i) * Character.getNumericValue(c);
    }

}