XOR razmena



Korišćenje XOR zamene na nibl-ovima između promenljivih bez korišćenja pomoćne promenljive

U programiranju, XOR zamena je algoritam koji koristi XOR operaciju nad bitovima da zameni vrednosti "posebnim" promenljivama bez korišćenja pomoćne promenljive. "Posebne" promenljive su promenljive na različitim memorijskim adresama (vrednosti promenljivih ne moraju biti različite).

Algoritam

Običan algoritam za zamenu zahteva upotrebu pomoćne promenljive, dok XOR algoritam zamene to radi bez pomoćne promenljive. Ovako izgleda algoritam:

X := X XOR Y
Y := X XOR Y
X := X XOR Y

Algoritam tipično zahteva tri instrukcije u mašinskom jeziku. Budući da je XOR komutativna operacija, X XOR Y se može zameniti sa Y XOR X u svakoj od linija. Kada se kodira u mašinskom jeziku, ova komutativnost se često ispoljava u drugom koraku:

Pseudokod	IBM System/370 asembler	x86 asembler
X := X XOR Y	XR R1,R2	xor eax, ebx
Y := X XOR Y	XR R2,R1	xor ebx, eax
X := X XOR Y	XR R1,R2	xor eax, ebx

U gore navedenom System/370 primeru asemblerskog jezika, R1 i R2 su "posebni" registri, i svaka XR operacija smešta rezultat u prvu promenljivu. U x86 asembleru, vrednosti X i Y su u registrima eax i ebx (redom), i xor operacija smešta rezultat u prvu promenljivu.

Međutim, algoritam ne radi ako x i y koriste istu memorijsku lokaciju, pošto će se posle prve linije algoritma u prvoj promenljivoj upisati nula i ostaće nula do kraja algoritma (neće se "zameniti sama sa sobom"), ali zato treba naznačiti da ovo nije isto kao da x i y imaju istu vrednost. Problem se samo pojavljuje kada x i y koriste istu memorijsku lokaciju i u tom slučaju moraju imati istu vrednost. U tom slučaju algoritam:

X := X XOR Y

postavlja x na nulu (zato što x = y i zbog toga X XOR Y je 0) i postavlja y na nulu (zato što koristi istu lokaciju), što uzrokuje da x i y izgube svoje prvobitne vrednosti.

Dokaz ispravnosti

Binarna operacija XOR ispoljava sledeća svojstva za bitovske niske dužine $N$ (gde $\oplus$ predstavlja XOR):

• L1. Komutativnost: $A\oplus B=B\oplus A$
• L2. Asocijativnost: $(A\oplus B)\oplus C=A\oplus (B\oplus C)$
• L3. Identitet: postoji bitovska niska, 0, (dužine N) takva da $A\oplus 0=A$ za svaku $A$
• L4. Svaki elemenat ima svoj inverz: za svako $A$, $A\oplus A=0$.

Pretpostavimo da postoje "posebni" registri R1 i R2 u tabeli ispod, sa početnim vrednostima A i B redom. Obavljamo operacije u redosledu predstavljenim u tabeli ispod i smanjujemo operacije u skladu sa svojstvima navedenim iznad.

Korak	Operacija	Registar 1	Registar 2	Smanjenje
0	Početna vrednost	$\ A$	$\ B$	—
1	R1 := R1 XOR R2	$\ A\oplus B$	$\ B$	—
2	R2 := R1 XOR R2	$\ A\oplus B$	${\begin{aligned}(A\oplus B)\oplus B=&A\oplus (B\oplus B)\\=&A\oplus 0\\=&A\end{aligned}}$	L2 L4 L3
3	R1 := R1 XOR R2	${\begin{aligned}(A\oplus B)\oplus A=&A\oplus (A\oplus B)\\=&(A\oplus A)\oplus B\\=&0\oplus B\\=&B\end{aligned}}$	$\ A$	L1 L2 L4 L3

Interpretacija u linearnoj algebri

Kako XOR operacija može biti tumačena kao binarno sabiranje i dve vrednosti mogu biti tumačene kao tačka u dvo-dimenzionom prostoru, koraci u algoritmu mogu biti tumačeni kao 2×2 matrice sa binarnim vrednostima. Zbog jednostavnosti, pretpostaviti da su x i y jedan bit, a ne vektori bitova.

Na primer, korak:

X := X XOR Y

koji takođe ima implicitno značenje:

Y := Y

odgovara matrici $\left({\begin{smallmatrix}1&1\\0&1\end{smallmatrix}}\right)$ kao

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

Sekvenca operacija je onda predstavljena kao:

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

Generalizovano gde X i Y nisu veličine od jednog bita, već vektori dužine n, ove 2×2 matrice se menjaju sa 2n×2n blok matricama kao što je $\left({\begin{smallmatrix}I_{n}&I_{n}\\0&I_{n}\end{smallmatrix}}\right).$

