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.

Примечания[править | править код]

  1. This year’s challenge: weak encryption // 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.»