XOR-обмен

XOR-обмен (англ. Xor swap algorithm) — алгоритм, в котором используется побитовая операция XOR (исключающее «или») для обмена значениями между переменными, которые содержат данные одного типа, без использования дополнительной (временной) переменной. Решение задачи обеспечивается за счёт свойства самообратимости XOR: A XOR A = 0 для всех A.

Алгоритм в псевдокоде:

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

Это обычно соответствует трём инструкциям в машинном коде, например, в коде ассемблера IBM System/370:

XOR R1, R2
XOR R2, R1
XOR R1, R2

где R1 и R2 — регистры и операция XOR сохраняет результат в первом аргументе.

Алгоритм особенно часто применяется в практике программирования на ассемблере благодаря его эффективности: прочие алгоритмы обмена требуют либо использования промежуточного регистра (дополнительного ресурса хранения), либо (для числовых типов) дополнительных арифметических операций (использования излишних вычислительных ресурсов), что особенно важно при программировании микроконтроллеров и подобных простых устройств, в которых стоят жёсткие требования к расходу памяти и тактов процессора. Некоторые оптимизирующие компиляторы могут генерировать код, использующий этот алгоритм.

Тем не менее, на современных центральных процессорах общего назначения XOR-техника может оказаться медленнее, чем использование временной переменной для обмена в связи c распараллеливанием выполнения команд: в XOR-технике операнды всех команд зависят от результатов предыдущих команд, поэтому они должны быть выполнены в строго последовательном порядке. Зачастую детали используемого алгоритма скрываются внутри макроса или инлайн-функции, и в зависимости от особенностей платформы выполнения выбирается тот или иной алгоритм обмена.

При реализации такого алгоритма обмена существует ряд ошибок-ловушек, в частности, если функция обмена принимает указатели или ссылки и вызвана с одинаковыми аргументами, то произойдёт не обмен, а обнуление данных.

Ряд архитектур реализуют XOR-обмен на аппаратном уровне, первой эффективной реализацией считается машина Datacraft (1970 год), обеспечивавшая обмен любых регистров за один такт. PDP-6 имела такую возможность ещё в 1964; её инструкция EXCH могла обменивать содержимое любого регистра с содержимым любого участка памяти или другого регистра. Процессоры x86 также имеют инструкцию XCHG.

Доказательство

Битовая операция XOR над последовательностью бит $A,B,C$ длинной $N$ обладает следующими свойствами (для обозначения XOR используется $\oplus$):

• 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$ соответственно, тогда пошаговое исполнение алгоритма будет следующим:

Шаг	Операция	Регистр R1	Регистр R2	Преобразование
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=(B\oplus A)\oplus A$ $=B\oplus (A\oplus A)$ $=B\oplus 0$ $=B$	$\ A$	L1 L2 L4 L3