Treba napomenuti da ove matrice rade sa vrednostima, a ne sa promenljivama (sa memorijskim lokacijama), zbog čega ova interpretacija odbacuje probleme memorijskih lokacija i problem kada obe vrednosti imaju istu memorijsku lokaciju.

Primer koda

C funkcija koja implementira XOR zamenu:

 void xorSwap (int *x, int *y) {
     if (x != y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

Može se primetiti da algoritam ne menja odmah vrednosti promenljivih, nego prvo proveri da li su im memorijske lokacije iste. Ako su memorijske lokacije iste algoritam će odraditi *x ^= *x tri puta, što daje nulu za rezultat.

Telo ove funkcije se ponekad netačno skraćuje na if (x != y) *x^=*y^=*x^=*y;. Ovaj kod ima nedefinisano ponašanje.

Razlozi za korišćenje u praksi

U većini praktičnih scenarija, trivijalni algoritam zamene sa korišćenjem pomoćnog registra je efikasniji. Određene situacije u kojima XOR zamena može biti praktićna uključuju:

• Na procesoru gde skup instrukcija za kodiranje dozvoljava XOR razmeni da se kodira manjim brojem bajtova;
• U regionu sa visokim pritiskom registara, moze pomoci alokatoru registara da izbegne curenje registra;
• U mikrokontroleru gde je raspoloživ RAM veoma ograničen.

Zbog toga što su ove situacije retke, većina optimizujućih kompilatora ne generiše kod za XOR razmenu.

Razlozi za izbegavanje u praksi

Većina modernih kompilatora mogu da dalje optimizuju privremenu promenljivu u običnoj razmeni. U tom slučaju obična razmena koristi istu koločinu memorije i isti broj registara kao i XOR razmena i takođe je u većini slučajeva brži. XOR razmena je takođe manje čitljiva i nerazumljiva bilo kome ko nije upoznat sa algoritmom.

Na modernim arhitekturama procesora, XOR tehnika je znatno sporija od varijante sa privremenom promenljivom u razmeni. Jedan od razloga je to što moderni procesori teže da izvršavaju instrukcije paralelno sa pajplajnom instrukcija. U XOR tehnici, inputi svake operacije zavise od rezultata prethodnih operacija, zbog čega moraju biti izvršavane u striktno sekvencijalnom redosledu. Ako je efikasnost od ogromnog značaja, preporučuje se da se testiraju i XOR tehnika i razmena sa privremenom promenljivom na ciljnoj arhitekturi.

Optimizacija XOR razmene i alternative

Moderni optimizirajući kompilatori rade tako sto prevedu dati kod u "internal flow-based" reprezentaciju koju menjaju više puta pre nego što generišu odgovarajući mašinski kod. Ovi kompilatori verovatnije će da prepoznaju i optimizuju konvencionalan algoritam za zamenu (sa privremenom promenljivom). Mnogo puta ono što se napiše kao razmena u jeziku višeg nivoa kompilator prevede na jednostavan interni zapis da su dve promenljive promenile memorijske adrese, pre nego što će da generiše odgovarajući mašinski kod. Sa druge strane, kompilator može da koristi jednu instrukciju za razmenu (kao što je kod x86 XCHG instrukcija), kada ciljna arihtektura to podržava.

Aliasing

XOR razmena je takođe komplikovana u praksi aliasing-a (kada više promenljivih može imati istu memorijsku adresu). Kao što je napomenuto gore, ako se algoritam XOR razmene primeni na istu lokaciju, rezultat te lokacije će postati nula i vrednost će biti izgubljena.

Varijacije

Osnovni princip XOR razmene se može primeniti na bilo koju operaciju koja ispunjava kriterijume od L1 do L4. Menjanjem XOR-a sabiranjem i oduzimanjem dobija se nešto drugačija, ali ekvivalentna formulacija:

 void addSwap (unsigned int *x, unsigned int *y)
 {
     if (x != y) {
         *x = *x + *y;
         *y = *x - *y;
         *x = *x - *y;
     }
 }

Za razliku od XOR razmene, ova varijacija zahteva da procesor ili programski jezik koriste metode kao što je modularna aritmetika da bi garantovala da X + Y ne napravi grešku zbog prekoračenja brojeva. Zbog toga, ova varijanta je još ređe viđena u praksi od XOR razmene.

Međutim, može se primetiti da implementacija addSwap u C programskom jeziku uvek radi, čak i u slučaju prekoračenja jer, po C standardu, sabiranje i oduzimanje "unsigned" brojeva prate pravila modularne aritmetike. Korektnost ovog algoritma proizilazi iz činjenice da su formule $(x+y)-y=x$ i $(x+y)-((x+y)-y)=y$ sadržane u svakoj Abelovoj grupi. Ovo je zapravo generalizacija dokaza koreknosti za XOR razmenu: XOR je i sabiranje i oduzimanje u abelovoj grupi $(\mathbb {Z} /2\mathbb {Z} )^{s}$.