Cesko.wiki Prohození hodnot XORem
Author
Albert Florespů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 |
|---|
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. +more 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. +more 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. +more 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
