Зор-своп алгоритм

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

Алгоритм

Стандартные алгоритмы обмена требуют использования временного хранилища. Интуитивный алгоритм для обмена x и y включает:

1. Копирование  y во временное хранилище (temp ← y)
2. Установка  y значением x (y ← x)
3. Копирование значения из временного хранилища обратно в x. (x ← temp)

Или, если даны две переменные x и y целого типа, арифметический алгоритм для их обмена таков:

1. x := x + y
2. y := x – y
3. x := x – y

Конечно, вышеприведённый алгоритм будет прерываться на системах, которые перехватывают переполнение целого. Используя алгоритм обмена при помощи исключающего ИЛИ, однако, не требуется ни временное хранилище, ни определение переполнения. Алгоритм в данном случае таков (где X и Y — имена переменных, а не значения):

1. XOR X и Y и сохраняем в X
2. XOR X и Y и сохраняем в Y
3. 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-связный список