Prohození hodnot XORem

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:

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á ${\displaystyle \oplus }$) na bitových řetězcích pevné délky splňuje následující čtyři vlastnosti:

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

Krok	Operace	Registr 1	Registr 2	Redukce dle vlastnosti
0	Úvodní hodnota	${\displaystyle A}$	${\displaystyle B}$	—
1	R1 := R1 XOR R2	${\displaystyle A\oplus B}$	${\displaystyle \ B}$	—
2	R2 := R1 XOR R2	${\displaystyle A\oplus B}$	${\displaystyle (A\oplus B)\oplus B=A\oplus (B\oplus B)}$ ${\displaystyle =A\oplus 0}$ ${\displaystyle =A}$	L2 L4 L3
3	R1 := R1 XOR R2	${\displaystyle (A\oplus B)\oplus A=A\oplus (A\oplus B)}$ ${\displaystyle =(A\oplus A)\oplus B}$ ${\displaystyle =0\oplus B}$ ${\displaystyle =B\oplus 0}$ ${\displaystyle =B}$	${\displaystyle \ 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ě ${\displaystyle \mathbb {Z} /2^{s}\mathbb {Z} }$, kde ${\displaystyle 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.