Lubię bity, czyli jak dodawać, odejmować, mnożyć i dzielić na bitach ;-)

Lubię bity.

Pamiętam, że te lata temu zastanawiało mnie jak komputer liczy.
Początkowo wydawało mi się, że robi to w jakiś głupi sposób, np. że dodawanie to jest inc na jednej liczbie i dec na drugiej i że mamy pętlę aż ta druga będzie 0 (mówimy o liczbach dodatnich tutaj).

Później do mnie dotarło, że tego się tak nie robi, że się da liczyć np. pod kreskę na bitach :-)

Tylko, że zamiast na każdym bicie robić tą operację oddzielnie robi się je na wszystkich jednocześnie ;-)

No bo jak popatrzeć na wyniki dodawania 2 bitów to mamy:

bit 1	bit 2	+	carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Co jest podejrzanie podobne do wyniku z xor ;-) dla tego co mamy w +:

 

bit 1	bit 2	^
0	0	0
0	1	1
1	0	1
1	1	0

oraz do and tego co mamy w carry ;-)

 

bit 1	bit 2	&
0	0	0
0	1	0
1	0	0
1	1	1

No i wiemy, że carry idzie o 1 bit  dalej, czyli trzeba na nim zrobić << :-)

Czyli jak chcemy dodać a do b to wiemy, że będziemy musieli zrobić:

c = a^b które da nam wartość bitów "po dodaniu", ale brakuje nam carry, które to carry mamy z (a&b)<<1 :-)

stąd may:

public int add(int a, int b) {
    while (b!=0) {
        var c = a&b;
        a^=b;
        b=c<<1;
    }
    return a;
}

Teraz jak mamy dodawanie to wystarczy wiedzieć, że odejmowanie to dodawanie liczby o przeciwnym znaku ;-) i tego, że liczba plus jej element odwrotny to 0 ;-)

Wtedy jasne się staje jak są reprezentowane liczby ujemne, czyli jako negacja wszystkich bitów... ale to by było za mało bo wtedy 0 miałoby odwrotność... i 1 + -1 by było wszystkimi zapalonymi bitami ;-) 

Więc jest negacja wszystkich bitów +1 ;-)

Czyli:

-1 = -(0001) = ~(0001)+1 = 1110+0001 = 1111

stąd -1 + 1 = 1111 + 0001 = (1)0000 (gdzie to (1) to carry które jest wyniesione poza liczbę :-)).

Stąd możemy powiedzieć, że odejmowanie b od a to dodanie do a -b ;-)

No i mamy:

public int minus(int b) {
    return add(~b, 1);
}

public int sub(int a, int b) {
    return add(a, minus(b));
}

Btw. a jak rozpoznać, że liczba jest ujemna? ;-)

Tak się fajnie składa, że ma zapalony najwyższy bit ;p

Czyli np. tak:

private int sig(int a) {
    return new int[]{1,-1}[a>>>=31];
}

Ale OK, już umiemy dodawać i odejmować, nawet powiedzieć jaki jest znak liczby, ale może by tak pomnożyć? ;-)

Niby mnożenie to tylko dodawanie.. wystarczy dodać mnożną tyle razy jak mówi mnożnik i mamy wynik... (a, że w komputerze to będzie pętla, to to nawet działa dla ujemnych liczb, ale dziwnie ;-))

No więc: 7*3=7+7+7=21

Ale... 3 to 2 +1, czyli 7*3=7*2+7=21

a 2 i 1 to potęgi dwójki ;-)

A znamy operację shift :-) [użyliśmy jej już w dodawaniu i w wyznaczaniu znaku :-)]

Czyli co by było gdybyśmy zaczęli od liczby 0, i dodali do niej a jeśli bit dla 1 się świeci w b? później przesunęli a o 1 bit w kierunku wyższych liczb (czyli pomnożyli x2), a b o jeden bit w kierunku mniejszych (czyli podzielili przez 2), i znów sprawdzili? ;-)

No to użyjmy tej wiedzy ;-)

public int mul(int a, int b) {
    var sum = 0;
    while (b!=0) {
        if ((b&1)==1) sum=add(sum,a);
        a<<=1;
        b>>>=1;
    }
    return sum;
}

I mamy mnożenie :-) jak widać nawet się nie musimy przejmować znakami... 

W końcu jest czas na dzielenie, to jest najtrudniejsze.

Ale coby było gdyby oszukać? I zamiast dzielić to mnożyć? ;-)

No bo przecież dzielenie to znalezienie liczby, która pomnożona przez dzielnik da dzielną... albo będzie największą liczbą nie większą od dzielnej, która jest wielokrotnością dzielnika.

Czyli musimy znaleźć tylko liczbę, która pomnożona razy dzielnika będzie równa dzielnej, lub będzie jej najbliższa.

Moglibyśmy więc przelecieć od 1 wzwyż, aż wynik mnożenia tej liczby z dzielnikiem będzie większy od dzielnej, wiemy wtedy, że liczba o 1 mniejsza jest wynikiem dzielenia :-)

Ale co będziemy wszystkie bity po drodze zapalać? Pamiętamy z mnożenia, że mnożenie to dodawanie mnożnej * potęga dwójki dla której pali się bit w mnożniku...

Co nam więc szkodzi poszukać największego bitu naszego wyniku dzielenia, który będzie zapalony? ;-)

Zaczniemy od 1 i będziemy je przesuwać w lewo (czyli mnożyć x2) aż będzie większa od dzielnej... wtedy wystarczy przesunąć raz w prawo i mamy najstarszy bit wyniku dzielenia :-)

A jak mamy najstarszy bit... to dodajemy tą liczbę do wyniku, i teraz przesuwamy ten bit znów w prawo (dzielimy przez 2) i sprawdzamy czy suma jest mniejsza lub równa dzielnej... jak jest mniejsza lub równa, znaczy, że ten bit też trzeba zapalić (+ nam to zrobi, ale i or)...

Znaki nam tu trochę przeszkadzają, ale użyjemy magii, że - i + robią -, a + i + oraz - i - robią + (takie odwrotne xor ;-)), i jeśli zrobimy działanie na liczbach dodatnich, ale zapamiętamy znaki z początku to możemy później po prostu zrobić odpowiedni znak.

I nasze dzielenie wygląda tak ;-)

public int div(int a, int b) {
    // c = a/b => a=b*c
    if (b==0) throw new ArithmeticException("Div by 0");
    var sigA = sig(a);
    var sigB = sig(b);
    a=mul(sigA,a);
    b=mul(sigB,b);
    var d = 1;
    while (a>=mul(b,d<<1) && mul(b,d<<1)>0 && (d<<1>0)) {
        d<<=1;
    }
    var c = 0;
    while (d>0) {
        var mul = mul(b, c | d);
        if (a>=mul && mul>0) c|=d;
        d>>>=1;
    }
    c=mul(c,mul(sigA,sigB));
    return c;
}

Jak widać musimy jakoś obsłużyć to, że niestety nie da się dzielić przez 0 ;-)

No co ja zrobię, że lubię bity? :-)

Podobne posty^beta
Potworność ;-) czyli mnożenie w 90 liniach ;-)
2016 będzie rokiem "nietypowym"
32 bity vs. 64 bity, tym razem C++ ;-)
Przesyłanie "obcych" na odległość, albo uniwersalny format danych ;-)
Java 32 bit vs. Java 64 bit