Co to jest operacja XOR?

Na bitach można wykonywać operacje logiczne takie jak: AND (koniunkcja), OR (alternatywa), czy właśnie XOR. Polegają one na porównaniu poszczególnych bitów zadanych liczb i zwrócenie wyniku tego porównania:

Jak widać operacja AND jest prawdziwa wtedy, gdy oba bity maja wartość 1 (prawda), a OR jest prawdziwe gdy CONAJMNIEJ jeden bit ma wartość 1.

Co zatem zwraca XOR? XOR zwraca prawdę (czyli 1) gdy TYLKO JEDEN z porównywanych bitów ma wartość 1. A wiec:

Co więcej operacja XOR ma ciekawa własność. Mianowicie mamy dane dwie liczby A i B. Wtedy po operacji XOR dadzą one jakąś liczbę C: A XOR B = C (również B XOR A = C). Okazuje się, że wynikiem operacji XOR na liczbie C i jednej z tych liczb jest druga liczba:

Przykład praktyczny:

I ta własność jest wykorzystana przy zamianie liczb!

Aby dokonać tej zamiany wystarczy wykonać następujące działania (zamieniamy miejscami zawartość zmiennych A i B):

Zobaczmy co dzieje się z zawartością zmiennych po tych operacjach:

(0) Załóżmy, że zmienna A zawiera liczbę o wartości x, a zmienna B zawiera liczbę o wartości y. Wiemy też, że A XOR B = z (x XOR y = z). Liczby z nie znamy ale tak naprawdę nie będzie nam to potrzebne.

Wartości zmiennych przed zamianą:

(1) Do zmiennej A przypisujemy A XOR B, a wiec x XOR y, co jest równe z.

Wartości zmiennych po 1 operacji:

(2) Teraz do zmiennej B zapisujemy wynik operacji A XOR B, a że w zmiennej A znajduje się już liczba z zostanie wykonana operacja z XOR y, z własności operacji XOR wiemy, że wynikiem będzie liczba x (z XOR y = x).

Wartości zmiennych po 2 operacji:

(3) Na koniec jeszcze raz XOR'ujemy liczby - A XOR B (z XOR x = y), wynikiem jest liczba y, którą przypisujemy do zmiennej A.

Wartości zmiennych po 3 operacji:

I tym samym zamieniliśmy ze sobą dwie liczby nie korzystając z żadnych innych zmiennych!