XOR csere algoritmus

Az XOR swap algoritmus használata apró adatrészletek cseréjére változók között ideiglenes tárolás használata nélkül

A számítógép-programozásban a kizáró VAGY csere ('XOR swap) egy olyan algoritmus, amely a kizáró vagy (XOR) bitműveletet használja két változó értékének felcserélésére anélkül, hogy az általában szükséges ideiglenes változót használná.

Az algoritmus elsősorban újdonság, és a kizáró vagy (exclusive OR, vagy XOR) művelet tulajdonságainak bemutatására szolgál. Néha programoptimalizálásként is emlegetik, de szinte nincs olyan eset, amikor a kizáró vagy művelettel végrehajtott csere előnyt biztosítana a standard, nyilvánvaló technikával szemben.

Az algoritmus

A hagyományos csere egy ideiglenes tárolási változó használatát igényli. Az XOR cserealgoritmus használatával azonban nincs szükség ideiglenes tárolásra. Az algoritmus a következő:

X := Y XOR X; // XOR műveletet alkalmaz az értékekre, és az eredményt X-ben tárolja
Y := X XOR Y; // XOR műveletet alkalmaz az értékekre, és az eredményt Y-ban tárolja
X := Y XOR X; // XOR műveletet alkalmaz az értékekre, és az eredményt X-ben tárolja

Mivel az XOR egy kommutatív művelet, az X XOR Y vagy az Y XOR X felcserélhetően használható az előző három sorban. Megjegyzendő, hogy egyes architektúrákon az XOR utasítás első operandusa meghatározza a művelet eredményének tárolási célhelyét, megakadályozva ezt a felcserélhetőséget. Az algoritmus jellemzően három gépi kódú utasításnak felel meg, amelyeket a következő táblázat három sorában található megfelelő pszeudokód és assembly utasítások képviselnek:

Pszeudokód	IBM System/370 assembly	x86 assembly	RISC-V assembly
X := X XOR Y	XR R1,R2	xor eax, ebx	xor x10, x11
Y := Y XOR X	XR R2,R1	xor ebx, eax	xor x11, x10
X := X XOR Y	XR R1,R2	xor eax, ebx	xor x10, x11

A fenti System/370 assembly kódmintában az R1 és R2 különálló regiszterek, és minden XR művelet az első argumentumban megnevezett regiszterben hagyja az eredményét. x86 assembly használatával az X és Y értékek az eax és ebx regiszterekben találhatók (rendre), az xor pedig a művelet eredményét az első regiszterbe helyezi. A RISC-V assemblyben az X és Y értékek az X10 és X11 regiszterekben találhatók, az xor pedig a művelet eredményét az első regiszterbe helyezi (ugyanúgy, mint az x86).

A pszeudokódban vagy a magas szintű nyelvi verzióban vagy implementációban azonban az algoritmus kudarcot vall, ha x és y ugyanazt a tárolási helyet használja, mivel az adott helyen tárolt értéket az első XOR utasítás lenullázza, majd nulla marad; nem „cserélődik önmagával”. Ez nem ugyanaz, mintha x és y értékei megegyeznének. A probléma csak akkor jelentkezik, ha x és y ugyanazt a tárolási helyet használja, ebben az esetben az értéküknek már eleve egyenlőnek kell lennie. Vagyis, ha x és y ugyanazt a tárolási helyet használja, akkor a sor:

X := X XOR Y

nullára állítja x-et (mivel x = y, tehát X XOR Y nulla), és y-t is nullára állítja (mivel ugyanazt a tárhelyet használja), aminek következtében x és y elveszítik eredeti értéküket.

A helyesség bizonyítása

Az $N$ hosszúságú bittömbök feletti XOR binér művelet a következő tulajdonságokkal rendelkezik (ahol $\oplus$ az XOR műveletet jelöli):

• L1. Kommutativitás: $A\oplus B=B\oplus A$
• L2. Asszociativitás: $(A\oplus B)\oplus C=A\oplus (B\oplus C)$
• L3. Neutrális elem: Létezik egy 0 értékű (N hosszú) bitlánc, amelyre bármely $A$ esetén $A\oplus 0=A$
• L4. Minden elem a saját inverze: minden $A$ esetén $A\oplus A=0$.

Tegyük fel, hogy két különböző regiszterünk van, R1 és R2, ahogy az az alábbi táblázatban látható, A és B kezdeti értékekkel. Az alábbi műveleteket sorban végrehajtjuk, és az eredményeket a fent felsorolt tulajdonságok felhasználásával redukáljuk.

Lépés	Művelet	1. regiszter	2. regiszter	Redukció
0	Kezdeti érték	$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=(B\oplus A)\oplus A$ $=B\oplus (A\oplus A)$ $=B\oplus 0$ $=B$	$\ A$	L1 L2 L4 L3

Lineáris algebrai értelmezés

Mivel az XOR értelmezhető bináris összeadásként, és egy bitpár értelmezhető vektorként egy kétdimenziós vektortérben a kételemű mező felett, az algoritmus lépései 2×2 mátrixokkal való szorzásként értelmezhetők a kételemű test felett. Az egyszerűség kedvéért kezdetben tegyük fel, hogy x és y egyaránt egyedi bitek, nem bitvektorok.

Például a lépés:

X := X XOR Y

amely implicit módon tartalmazza a következőt:

Y := Y

megfelel a $\left({\begin{smallmatrix}1&1\\0&1\end{smallmatrix}}\right)$ mátrixnak, mint

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

A műveletek sorrendjét ezután a következőképpen fejezzük ki:

${\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}}$

