Jak działa Zamiana zmiennych XOR?

Inni to wyjaśnili, teraz chcę wyjaśnić, dlaczego to był dobry pomysł, ale teraz nie jest.

W czasach, gdy mieliśmy proste Procesory jedno-lub wielo-cyklowe, tańsze było użycie tej sztuczki, aby uniknąć kosztownych dereferencji pamięci lub rozlewania rejestrów na stos. Mamy jednak teraz procesory z masywnymi rurociągami. Rurociąg P4 miał od 20 do 31 (lub więcej) etapów w swoich rurociągach, gdzie każda zależność między odczytem i zapisem do rejestru mogła spowodować wszystko na zwłokę. Swap xor ma bardzo duże zależności między A i B, które w rzeczywistości nie mają żadnego znaczenia, ale w praktyce opóźniają rurociąg. Zablokowany rurociąg powoduje powolną ścieżkę kodu, a jeśli ten swap znajduje się w twojej wewnętrznej pętli, będziesz poruszać się bardzo powoli.

Ogólnie rzecz biorąc, kompilator może dowiedzieć się, co naprawdę chcesz zrobić, gdy wykonasz swap ze zmienną temp i możesz skompilować go do pojedynczej instrukcji XCHG. Korzystanie z XOR swap znacznie utrudnia aby kompilator odgadł twoje intencje i tym samym znacznie mniej prawdopodobne, aby zoptymalizować je poprawnie. Nie wspominając o konserwacji kodu itp.

Lubię myśleć o tym graficznie, a nie numerycznie.

Powiedzmy, że zaczynasz od x = 11 i y = 5 W systemie binarnym (i użyję hipotetycznej maszyny 4-bitowej), oto x i y

       x: |1|0|1|1|   -> 8 + 2 + 1
       y: |0|1|0|1|   -> 4 + 1

Teraz dla mnie XOR jest operacją odwrotną, a robienie tego dwa razy jest lustrem:

     x^y: |1|1|1|0|
 (x^y)^y: |1|0|1|1|   <- ooh!  Check it out - x came back
 (x^y)^x: |0|1|0|1|   <- ooh!  y came back too!

Oto jeden, który powinien być nieco łatwiejszy do grok:

int x = 10, y = 7;

y = x + y; //x = 10, y = 17
x = y - x; //x = 7, y = 17
y = y - x; //x = 7, y = 10

x + y - ((x + y) - x) == x 

, więc:

x ^ y ^ ((x ^ y) ^ x) == x

Powodem, dla którego to działa, jest to, że XOR nie traci informacji. Możesz zrobić to samo ze zwykłym dodawaniem i odejmowaniem, jeśli możesz zignorować przepełnienie. Na przykład, jeśli zmienna Para A, B pierwotnie zawiera wartości 1,2, można zamienić je w następujący sposób:

 // A,B  = 1,2
A = A+B // 3,2
B = A-B // 3,1
A = A-B // 2,1

BTW jest stara sztuczka na kodowanie 2-way linked list w jednym "wskaźniku". Załóżmy, że masz listę bloków pamięci pod adresami A, B i C. Pierwsze słowo w każdym bloku to , odpowiednio:

 // first word of each block is sum of addresses of prior and next block
 0 + &B   // first word of block A
&A + &C   // first word of block B
&B + 0    // first word of block C

Jeśli masz dostęp do bloku A, daje Ci adres B. Aby dostać się do C, bierzesz "wskaźnik" w B i odejmujesz A, i tak dalej. Działa równie dobrze do tyłu. Aby uruchomić listę, musisz zachować wskaźniki do dwóch kolejnych bloków. Oczywiście użyłbyś XOR zamiast dodawania/subtracji, więc nie musiałbyś się martwić o przepełnienie.

Możesz rozszerzyć to na "linked web", jeśli chcesz się zabawić.

Większość ludzi zamieniłaby dwie zmienne x i y używając zmiennej tymczasowej, jak to:

tmp = x
x = y
y = tmp

Oto zgrabna sztuczka programistyczna, aby zamienić dwie wartości bez potrzeby temp:

x = x xor y
y = x xor y
x = x xor y

Więcej szczegółów w Zamień dwie zmienne za pomocą XOR

W linii 1 łączymy x i y (używając XOR), aby uzyskać tę "hybrydę" i przechowujemy ją z powrotem w x. XOR jest świetnym sposobem na zapisanie informacji, ponieważ możesz ją usunąć, wykonując ponownie XOR.

