Algoritmus swapu XOR - XOR swap algorithm

Výměna pomocí algoritmu XOR swap křupky mezi proměnnými bez použití dočasného úložiště

v programování, Výměna XOR je algoritmus který používá XOR bitový provoz na vyměnit hodnoty odlišných proměnné mít stejné datový typ bez použití dočasné proměnné. „Odlišný“ znamená, že proměnné jsou uloženy na různých nepřekrývajících se adresách paměti, protože algoritmus by nastavil jedinou aliasovanou hodnotu na nulu; skutečné hodnoty proměnných se nemusí lišit.

Algoritmus

Konvenční swapování vyžaduje použití dočasné proměnné úložiště. Při použití swapového algoritmu XOR však není potřeba žádné dočasné úložiště. Algoritmus je následující:^[1]^[2]

X := X XOR YY := Y XOR XX := X XOR Y

Algoritmus obvykle odpovídá třem strojový kód instrukce. Protože XOR je a komutativní operace, X XOR Y lze v libovolném řádku nahradit Y XOR X. Při kódování v assembleru se tato komutativita často uplatňuje ve druhém řádku:

Pseudo kód	IBM Systém / 370 shromáždění	Sestava x86
`X := X XOR Y`	`XR R1,R2`	`xor eax, odliv`
`Y := Y XOR X`	`XR R2,R1`	`xor odliv, eax`
`X := X XOR Y`	`XR R1,R2`	`xor eax, odliv`

Ve výše uvedeném ukázkovém kódu sestavy System / 370 jsou R1 a R2 odlišné registry a každý XR operace ponechá svůj výsledek v registru pojmenovaném v prvním argumentu. Pomocí sestavy x86 jsou hodnoty X a Y v registrech eax a ebx (v uvedeném pořadí) a xor umístí výsledek operace do prvního registru.

Algoritmus však selže, pokud X a y použít stejné umístění úložiště, protože hodnota uložená v tomto umístění bude vynulována první instrukcí XOR a poté zůstane nulová; nebude „vyměněn za sebe“. Tohle je ne stejně jako kdyby X a y mají stejné hodnoty. Problém nastane, až když X a y použít stejné umístění úložiště, v takovém případě musí být jejich hodnoty již stejné. To je, pokud X a y použijte stejné umístění úložiště, pak řádek:

X := X XOR Y

sady X na nulu (protože X = y takže X XOR Y je nula) a sady y na nulu (protože používá stejné umístění úložiště), což způsobí X a y ztratit své původní hodnoty.

Důkaz správnosti

The binární operace XOR přes bitové řetězce délky ${ displaystyle N}$ vykazuje následující vlastnosti (kde ${ displaystyle oplus}$ označuje XOR):^[A]

L1. Komutativita: ${ displaystyle A oplus B = B oplus A}$
L2. Asociativita: ${ displaystyle (A oplus B) oplus C = A oplus (B oplus C)}$
L3. Identita existuje: existuje bitový řetězec, 0, (délky N) takové, že ${ displaystyle A oplus 0 = A}$ pro všechny ${ displaystyle A}$
L4. Každý prvek je svůj vlastní inverzní: pro každého ${ displaystyle A}$ , ${ displaystyle A oplus A = 0}$ .

Předpokládejme, že máme dva odlišné registry R1 a R2 jako v tabulce níže, s počátečními hodnotami A a B resp. Níže provádíme níže uvedené operace a výsledky snižujeme pomocí výše uvedených vlastností.

Krok	Úkon	Registrace 1	Registrovat 2	Snížení
0	Počáteční 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 = (B oplus A) oplus A}$ ${ displaystyle = B oplus (A oplus A)}$ ${ displaystyle = B oplus 0}$ ${ displaystyle = B}$	${ displaystyle A}$	L1 L2 L4 L3

Interpretace lineární algebry

Protože XOR lze interpretovat jako binární sčítání a dvojici bitů lze interpretovat jako vektor v dvojrozměrném vektorový prostor přes pole se dvěma prvky, kroky v algoritmu lze interpretovat jako násobení maticemi 2 × 2 nad polem se dvěma prvky. Pro jednoduchost předpokládejme, že zpočátku X a y jsou jednotlivé bity, ne bitové vektory.

Například krok:

X := X XOR Y

který má také implicitní:

Y := Y

odpovídá matici ${ displaystyle left ({ begin {smallmatrix} 1 & 1 0 & 1 end {smallmatrix}} right)}$ tak jako

{ displaystyle { begin {pmatrix} 1 & 1 0 & 1 end {pmatrix}} { begin {pmatrix} x y end {pmatrix}} = { begin {pmatrix} x + y y end {pmatrix}}.}

