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
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 hosszúságú bittömbök feletti XOR binér művelet a következő tulajdonságokkal rendelkezik (ahol az XOR műveletet jelöli):
L1. Kommutativitás: L2. Asszociativitás: L3. Neutrális elem: Létezik egy 0 értékű (N hosszú) bitlánc, amelyre bármely esetén L4.''' Minden elem a saját inverze: minden esetén .A matematikában az inverz elem fogalma általánosítja a számok ellentétét () és reciprokát ().
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 — 1 R1 := R1 XOR R2 — 2 R2 := R1 XOR R2 L2 L4 L3 3 R1 := R1 XOR R2 L1L2L4L3
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 mátrixnak, mint . A műveletek sorrendjét ezután a következőképpen fejezzük ki:
(bináris értékekkel dolgozik, tehát ), amely két sor (vagy oszlop) felcserélésének elemi mátrixát fejezi kiAz elemi mátrix egy négyzetes mátrix, amelyet az egységmátrixon végzett egyetlen elemi sorművelet alkalmazásával kapunk. az egyik elem másikhoz való hozzáadásának transzvekcióival (nyírásaivalA síkgeometriában a nyírási leképezés egy affin transzformáció, amely minden pontot egy rögzített irányban elmozdít egy adott, az adott iránnyal párhuzamos egyenestől való előjeles távolságával arányos mennyiséggel.).
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
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ékA guard egy logikai kifejezés, amelynek igaznak kell lennie az értékelése során, ha a program végrehajtásának folytatódnia kell a kérdéses ágban. A guard clause (védelmi záradék) korai kilépést biztosít egy szubrutinból, és egy gyakran használt eltérés a strukturált programozástól, eltávolítva egy szintet a beágyazásból és kisebb kódot eredményezve: az if guard { ... } helyére if not guard: return; ... kerül. 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.A számítástechnikában az utasítás-pipelining egy olyan technika, amely egyetlen processzoron belüli utasításszintű párhuzamosságot valósít meg. A pipelining célja, hogy a processzor minden részét valamilyen utasítással lefoglalja azáltal, hogy a bejövő utasításokat egymást követő lépések sorozatára ("pipeline") osztja, amelyeket különböző processzoregységek hajtanak végre, az utasítások különböző részeit párhuzamosan feldolgozva. 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ésA számítástechnikában az aliasing olyan helyzetet ír le, amelyben a memóriában lévő adathelyhez a programban különböző szimbolikus neveken keresztül lehet hozzáférni. Így az adatok egyetlen névvel történő módosítása implicit módon módosítja az összes alias névhez tartozó értékeket, amire a programozó nem feltétlenül számít. Ennek eredményeként az aliasing különösen megnehezíti a programok megértését, elemzését és optimalizálását. 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,A név szerinti hívás (call by name) egy kiértékelési stratégia, ahol a függvény argumentumai nem értékelődnek ki a függvény meghívása előtt, hanem közvetlenül a függvény törzsébe helyettesítődnek be, majd valahányszor megjelennek a függvényben, kiértékelődnek. 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,A számítástudományban az tetszőleges precizitású aritmetika, más néven bignum aritmetika azt jelenti, hogy a számításokat olyan számokon végzik, amelyek pontosságát potenciálisan csak a gazdarendszer rendelkezésre álló memóriája korlátozza. hogy garantálja, hogy az X + Y kiszámítása ne okozzon hibát egészszám-túlcsordulás miatt.Egész szám túlcsordulás akkor fordul elő, amikor egy egész számokon végrehajtott aritmetikai művelet olyan numerikus értéket próbál létrehozni, amely kívül esik az adott számú számjeggyel ábrázolható tartományon – vagy magasabb, mint a maximális, vagy alacsonyabb, mint a minimálisan ábrázolható érték. 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 ciklikus csoportban történik, ahol az unsigned int bitjeinek száma. Valójában az algoritmus helyessége abból következik, hogy az és a 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 Abel-csoportban (ami a 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:
Regiszterkiosztás alkalmazása