Úvodní stránka | Tato stránka v originále

Xor výměnový algoritmus

V programování počítače, výměna xor je algoritmus který používá exkluzivní disjunkci (XOR) operace vyměnit hodnoty dvou proměnných bez dočasné proměnné. Tento algoritmus zpracuje využití symmetric rozdílné vlastnosti XOR, to
Xor = 0 pro každý

Tabulka s obsahem
1 algoritmus
2 vysvětlení
3 kódové příklady
4 použití v praxi

Algoritmus

Standard vyměňovat algoritmy vyžadovat použití dočasného skladu - standardní intuitivní algoritmy k výměně x a y zahrnout:

Nicméně, XOR výměnový algoritmus dělá ne -- tento algoritmus následuje (kde X a Y jsou jména dvou proměnných, poněkud než dvě hodnoty):
  1. XOR X a Y a skladovat v X
  2. XOR X a Y a skladovat v Y
  3. XOR X a Y a skladovat v X

Algoritmus se dívá hodně jednodušší když to je psáno v pseudokódu.
X: = X XOR Y
Y: = X XOR Y
X: = X XOR Y

Toto typicky odpovídá tři strojová kódová poučení. Například, v IBM 370 assemblerového kódu:
XOR R1, R2
XOR R2, R1
XOR R1, R2

kde R1, a R2 je registry a operace XOR opustí výsledek v prvním argumentu. Tento algoritmus je zvláště atraktivní pro programátory assembleru přímo k jeho výkonu a efektivitě. To vyloučí použití přechodného registru, který je omezený zdroj v programování programovacího jazyka. To také odklidí dva pamětové přístupové cykly, které by byly drahé se vyrovnal operaci registru.

Vysvětlení

Například, nechal nás říkat, že my máme dvě hodnoty X = 12 a Y = 10. V binární, my máme

X = 1 1 0 0
Y = 1 0 1 0

Nyní, my XOR X a Y dostat 0 1 1 0 a skladovat v X. my teď máme
X = 0 1 1 0
Y = 1 0 1 0

XOR X a Y znovu dostat 1 1 0 0 - skladovat v Y, a my teď máme
X = 0 1 1 0
Y = 1 1 0 0

XOR X a Y znovu dostat 1 0 1 0 - skladovat v X, a my máme
X = 1 0 1 0
Y = 1 1 0 0

Hodnoty jsou vyměněny a algoritmus opravdu pracoval v tomto případě.

Obecně nicméně, jestliže my voláme počáteční hodnotu X = x0 a počáteční hodnota Y = y0. Pak, hrát nad kroky, si pamatovat XOR = 0 a b XOR 0 = b

  1. X = x0 XOR y0, Y = y0
  2. X = x0 XOR y0, Y = x0 XOR y0 XOR y0 = x0 XOR 0 = x0
  3. X = x0 XOR y0 XOR x0 = x0 XOR x0 XOR y0 = 0 XOR y0 = y0, Y = x0

Příklady kódu

x86 jazyk symbolických instrukcí

Dodržování kodexu v x86 jazyk symbolických instrukcí používá xor výměnový algoritmus vyměnit hodnotu v registru sekyry s hodnotou v BX registru bez používání dočasná vyrovnávací paměť.

           XOR sekyra, BX XOR BX, zrušit XOR sekyru, BX
Nicméně, všichni x86 mikroprocesory mají XCHG instrukci, která dělá stejnou práci na jeho operands více efektivně než nad sledem XORs.

Vizuální základní

Pokračování Vizuální základní subrutina vymění hodnoty jeho parametrů používat operátora xor.

Výměna náhradníka (Var1, Var2) Var1 = Var1 Xor Var2 Var2 = Var2 Xor Var1 Var1 = Var1 Xor Var2 končí náhradníka

C

C programovací jazyk kód realizovat XOR výměnu x a y:

 x ^= y;
 y ^= x;
 x ^= y;
Nastavení jako překladačové makro je obyčejné pro rozsáhlé užití.

# definovat xorSwap (x, y) {( x) = (x) ^ (y); (y) = (x) ^ (y); (x) = (x) ^ (y);}

Jako funkce:

 nicota xorSwap (int * x, int * y) {* x = * x ^ * y; * y = * x ^ * y; * x = * x ^ * y;}
To by mělo být poznamenal, že tato funkce nebude pracovat jestliže vy pokusíte se vyměnit něco s sebou (ie tady xorSwap (a var;, a var;) propadne - to přiřadí nulu hodnoty k var).

Použití v praxi

Někteří zkušení programátoři radí, že tato technika by neměla být použita v programování, zatímco jeho účinek není jasný ledaže vy už znáte trik. Nicméně, jiní poznamenávají, že jeho použití je přijatelné stanovovat, že trik je balen v přiměřeně jmenoval makro takový jako výměna nebo XOR _ výměna, nebo vhodný komentovat to kódu je dělán.

Použití algoritmu není neobvyklé ve vloženém shromážděném kódu kde často je velmi dostupný ohraničený prostor pro dočasný výměnový prostor a tato forma výměny může také se vyhnout nákladu/obchodu, který může dělat věci hodně rychleji. Někteří optimalizovat kompilátory moci tvořit kód používat tento algoritmus.

Tento trik mohl také být používán někým snažit se vyhrát Popletl C zápas kódu.

Vidět také: xor, rozdíl symmetric, xor provázaný seznam