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

Материал из Википедии — свободной энциклопедии

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

Содержание 1 Алгоритм 2 Ловушка 3 Примеры кода 3.1 Object Pascal 3.2 C 4 Использование на практике 5 Машины с аппаратной поддержкой обмена 6 См. также

[править] Алгоритм

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

Если бы в PDP-11 такая инструкция была включена, то возможно, что язык Си имел бы возможность обмена переменных как основной бинарный оператор.

[править] См. также

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