On line 2. We XOR the hybrid z y, który usuwa wszystkie informacje y, pozostawiając nas tylko z x. zapisujemy ten wynik z powrotem do y, więc teraz zostały zamienione.

W ostatniej linii x nadal ma wartość hybrydową. XOR jeszcze raz z y (teraz z oryginalną wartością x), aby usunąć wszystkie ślady x z hybrydy. Zostaje nam y i zamiana jest zakończona!

Komputer faktycznie ma ukrytą zmienną "temp", która przechowuje pośrednie wyniki przed zapisaniem ich z powrotem do Zarejestruj się. Na przykład, jeśli dodasz 3 do rejestru (w pseudokodzie maszynowym):

ADD 3 A // add 3 to register A

ALU (arytmetyczna Jednostka logiczna) jest w rzeczywistości tym,co wykonuje instrukcję 3+A. pobiera dane wejściowe (3, A) i tworzy wynik (3 + A), który następnie procesor zapisuje z powrotem do oryginalnego rejestru A. Więc użyliśmy ALU jako tymczasowej przestrzeni zarysowania, zanim otrzymaliśmy ostateczną odpowiedź.

Bierzemy tymczasowe dane ALU za pewnik, ale zawsze tam są. W podobnym w ten sposób ALU może zwrócić pośredni wynik XOR w przypadku x = XOR y, w którym to momencie procesor zapisuje go do oryginalnego rejestru x.

Ponieważ nie jesteśmy przyzwyczajeni do myślenia o biednym, zaniedbanym ALU, XOR swap wydaje się magiczny, ponieważ nie ma wyraźnej zmiennej tymczasowej. Niektóre maszyny posiadają 1-stopniową instrukcję exchange XCHG do zamiany dwóch rejestrów.

@VonC ma rację, to zgrabna sztuczka matematyczna. Wyobraź sobie 4 bitowe słowa i zobacz, czy to pomoże.

word1 ^= word2;
word2 ^= word1;
word1 ^= word2;


word1    word2
0101     1111
after 1st xor
1010     1111
after 2nd xor
1010     0101
after 3rd xor
1111     0101

Zasadniczo w podejściu XOR są 3 kroki:

A ' = A XOR b (1)
b '= a ' XOR b (2)
a "= A 'XOR b' (3)

Zrozumieć dlaczego to działa najpierw zauważ, że:

1. XOR wytworzy 1 tylko wtedy, gdy dokładnie jeden z jego operandów wynosi 1, a drugi zero;
2. XOR jest więc a XOR b = B XOR a;
3. XOR jest asocjacyjny więc (a XOR b) XOR c = A XOR (b XOR c); oraz
4. A XOR a = 0 (powinno to być oczywiste z definicji w 1 powyżej)

Po kroku (1), binarna reprezentacja a będzie miała 1-bity tylko w pozycjach bitowych, gdzie A i b mają przeciwstawne bity. Jest to albo (ak=1, bk=0) albo (ak=0, bk=1). Teraz, gdy wykonamy podstawienie w Kroku (2) otrzymujemy:

B' = (A XOR b) XOR B
= a XOR (b XOR b) ponieważ XOR jest asocjacyjny
= a XOR 0 ponieważ [4] powyżej
= a ze względu na definicję XOR (patrz 1 powyżej)

Teraz możemy zastąpić Step (3):

A " = (A XOR b) XOR a
= (b XOR a) XOR a ponieważ XOR jest przemienny
= b XOR (a XOR a) ponieważ XOR jest asocjacyjny
= b XOR 0 ponieważ [4] powyżej
= b ze względu na definicję XOR (patrz 1 powyżej)

Więcej informacji tutaj: konieczne i wystarczające

Na marginesie odkryłem to koło niezależnie kilka lat temu w formie zamiany liczb całkowitych wykonując:

a = a + b
b = a - b ( = a + b - b once expanded)
a = a - b ( = a + b - a once expanded).

(jest to wspomniane wyżej w sposób trudny do odczytania),

To samo rozumowanie odnosi się do swapów xor: a ^ b ^ b = a i a ^ b ^ A = a. ponieważ xor jest przemienny, x ^ x = 0 i x ^ 0 = x, jest to dość łatwe do zauważenia, ponieważ

= a ^ b ^ b
= a ^ 0
= a

I

= a ^ b ^ a 
= a ^ a ^ b 
= 0 ^ b 
= b