Prohození hodnot XORem

Příklad prohození dvou půlslabik bez pomocné proměnné pomocí XORu

Prohození hodnot XORem je v programování jedním z algoritmů, kterými lze dosáhnout prohození hodnot dvou proměnných bez použití pomocné dočasné proměnné. Používá k tomu bitovou operaci úplné disjunkce.

Algoritmus

Algoritmus se skládá ze tří kroků, přičemž všechny využívají operaci XOR:

X := X xor Y
Y := Y xor X
X := X xor Y

Jednotlivé řádky obvykle přímo odpovídají instrukcím jazyka symbolických adres respektive přímo strojovým instrukcím. Následující příklad uvádí instrukce na platformách IBM System/370 a x86:

Pseudokód	IBM System/370	x86
X := X XOR Y	XR R1,R2	xor eax, ebx
Y := Y XOR X	XR R2,R1	xor ebx, eax
X := X XOR Y	XR R1,R2	xor eax, ebx

Pro funkčnost algoritmu je zásadní, aby jeho vstupem nebylo dvakrát stejné umístění. Protože totiž pro každé x je výsledek operace x XOR x nulový, bylo by hned v prvním kroku toto umístění vynulováno a tím jeho hodnota ztracena.

Důkaz správnosti

Správnost algoritmu je odvozena z toho, že binární operace XOR (značená $\oplus$) na bitových řetězcích pevné délky splňuje následující čtyři vlastnosti:

• L1. Komutativitu: $A\oplus B=B\oplus A$
• L2. Asociativitu: $(A\oplus B)\oplus C=A\oplus (B\oplus C)$
• L3. Existenci neutrálního prvku: existuje prvek, značený 0, pro který platí $A\oplus 0=A$ pro každé $A$
• L4. Každý prvek je sám sobě inverzním: pro každé $A$, $A\oplus A=0$.

Krok	Operace	Registr 1	Registr 2	Redukce dle vlastnosti
0	Úvodní hodnota	$A$	$B$	—
1	R1 := R1 XOR R2	$A\oplus B$	$\ B$	—
2	R2 := R1 XOR R2	$A\oplus B$	$(A\oplus B)\oplus B=A\oplus (B\oplus B)$ $=A\oplus 0$ $=A$	L2 L4 L3
3	R1 := R1 XOR R2	$(A\oplus B)\oplus A=A\oplus (A\oplus B)$ $=(A\oplus A)\oplus B$ $=0\oplus B$ $=B\oplus 0$ $=B$	$\ A$	L1 L2 L4 L1 L3

Varianty

Podobný algoritmus lze realizovat pomocí sčítání a odčítání:

 void addSwap (unsigned int *x, unsigned int *y)
 {
     if (x != y) {
         *x = *x + *y;
         *y = *x - *y;
         *x = *x - *y;
     }
 }

Jeho správnost je ale závislá na tom, že nedojde k celočíselnému přetečení. Je-li například práce na celých číslech realizována s podporou libovolné přesnosti nebo v rámci modulární aritmetiky, algoritmus funguje. Například v rámci jazyka C tento algoritmus funguje, neboť sčítání a odčítání dle standardu odpovídá operacím v cyklické grupě $\mathbb {Z} /2^{s}\mathbb {Z}$, kde $s$ je počet bitů.

Vzhledem k dodatečnému požadavku na vlastnosti sčítání je tato varianta používána ještě méně než varianta základní.

Výhody a nevýhody

Nevýhody:

• Je-li v daném kontextu dost volných registrů procesoru, pak bude prohození hodnot pomocí nějakého volného pravděpodobně rychlejší
• Moderní počítačové architektury často využívají překrývané zpracování strojových instrukcí. To umí rychle zpracovávat kód, ve kterém zpracování instrukce nezávisí na výsledku instrukcí těsně předcházejících. V tomto algoritmu na sebe všechny tři instrukce bezprostředně navazují, takže překrývané zpracování nemůže být využito a procesor je bude zpracovávat pomalu postupně.
• Pro programátora, který postup nezná, se jedná o obtížně pochopitelný trik, jehož prokouknutí ho při studování kódu zbytečně zdrží.

Výhody:

• Instrukce XOR má na některých architekturách úsporné kódování (tedy využití algoritmu může šetřit instrukční cache)
• V rámci části kódu náročné na volné registry může mít ušetření pomocného registru zásadní dopady na výkon.
• Na jednočipových počítačích a jiných malých platformách může mít smysl i ušetření pomocné operační paměti

Reference

V tomto článku byl použit překlad textu z článku XOR swap algorithm na anglické Wikipedii.