Алгоритм обміну XOR

У комп'ютерному програмуванні, XOR обмін (Шаблон:Lang-en) — алгоритм, який використовує бітову операцію XOR для обміну значень різних змінних однакового типу даних без використання додаткової тимчасової змінної. Під словом «різні» мається на увазі, що значення змінних зберігається в різних адресах пам'яті; фактичні значення змінних не обов'язково повинні бути різними.

Алгоритм

Традиційний обмін значеннями потребує використання тимчасової змінної для збереження. При використанні алгоритму XOR обміну, не потрібно мати тимчасового збереження. Алгоритм виконується наступним чином:^[1]^[2]

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

Алгоритм зазвичай відповідає трьом інструкціям машинного коду. Оскільки XOR є комутативною операцією, X XOR Y можна замінити на Y XOR X у будь-якому з цих рядків. При написанні коду на мові асемблер, ця комутативність часто використовується в другому рядку:

Псевдокод	IBM System/370 асемблер	x86 асемблер
Шаблон:Code	Шаблон:Code	Шаблон:Code
Шаблон:Code	Шаблон:Code	Шаблон:Code
Шаблон:Code	Шаблон:Code	Шаблон:Code

У приведеному вище коді асемблеру для System/370, R1 і R2 є різними регістрами, і кожна операція XR записує свій результат у регістрі, що вказаний першим аргументом. При використанні асемблеру x86, значення X і Y знаходяться в регістрах eax і ebx (відповідно), а Шаблон:Code записує результат операції в перший регістр.

Однак, алгоритм не буде виконуватись, якщо x і y використовують одне сховище пам'яті, оскільки значення, що знаходиться за однією адресою будуть мати нульові значення після виконання першої інструкції XOR, і потім залишаться нулями; і це не буде заміною.

Доведення справедливості

Бітова операція XOR над послідовностями біт довжини $N$ має наступні властивості (де $\oplus$ позначає XOR):Шаблон:Efn

L1. Комутативність: $A \oplus B = B \oplus A$
L2. Асоціативність: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$
L3. Існування нейтральності: існує бітова послідовність, 0, (довжиною N), для якої виконується $A \oplus 0 = A$ для будь-якого $A$
L4. Кожен елемент є своїм власним оберненим: для кожного $A$ , $A \oplus A = 0$ .

Припустимо, що ми маємо два різні регістри R1 і R2 як показано нижче в таблиці, які мають початкові значення A і B відповідно. Виконаємо приведені нижче операції по черзі, і виконаємо спрощення за допомогою наведених вище властивостей.

Крок	Операція	Регістр 1	Регістр 2	Перетворення
0	Початкове значення	$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 = A \oplus (A \oplus B)$ $= (A \oplus A) \oplus B$ $= 0 \oplus B$ $= B \oplus 0$ $= B$	$A$	L1 L2 L4 L1 L3

Причини використання на практиці

Здебільшого, звичайний алгоритм обміну з використанням тимчасового регістра більш ефективний. Конкретні ситуації, в яких практично корисно застосувати XOR обмін є наступні:

у процесорах де набір інструкцій дозволяє виконувати XOR обмін закодований за допомогою меншої кількості байт;
у випадках з постійною нестачею вільних регістрів, це може дозволити уникнути застосування пам'яті замість регістрів;
у мікроконтролерах де доступна пам'ять RAM дуже обмежена.

Оскільки ці ситуації не є частим, більшість оптимізувальних компіляторів ніколи не генерують коду з XOR обміном.

Приклад реалізації

За допомогою препроцесора мови C, цю функцію можна реалізувати наступним чином:

#define swapXOR(x,y) do { *x ^= *y;  *y ^= *x; *x ^= *y; } while(0)

int main (int argc, char** argv) {
    int x = 5;
    int y = 7;

    printf("%i, %i\n", x,y); // до заміни 5, 7
    swapXOR(&x,&y);
    printf("%i, %i\n", x,y); // після 7, 5
}

Див. також

Примітки

Шаблон:Reflist Шаблон:Notelist

[1] Шаблон:Cite web

[2] Шаблон:Cite web

[1]

[2]

Алгоритм обміну XOR

Зміст