JS - bitwise add vol. 4

Już teraz chyba uda nam się napisać operację dodawania za pomocą operatorów bitowych. Jeszcze raz przeróbmy poprzednie lekcje i zastanówmy się jak ma to wyglądać!

Ok, dodamy sobie dwie liczby wyszczególniając w pamięci oraz cyfrę:

w pamięci |  1  |  1  |  -  |  -  |
x         |  0  |  0  |  1  |  1  | (3)
y         |  0  |  1  |  1  |  0  | (6)
--------------------------------------
suma      |  1  |  0  |  0  |  1  | (9)

Jak widać :

1 + 0, cyfra 0, w pamięci 0
1 + 1, cyfra 0, w pamięci 1
1 + 0 i 1 w pamięci – cyfra 0, 1 w pamięci
0 + 0 i 1 w pamięci – cyfra 1, 0 w pamięci
0 w pamięci bo 0 & 0 << 1 daje 0, wyjście z pętli

Lepiej tego wyjaśnić nie potrafię. Możemy jeszcze przejść się po kodzie:

function bitwiseAddNumbers(x, y){
    while(y !== 0){
        let carry = x & y;
        x = x ^ y;
        y = carry << 1;
    }

    return x;
}

console.log(bitwiseAddNumbers(4, 4));//8
console.log(bitwiseAddNumbers(5, 3));//8
console.log(bitwiseAddNumbers(3, 2));//5

Wygląda to tak:

Jak y to zero to zwróć x (ma to sens, 2 + 0 to 2)
Wylicz w pamięci – tylko 1 & 1 daje 1 w pamięci
Wylicz pod x wartość z dodania cyfr – 1 ^ 1 da 0, 0 ^ 0 da 0, 0 ^ 1 da 1
Wylicz następny y, czyli:
- Jeżeli 1 + 1, to (1 & 1) << 1 daje 2, wartość się zgadza tego co w pamięci
- Jeżeli gdzieś mamy już 0, to 0 & 0 << 1 daje 0 i wychodzimy z pętli
- Algorytm tak sprytnie zaplanowany, że pod x mamy wyliczoną wartość i jeśli to, co w pamięci, zostało, to też jest dodane

Dodajmy 5 + 5 i sprawdźmy, czy rozumiemy:

To po prostu trzeba sobie na spokojnie analizować aż zrozumiemy…

Jeszcze raz, teraz na pełnych liczbach nie cyfrach, co 5 + 5 oznacza względem naszego algorytmu:

5 + 5

x = 5, y = 5

algorytm:

tak długo jak y !== 0
      carry - x & y
       x    - x ^ y
       y    - carry << 1

wykonanie dla 5 + 5

sprawdź, czy y !== 0 - nie jest, y to 5

carry - 5 & 5
0 1 0 1
0 1 0 1 &
-------
0 1 0 1 (5) <-- carry

x - 5 ^ 5
0 1 0 1
0 1 0 1 ^
--------
0 0 0 0 (0) <--- x

y = carry << 1

0 1 0 1 << 1
--------
1 0 1 0 (10)

sprawdź warunek
y !== 0
10 !== 0 - prawda

carry - 0 & 10 (0)
x - 0 ^ 10 (10)
y - 0 << 1 (0)

koniec pętli, zwróć x (10)

Tak to działa.

JS – bitwise add vol. 4