(bináris értékekkel dolgozik, tehát $1+1=0$), amely két sor (vagy oszlop) felcserélésének elemi mátrixát fejezi ki az egyik elem másikhoz való hozzáadásának transzvekcióival (nyírásaival).

Az X és Y nem egyetlen bit, hanem n hosszúságú bitvektorokra való általánosításhoz ezeket a 2×2 mátrixokat 2n×2n blokkmátrixokkal helyettesítjük, például $\left({\begin{smallmatrix}I_{n}&I_{n}\\0&I_{n}\end{smallmatrix}}\right).$

Ezek a mátrixok értékekkel, nem pedig változókkal (tárolási helyekkel) működnek, ezért ez az értelmezés elvonatkoztat a tárolási hely kérdéseitől és attól a problémától, hogy mindkét változó ugyanazon a tárolási helyen van.

Példa kód

Egy C függvény, amely megvalósítja az XOR csere algoritmust:

void XorSwap(int *x, int *y) 
{
  if (x == y) return;
  *x ^= *y;
  *y ^= *x;
  *x ^= *y;
}

A kód először ellenőrzi, hogy a címek különbözőek-e, és egy védelmi záradék segítségével korán kilép a függvényből, ha egyenlőek. Ezen ellenőrzés nélkül, ha egyenlőek lennének, az algoritmus egy *x ^= *x hármast adna, ami nullát eredményezne.

Az XOR cserealgoritmus makróval is definiálható:

#define XORSWAP_UNSAFE(a, b)                                                   \
  ((a) ^= (b), (b) ^= (a),                                                     \
   (a) ^= (b)) /* Nem működik, ha a és b ugyanaz az objektum \
                  - ebben az esetben nullát (0) rendel az objektumhoz */
#define XORSWAP(a, b)                                                         \
  ((&(a) == &(b)) ? (a) /* Különböző értékek ellenőrzése */                    \
                  : XORSWAP_UNSAFE(a, b))

A gyakorlatban elkerülendő okok

A modern CPU-architektúrákon az XOR technika lassabb lehet, mint egy ideiglenes változó használata a cseréhez. Legalábbis a legújabb x86-os CPU-kon, mind az AMD, mind az Intel esetében, a regiszterek közötti mozgás rendszeresen nulla késleltetéssel jár. (Ezt MOV-eliminációnak nevezik.) Még ha nincs is elérhető architekturális regiszter, az XCHG utasítás legalább olyan gyors lesz, mint a három XOR együttvéve. Egy másik ok, hogy a modern CPU-k igyekeznek az utasításokat párhuzamosan végrehajtani utasításpipeline-okon keresztül. Az XOR technikában az egyes műveletek bemenetei az előző művelet eredményétől függenek, ezért szigorúan egymás után kell végrehajtani őket, ami érvényteleníti az utasításszintű párhuzamosság előnyeit.

Aliasing

