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

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

В программировании, обмен при помощи исключающего ИЛИ (англ. 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(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));

Такая запись, однако, некорректна: она эквивалентна

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

Вычисления левого (x) и правого (y ^= (x ^= y)) операндов операции ^ не упорядочены по отношению друг к другу, причём левый операнд содержит чтение значения переменной x, а правый — связанный с переменной x побочный эффект. Согласно стандартам C/C++, это приводит к неопределённому поведению.

Использование на практике[править | править исходный текст]

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

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

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

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

Следует быть внимательным при реализации функции XOR swap, принимающей указатели или ссылки. Если такая функция будет вызвана с одинаковыми аргументами, произойдет не обмен, а обнуление данных.[1]

Машины с аппаратной поддержкой обмена[править | править исходный текст]

В настоящем коде необходимость обмена содержимого двух переменных встречается часто. По меньшей мере одна машина позволяла это делать в 1970 году. Datacraft (позднее Harris) 6024 серии обеспечивала такую возможность, избегая необходимости в использовании любого алгоритма. Инструкции обменивали содержимое любых регистров за один такт. Другая машина, 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."