Алгоритм обмена при помощи исключающего ИЛИ

В программировании, обмен при помощи исключающего ИЛИ (англ. 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 Y и X и сохраняем в Y
3. XOR X и Y и сохраняем в X

Алгоритм выглядит проще, когда записан в псевдокоде.

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

Примеры кода

Object Pascal

Процедура на Object Pascal для обмена двух целых, используя алгоритм обмена с исключающим ИЛИ:

procedure XorSwap(var X, Y: Integer);
begin
  X := X xor Y;
  Y := Y xor X;
  X := X xor Y;
end;

Надо заметить, что эта функция не будет работать, если мы попытаемся обменять переменную саму с собой.

C++

Код на C++ для выполнения:

     void xorSwap(int &x, int &y)
     {
          if (&x == &y) 
             return;
          x ^= y;
          y ^= x;
          x ^= y;
     }

Часто встречаемый однострочник:

x ^= (y ^= (x ^= y));

Java

void xorSwap(int x, int y)
{
 x = x^y;
 y = y^x;
 x = x^y;
}

Использование на практике

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

Однако на современных ЦП XOR-техника значительно медленнее, чем использование временной переменной для обмена. Это происходит по причине распараллеливания выполнения команд. В XOR-технике операнды всех команд зависят от результатов предыдущих команд, поэтому они должны быть выполнены в строго последовательном порядке. В каждом конкретном случае рекомендуется протестировать скорости обеих альтернатив на целевой архитектуре.

Если позволяет язык, детали алгоритма должны быть скрыты внутри макроса или инлайн-функции. Это не только делает код чище, но и также позволяет переключиться на другую процедуру обмена, если она быстрее.

Эта уловка также может быть использована, если вы пытаетесь выиграть Obfuscated C Code Contest.

Машины с аппаратной поддержкой обмена

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

См. также

• Симметричное различие
• Xor
• XOR-связный список