Az XOR csere a gyakorlatban az álnevezés miatt bonyolult. Ha megpróbáljuk egy adott hely tartalmát önmagával XOR-cserével felcserélni, az eredmény az, hogy a hely nullázódik, és az értéke elvész. Ezért az XOR-cserét nem szabad vakon használni magas szintű nyelvekben, ha az álnevezés lehetséges. Ez a probléma nem érvényes, ha a technikát assemblyben használják két regiszter tartalmának felcserélésére.

Hasonló problémák fordulnak elő a név szerinti hívással, mint például Jensen eszközében, ahol az i és A[i] felcserélése egy ideiglenes változón keresztül helytelen eredményeket ad az argumentumok összefüggése miatt: a csere a temp = i; i = A[i]; A[i] = temp változón keresztül megváltoztatja az i értékét a második utasításban, ami aztán helytelen i értéket eredményez A[i] számára a harmadik utasításban.

Változatok

Az XOR csere algoritmus alapelve bármely, a fenti L1-L4 kritériumoknak megfelelő műveletre alkalmazható. Az XOR összeadással és kivonással való helyettesítése különféle, kissé eltérő, de nagyrészt egyenértékű megfogalmazásokat ad. Például:

void AddSwap( unsigned int* x, unsigned int* y )
{
    *x = *x + *y;
    *y = *x - *y;
    *x = *x - *y;
}

Az XOR cserével ellentétben ez a variáció megköveteli, hogy az alapul szolgáló processzor vagy programozási nyelv olyan módszert használjon, mint a moduláris aritmetika vagy a bignum, hogy garantálja, hogy az X + Y kiszámítása ne okozzon hibát egészszám-túlcsordulás miatt. Ezért a gyakorlatban még ritkábban fordul elő, mint az XOR csere.

Azonban a fenti AddSwap implementációja a C programozási nyelvben mindig működik, még egész szám túlcsordulás esetén is, mivel a C szabvány szerint az előjel nélküli egész számok összeadása és kivonása a maradékosztály szabályait követi, azaz a $\mathbb {Z} /2^{s}\mathbb {Z}$ ciklikus csoportban történik, ahol $s$ az unsigned int bitjeinek száma. Valójában az algoritmus helyessége abból következik, hogy az $(x+y)-y=x$ és a $(x+y)-((x+y)-y)=y$ képletek bármely Abel-csoportban érvényesek. Ez általánosítja az XOR-csere algoritmus bizonyítását: az XOR az összeadás és a kivonás is az $(\mathbb {Z} /2\mathbb {Z} )^{s}$ Abel-csoportban (ami a $\mathbb {Z} /2\mathbb {Z}$ s példányának direkt összege). Ez nem érvényes a signed int típus esetén (ez az alapértelmezett az int típusnál). Az előjeles egészszám-túlcsordulás egy nem definiált viselkedés a C-ben, így a maradékosztály nem garantált a szabvány által, ami helytelen eredményekhez vezethet.

Az AddSwap műveletsorozata mátrixszorzással fejezhető ki a következőképpen:

${\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}}$

Regiszterkiosztás alkalmazása

A dedikált swap utasítással nem rendelkező architektúrákon az XOR-swap algoritmus szükséges az optimális regiszterkiosztáshoz, mivel ez elkerüli az extra ideiglenes regisztert. Ez különösen fontos azoknál a fordítóprogramoknál, amelyek statikus egyszeres értékadási formát használnak a regiszterelosztáshoz; ezek a fordítók időnként olyan programokat hoznak létre, amelyeknek két regisztert kell cserélniük, amikor egyetlen szabad regiszter sincs. Az XOR csere algoritmus elkerüli egy extra regiszter lefoglalásának vagy a regiszterek főmemóriába való kibontásának szükségességét. Az összeadás/kivonás változat is használható ugyanerre a célra.

Ez a regiszterallokációs módszer különösen releváns a GPU shader fordítók számára. A modern GPU architektúrákon a változók kiszórása költséges a korlátozott memória-sávszélesség és a magas memóriakésleltetés miatt, míg a regiszterhasználat korlátozása javíthatja a teljesítményt a regiszterfájl dinamikus particionálása miatt. Ezért egyes GPU fordítók megkövetelik az XOR swap algoritmust.

Lásd még

• XOR
• Kizáró vagy

Fordítás

• Ez a szócikk részben vagy egészben a XOR swap algorithm című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.