- Зор-своп алгоритм
-
В программировании, обмен при помощи исключающего ИЛИ (англ. Xor swap algorithm, кзор-своп алгоритм) — это алгоритм, который использует операцию исключающего ИЛИ (XOR) для обмена различных значений переменных, имеющих один и тот же тип данных без использования временной переменной. Этот алгоритм работает при помощи свойства симметричного различия, которым обладает XOR:
A XOR A = 0 для всех A
Содержание
Алгоритм
Стандартные алгоритмы обмена требуют использования временного хранилища. Интуитивный алгоритм для обмена x и y включает:
- Копирование y во временное хранилище (
temp ← y
) - Установка y значением x (
y ← x
) - Копирование значения из временного хранилища обратно в x. (
x ← temp
)
Или, если даны две переменные x и y целого типа, арифметический алгоритм для их обмена таков:
- x := x + y
- y := x – y
- x := x – y
Конечно, вышеприведённый алгоритм будет прерываться на системах, которые перехватывают переполнение целого. Используя алгоритм обмена при помощи исключающего ИЛИ, однако, не требуется ни временное хранилище, ни определение переполнения. Алгоритм в данном случае таков (где X и Y — имена переменных, а не значения):
- XOR X и Y и сохраняем в X
- XOR X и Y и сохраняем в Y
- XOR X и Y и сохраняем в X
Алгоритм выглядит проще, когда записан в псевдокоде.
- X := X XOR Y
- Y := X XOR Y
- X := X XOR Y
Это обычно соответствует трём инструкциям в машинном коде. Например, в коде ассемблера IBM System/370:
- XOR R1, R2
- XOR R2, R1
- XOR R1, R2
где R1 и R2 регистры и операция XOR сохраняет результат в первом аргументе. Этот алгоритм особенно привлекателен для программистов на ассемблере из-за его эффективности. Он уничтожает необходимость в использовании промежуточного регистра, что обычно является ограниченным ресурсом в программировании на машинном языке. Он также уничтожает два цикла доступа к памяти, которые всегда более дорогие, по сравнению с регистровыми операциями.
Примеры кода
Object Pascal
Процедура на Object Pascal для обмена двух целых, используя алгоритм обмена с исключающим ИЛИ:
procedure XorSwap(var X, Y: Integer); begin X := X xor Y; Y := X xor Y; X := X xor Y; end;
Надо заметить, что эта функция не будет работать, если мы попытаемся обменять что-то с самим собой. Таким образом
XorSwap(var1, var1)
будет присваивать значение нуль переменнойvar1
.C
Код на Си для выполнения:
void xorSwap(int *x, int *y) { *x ^= *y; *y ^= *x; *x ^= *y; }
Часто встречаемый однострочник
x ^= y ^= x ^= y;
является примером с неопределённым поведением, так как он модифицирует
x
больше чем один раз без промежуточной точки следования. Этого следует избегать.Использование на практике
Использование алгоритма довольно распространено в ассемблерном коде для микроконтроллеров и подобных простых устройств, в которых стоят жёсткие требования к расходу памяти и тактов процессора. Некоторые оптимизирующие компиляторы могут генерировать код, использующий этот алгоритм.
Однако на современных ЦП XOR-техника значительно медленнее, чем использование временной переменной для обмена. Это происходит по причине распараллеливания выполнения команд. В XOR-технике операнды всех команд зависят от результатов предыдущих команд, поэтому они должны быть выполнены в строго последовательном порядке. В каждом конкретном случае рекомендуется протестировать скорости обеих альтернатив на целевой архитектуре.
Если позволяет язык, детали алгоритма должны быть скрыты внутри макроса или инлайн-функции. Это не только делает код чище, но и также позволяет переключиться на другую процедуру обмена, если она быстрее.
Эта уловка также может быть использована, если вы пытаетесь выиграть Obfuscated C Code Contest.
Машины с аппаратной поддержкой обмена
В настоящем коде необходимость обмена содержимого двух переменных встречается часто. По меньшей мере одна машина позволяла это делать в 1970 году. Datacraft (позднее Harris) 6024 серии обеспечивала такую возможность, избегая необходимости в использовании любого алгоритма. Инструкции обменивали содержимое любых регистров за один такт. Другая машина, PDP-6, имела такую возможность ещё в 1964; её инструкция EXCH могла обменивать содержимое любого регистра с содержимым любого участка памяти или другого регистра. Процессоры
Если бы в
См. также
- Симметричное различие
- Xor
- XOR-связный список
- Копирование y во временное хранилище (
Wikimedia Foundation. 2010.