JS – bitwise swap

Uczymy się zamieniać zmienne wartościami wykorzystując tylko i wyłącznie operatory binarne. Do dzieła.

Oto przykład z poprzedniej lekcji, jak zamienialiśmy matematycznie:

let a = 8;
let b = 3;

a = a + b;
b = a - b;
a = a - b;

console.log(a, b);
//3, 8

Wystarczy zamienić operator dodawania oraz odejmowania na XOR:

let a = 8;
let b = 3;

a = a ^ b;
b = a ^ b;
a = a ^ b;

console.log(a, b);
//3 8

Żeby było jasne – XOR nie dokonuje odejmowania ani dodawania. Natomiast sam algorytm działa w podobny sposób, to jest wykonując te wszystkie kroki, koniec końców zmienne zamieniają się wartościami.

Zobaczmy jak to działa:

a = 8
b = 3

a = 8 ^ 3 

1 0 0 0 
0 0 1 1 
------- ^
1 0 1 1 (11)

a = 11

b = 11 ^  3

1 0 1 1
0 0 1 1 
------- ^
1 0 0 0 (8)

b = 8

a = 11 ^ 8

1 0 1 1
1 0 0 0 
------- ^
0 0 1 1 (3)

a = 3
b = 8

Jeszcze raz – xor nie wykonuje ani dodawania ani odejmowania. On w tym algorytmie zastępuje oba operatory i ten algorytm tak działa, że wykonując te kroki dostaniemy zmienne z zamienionymi liczbami, co możemy przeanalizować powyżej.

8 ^ 3 oraz 8 + 3 dają 11, ale jest to przypadkowa koincydencja. Zobaczmy na 5 i 4:

0 1 0 1
0 1 0 0 
-------- ^
0 0 0 1

5 ^ 4 daje 1 zaś 5 + 4 to 9. Natomiast jak dalej będziemy drążyć to ten algorytm zamieni nam wartości:

0 1 0 1 <-- a (5)
0 1 0 0 <-- b (4)
-------- ^
0 0 0 1 <--- nowe a

b = a ^ b

0 0 0 1 <---- a
0 1 0 0 
-------^
0 1 0 1 (5) <---- nowe b

a = a ^ b

0 0 0 1
0 1 0 1
-------^
0 1 0 0 (4)

b = 5
a = 4