WikiSort.ru - Не сортированное

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 25 ноября 2013 года.

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

Примеры кода

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания