XОР размена

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

У програмирању, XОР замена је алгоритам који користи XОР операцију над битовима да замени вредности "посебним" променљивама без коришћења помоћне променљиве. "Посебне" променљиве су променљиве на различитим меморијским адресама (вредности променљивих не морају бити различите).

Алгоритам

Обичан алгоритам за замену захтева употребу помоћне променљиве, док XОР алгоритам замене то ради без помоћне променљиве. Овако изгледа алгоритам:

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

Алгоритам типично захтева три инструкције у машинском језику. Будући да је XОР комутативна операција, X XOR Y се може заменити са Y XOR X у свакој од линија. Када се кодира у машинском језику, ова комутативност се често испољава у другом кораку:

Псеудокод	ИБМ Сyстем/370 асемблер	x86 асемблер
`X := X XОР Y`	`XР Р1,Р2`	`xор еаx, ебx`
`Y := X XОР Y`	`XР Р2,Р1`	`xор ебx, еаx`
`X := X XОР Y`	`XР Р1,Р2`	`xор еаx, ебx`

У горе наведеном Сyстем/370 примеру асемблерског језика, Р1 и Р2 су "посебни" регистри, и свака XР операција смешта резултат у прву променљиву. У x86 асемблеру, вредности X и Y су у регистрима еаx и ебx (редом), и xор операција смешта резултат у прву променљиву.

Међутим, алгоритам не ради ако x и y користе исту меморијску локацију, пошто ће се после прве линије алгоритма у првој променљивој уписати нула и остаће нула до краја алгоритма (неће се "заменити сама са собом"), али зато треба назначити да ово није исто као да x и y имају исту вредност. Проблем се само појављује када x и y користе исту меморијску локацију и у том случају морају имати исту вредност. У том случају алгоритам:

X := X XOR Y

поставља x на нулу (зато што x = y и због тога X XOR Y је 0) и поставља y на нулу (зато што користи исту локацију), што узрокује да x и y изгубе своје првобитне вредности.

Доказ исправности

Бинарна операција XОР испољава следећа својства за битовске ниске дужине $N$ (где $\oplus$ представља XОР):^[1]

Л1. Комутативност: $A\oplus B=B\oplus A$
Л2. Асоцијативност: $(A\oplus B)\oplus C=A\oplus (B\oplus C)$
Л3. Идентитет: постоји битовска ниска, 0, (дужине Н) таква да $A\oplus 0=A$ за сваку $A$
Л4. Сваки елеменат има свој инверз: за свако $A$ , $A\oplus A=0$ .

Претпоставимо да постоје "посебни" регистри R1 и R2 у табели испод, са почетним вредностима А и Б редом. Обављамо операције у редоследу представљеним у табели испод и смањујемо операције у складу са својствима наведеним изнад.

Корак	Операција	Регистар 1	Регистар 2	Смањење
0	Почетна вредност	$\ 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}}$	Л2 Л4 Л3
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$	Л1 Л2 Л4 Л3

Интерпретација у линеарној алгебри

Како XОР операција може бити тумачена као бинарно сабирање и две вредности могу бити тумачене као тачка у дво-димензионом простору, кораци у алгоритму могу бити тумачени као 2×2 матрице са бинарним вредностима. Због једноставности, претпоставити да су x и y један бит, а не вектори битова.

На пример, корак:

X := X XOR Y

који такође има имплицитно значење:

Y := Y

одговара матрици $\left({\begin{smallmatrix}1&1\\0&1\end{smallmatrix}}\right)$ као

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

Секвенца операција је онда представљена као:

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

Генерализовано где X и Y нису величине од једног бита, већ вектори дужине н, ове 2×2 матрице се мењају са 2н×2н блок матрицама као што је $\left({\begin{smallmatrix}I_{n}&I_{n}\\0&I_{n}\end{smallmatrix}}\right).$

Треба напоменути да ове матрице раде са вредностима, а не са променљивама (са меморијским локацијама), због чега ова интерпретација одбацује проблеме меморијских локација и проблем када обе вредности имају исту меморијску локацију.

Пример кода

C функција која имплементира XОР замену:

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