Pořadí operací je pak vyjádřeno jako:

{ displaystyle { begin {pmatrix} 1 & 1 0 & 1 end {pmatrix}} { begin {pmatrix} 1 & 0 1 & 1 end {pmatrix}} { begin {pmatrix} 1 & 1 0 & 1 end {pmatrix} } = { begin {pmatrix} 0 & 1 1 & 0 end {pmatrix}}}

(práce s binárními hodnotami, so ${ displaystyle 1 + 1 = 0}$ ), který vyjadřuje elementární matice přepínání dvou řádků (nebo sloupců) z hlediska průřezy (nůžky) přidání jednoho prvku k druhému.

Zobecnit na to, kde X a Y nejsou jednotlivé bity, ale bitové vektory délky n, jsou tyto matice 2 × 2 nahrazeny 2n×2n blokové matice jako ${ displaystyle left ({ begin {smallmatrix} I_ {n} & I_ {n} 0 & I_ {n} end {smallmatrix}} right).}$

Tyto matice fungují hodnoty, ne na proměnné (s úložnými místy), proto tato interpretace abstrahuje od otázek umístění úložiště a problému sdílení obou proměnných stejného umístění úložiště.

Příklad kódu

A C funkce, která implementuje XOR swapový algoritmus:

prázdnota XorSwap(int *X, int *y) {  -li (X != y)  {    *X ^= *y;    *y ^= *X;    *X ^= *y;  }}

Kód nejprve zkontroluje, zda jsou adresy odlišné. Jinak by se algoritmus složil na trojitý * x ^ = * x, což by vedlo k nule.

Algoritmus swapu XOR lze také definovat pomocí makra:

#define XORSWAP_UNSAFE (a, b)   ((a) ^ = (b), (b) ^ = (a),    (a) ^ = (b)) / * Nepracuje, když a a b jsou stejný objekt - přiřadí nulu                   (0) k objektu v tom případě * /#define XORSWAP (a, b)   ((& (a) == & (b))? (a) / * Zkontrolujte odlišné adresy * /                    \                  : XORSWAP_UNSAFE (a, b))

Důvody pro použití v praxi

Ve většině praktických scénářů je triviální swapový algoritmus využívající dočasný registr efektivnější. Mezi omezené situace, ve kterých může být výměna XOR praktická, patří:

na procesoru, kde kódování sady instrukcí umožňuje kódování swapu XOR v menším počtu bytů
v regionu s vysokou registrační tlak, může to umožnit alokátor registrů vyhnout se rozlití registru
v mikrokontroléry kde dostupná RAM je velmi omezená.
v kryptografických aplikacích, které potřebují funkce konstantního času, aby se zabránilo časovým útokům bočního kanálu^[3]

Protože tyto situace jsou vzácné, většina optimalizujících překladačů negeneruje výměnný kód XOR.

Důvody vyhýbání se praxi

Většina moderních překladačů dokáže optimalizovat dočasnou proměnnou v třícestném swapu, v takovém případě použije stejné množství paměti a stejný počet registrů jako XOR swap a je přinejmenším stejně rychlá a často rychlejší. Kromě toho je výměna XOR zcela neprůhledná pro kohokoli, kdo tuto techniku nezná.

Na moderní Architektury CPU, technika XOR může být pomalejší než použití dočasné proměnné k výměně. Přinejmenším na nedávných procesorech x86, jak AMD, tak Intel, dochází při pohybu mezi registry pravidelně k nulové latenci. (Toto se nazývá eliminace MOV.) I když není k dispozici žádný architektonický registr k použití, XCHG instrukce bude minimálně tak rychlá jako tři XOR dohromady. Dalším důvodem je, že moderní CPU se snaží provádět instrukce paralelně přes instrukční potrubí. V technice XOR závisí vstupy do každé operace na výsledcích předchozí operace, takže musí být provedeny v přísně sekvenčním pořadí, což neguje všechny výhody paralelismus na úrovni instrukcí.^[4]

Aliasing

Výměna XOR je v praxi také komplikována aliasing. Pokud dojde k pokusu o XOR-zaměnit obsah nějakého místa za sebe, výsledkem je, že místo je vynulováno a jeho hodnota ztracena. XOR swapping proto nesmí být používán slepě v jazyce vysoké úrovně, pokud je možný aliasing.

Podobné problémy se vyskytují u volat podle jména, jako v Jensenovo zařízení, kde prohození i a A [i] prostřednictvím dočasné proměnné přináší nesprávné výsledky kvůli souvisejícím argumentům: swapping via teplota = i; i = A [i]; A [i] = tepl změní hodnotu pro i ve druhém prohlášení, které pak vede k nesprávné hodnotě i pro A [i] ve třetím prohlášení.

