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-технике операнды всех команд зависят от результатов предыдущих команд, поэтому они должны быть выполнены в строго последовательном порядке. Зачастую детали используемого алгоритма скрываются внутри макроса или инлайн-функции, и в зависимости от особенностей платформы выполнения выбирается тот или иной алгоритм обмена.

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

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

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

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

• L1. Коммутативность: ${\displaystyle A\oplus B=B\oplus A}$.
• L2. Ассоциативность: ${\displaystyle (A\oplus B)\oplus C=A\oplus (B\oplus C)}$.
• L3. Нейтральный элемент: если ${\displaystyle 0}$ – это битовая последовательность длинной ${\displaystyle N}$, состоящая из нулей, то ${\displaystyle A\oplus 0=A}$ для любого ${\displaystyle A}$.
• L4. Самообратимость: для любого ${\displaystyle A}$, ${\displaystyle A\oplus A=0}$.

Предположим, имеется два независимых регистра R1 и R2 , с начальными значениями ${\displaystyle A}$ и ${\displaystyle B}$ соответственно, тогда пошаговое исполнение алгоритма будет следующим:

Шаг	Операция	Регистр R1	Регистр R2	Преобразование
0	Начальные значения	${\displaystyle A}$	${\displaystyle B}$	—
1	R1 := R1 XOR R2	${\displaystyle A\oplus B}$	${\displaystyle B}$	—
2	R2 := R1 XOR R2	${\displaystyle A\oplus B}$	${\displaystyle (A\oplus B)\oplus B=A\oplus (B\oplus B)}$ ${\displaystyle =A\oplus 0}$ ${\displaystyle =A}$	L2 L4 L3
3	R1 := R1 XOR R2	${\displaystyle (A\oplus B)\oplus A=(B\oplus A)\oplus A}$ ${\displaystyle =B\oplus (A\oplus A)}$ ${\displaystyle =B\oplus 0}$ ${\displaystyle =B}$	${\displaystyle \ A}$	L1 L2 L4 L3

Примечания

1. This year’s challenge: weak encryption Архивная копия от 3 декабря 2013 на Wayback Machine // The Underhanded C Contest, 2007: «Runners Up David Wagner, Philipe Biondi, … misimplementation of RC4 .. The XOR-swap trick is an example of coders being too clever for their own good. Here, it gradually poisons the RC4 permutation with zeroes… the XOR swap trick is very common, and its misuse is a common bug.»