Може се приметити да алгоритам не мења одмах вредности променљивих, него прво провери да ли су им меморијске локације исте. Ако су меморијске локације исте алгоритам ће одрадити *x ^= *x три пута, што даје нулу за резултат.

Тело ове функције се понекад нетачно скраћује на if (x != y) *x^=*y^=*x^=*y;. Овај код има недефинисано понашање.

Разлози за коришћење у пракси

У већини практичних сценарија, тривијални алгоритам замене са коришћењем помоћног регистра је ефикаснији. Одређене ситуације у којима XОР замена може бити практићна укључују:

На процесору где скуп инструкција за кодирање дозвољава XОР размени да се кодира мањим бројем бајтова;
У региону са високим притиском регистара, мозе помоци алокатору регистара да избегне цурење регистра;
У микроконтролеру где је расположив РАМ веома ограничен.

Због тога што су ове ситуације ретке, већина оптимизујућих компилатора не генерише код за XОР размену.

Разлози за избегавање у пракси

Већина модерних компилатора могу да даље оптимизују привремену променљиву у обичној размени. У том случају обична размена користи исту колочину меморије и исти број регистара као и XОР размена и такође је у већини случајева бржи. XОР размена је такође мање читљива и неразумљива било коме ко није упознат са алгоритмом.

На модерним архитектурама процесора, XОР техника је знатно спорија од варијанте са привременом променљивом у размени. Један од разлога је то што модерни процесори теже да извршавају инструкције паралелно са пајплајном инструкција. У XОР техници, инпути сваке операције зависе од резултата претходних операција, због чега морају бити извршаване у стриктно секвенцијалном редоследу. Ако је ефикасност од огромног значаја, препоручује се да се тестирају и XОР техника и размена са привременом променљивом на циљној архитектури.

Оптимизација XОР размене и алтернативе

Модерни оптимизирајући компилатори раде тако сто преведу дати код у "интернал флоw-басед" репрезентацију коју мењају више пута пре него што генеришу одговарајући машински код. Ови компилатори вероватније ће да препознају и оптимизују конвенционалан алгоритам за замену (са привременом променљивом). Много пута оно што се напише као размена у језику вишег нивоа компилатор преведе на једноставан интерни запис да су две променљиве промениле меморијске адресе, пре него што ће да генерише одговарајући машински код. Са друге стране, компилатор може да користи једну инструкцију за размену (као што је код x86 XЦХГ инструкција), када циљна арихтектура то подржава.

Алиасинг

XОР размена је такође компликована у пракси алиасинг-а (када више променљивих може имати исту меморијску адресу). Као што је напоменуто горе, ако се алгоритам XОР размене примени на исту локацију, резултат те локације ће постати нула и вредност ће бити изгубљена.

Варијације

Основни принцип XОР размене се може применити на било коју операцију која испуњава критеријуме од Л1 до Л4. Мењањем XОР-а сабирањем и одузимањем добија се нешто другачија, али еквивалентна формулација:

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

За разлику од XОР размене, ова варијација захтева да процесор или програмски језик користе методе као што је модуларна аритметика да би гарантовала да X + Y не направи грешку због прекорачења бројева. Због тога, ова варијанта је још ређе виђена у пракси од XОР размене.

Међутим, може се приметити да имплементација addSwap у C програмском језику увек ради, чак и у случају прекорачења јер, по C стандарду, сабирање и одузимање "унсигнед" бројева прате правила модуларне аритметике. Коректност овог алгоритма произилази из чињенице да су формуле $(x+y)-y=x$ и $(x+y)-((x+y)-y)=y$ садржане у свакој Абеловој групи. Ово је заправо генерализација доказа корекности за XОР размену: XОР је и сабирање и одузимање у абеловој групи $(\mathbb {Z} /2\mathbb {Z} )^{s}$ .

^ Прва три својства, заједно са постојањем инверза за сваки елемент, су дефиниција Абелове групе. Последње својство је структурално својство XОР-а које остале Абелове групе могу, а и не морају имати.

[1] Прва три својства, заједно са постојањем инверза за сваки елемент, су дефиниција Абелове групе. Последње својство је структурално својство XОР-а које остале Абелове групе могу, а и не морају имати.

[1]