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

В программировании, обмен при помощи исключающего ИЛИ (англ. 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 типа integer, арифметический алгоритм для их обмена таков:

  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-связанный список
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home