Variace

Základní princip swapového algoritmu XOR lze použít na jakoukoli operaci splňující kritéria L1 až L4 výše. Nahrazení XOR sčítáním a odčítáním dává mírně odlišnou, ale do značné míry ekvivalentní formulaci:

prázdnota AddSwap( nepodepsaný int* X, nepodepsaný int* y ){  -li (X != y)  {    *X = *X + *y;    *y = *X - *y;    *X = *X - *y;  }}

Na rozdíl od swapu XOR vyžaduje tato variace, aby podkladový procesor nebo programovací jazyk používal metodu jako např modulární aritmetika nebo bignums zaručit, že výpočet X + Y nemůže způsobit chybu kvůli přetečení celého čísla. Proto je v praxi vidět ještě vzácněji než XOR swap.

Provádění AddSwap výše v programovacím jazyce C vždy funguje i v případě přetečení celého čísla, protože podle standardu C se sčítání a odčítání celých čísel bez znaménka řídí pravidly modulární aritmetika, i. E. jsou prováděny v cyklická skupina ${ displaystyle mathbb {Z} / 2 ^ {s} mathbb {Z}}$ kde ${ displaystyle s}$ je počet bitů nepodepsané int. Ve skutečnosti správnost algoritmu vyplývá ze skutečnosti, že vzorce ${ displaystyle (x + y) -y = x}$ a ${ displaystyle (x + y) - ((x + y) -y) = y}$ držet v každém abelianská skupina. Ve skutečnosti jde o zobecnění důkazu pro swapový algoritmus XOR: XOR je sčítání i odčítání v abelianské skupině ${ displaystyle ( mathbb {Z} / 2 mathbb {Z}) ^ {s}}$ (který je přímý součet z s kopie ${ displaystyle mathbb {Z} / 2 mathbb {Z}}$ ).

To neplatí při jednání s podepsané int typ (výchozí pro int). Podepsané celočíselné přetečení je nedefinované chování v jazyce C, a proto modulární aritmetika není standardem zaručena (kompilátor vyhovující standardu může takový kód optimalizovat, což vede k nesprávným výsledkům).

Viz také

Symetrický rozdíl
Propojený seznam XOR
Feistelova šifra (XOR swapový algoritmus je zdegenerovaná forma Feistelova cypheru)

Poznámky

^ První tři vlastnosti, spolu s existencí inverze pro každý prvek, jsou definicí an abelianská skupina. Poslední vlastností je tvrzení, že každý prvek je involuce, tedy mít objednat 2, což neplatí pro všechny abelianské skupiny.

Reference

^ „The Magic of XOR“. Cs.umd.edu. Citováno 2014-04-02.
^ „Zaměňovat hodnoty s XOR“. graphics.stanford.edu. Citováno 2014-05-02.
^ Bruce Schneier, Tadayoshi Kohno, Niels Ferguson, (2010). Kryptografické inženýrství: konstrukční principy a praktické aplikace. Indianapolis, IN: Wiley Pub., Inc. str. 251 a násl. ISBN 978-0-470-47424-2.CS1 maint: extra interpunkce (odkaz)
^ Amarasinghe, Saman; Leiserson, Charles (2010). „6.172 Výkonové inženýrství softwarových systémů, přednáška 2“. MIT OpenCourseWare. Massachusetts Institute of Technology. Citováno 27. ledna 2015.

[3] První tři vlastnosti, spolu s existencí inverze pro každý prvek, jsou definicí an abelianská skupina. Poslední vlastností je tvrzení, že každý prvek je involuce, tedy mít objednat 2, což neplatí pro všechny abelianské skupiny.

[1] „The Magic of XOR“. Cs.umd.edu. Citováno 2014-04-02.

[2] „Zaměňovat hodnoty s XOR“. graphics.stanford.edu. Citováno 2014-05-02.

[4] Bruce Schneier, Tadayoshi Kohno, Niels Ferguson, (2010). Kryptografické inženýrství: konstrukční principy a praktické aplikace. Indianapolis, IN: Wiley Pub., Inc. str. 251 a násl. ISBN 978-0-470-47424-2.CS1 maint: extra interpunkce (odkaz)

[5] Amarasinghe, Saman; Leiserson, Charles (2010). „6.172 Výkonové inženýrství softwarových systémů, přednáška 2“. MIT OpenCourseWare. Massachusetts Institute of Technology. Citováno 27. ledna 2015.

[1]

[2]

[A]

[3]

[4]