Алгоритм обмена XOR

В компьютерном программировании исключающая операция или замена (иногда сокращается до XOR swap ) — это алгоритм , который использует исключающую или побитовую операцию для замены значений двух переменных без использования временной переменной, которая обычно требуется.

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

Алгоритм

Обычная замена требует использования временной переменной хранения. Однако при использовании алгоритма подкачки XOR временное хранилище не требуется. Алгоритм следующий: ^[1]^[2]

X := Y XOR X; // XOR the values and store the result in X
Y := X XOR Y; // XOR the values and store the result in Y
X := Y XOR X; // XOR the values and store the result in X

Поскольку XOR является коммутативной операцией , X XOR Y или Y XOR X могут использоваться взаимозаменяемо в любой из трех предыдущих строк. Обратите внимание, что в некоторых архитектурах первый операнд инструкции XOR указывает целевое местоположение, в котором сохраняется результат операции, что предотвращает эту взаимозаменяемость. Алгоритм обычно соответствует трем инструкциям машинного кода , представленным соответствующим псевдокодом и инструкциями ассемблера в трех строках следующей таблицы:

Псевдокод	IBM System/370 Сборка	сборка х86
`X := X XOR Y`	`XR R1,R2`	`xor eax, ebx`
`Y := Y XOR X`	`XR R2,R1`	`xor ebx, eax`
`X := X XOR Y`	`XR R1,R2`	`xor eax, ebx`

В приведенном выше примере ассемблерного кода System/370 R1 и R2 — отдельные регистры , и каждый XR операция оставляет свой результат в регистре, указанном в первом аргументе. При использовании сборки x86 значения X и Y находятся в регистрах eax и ebx (соответственно), а xor помещает результат операции в первый регистр.

Однако в псевдокоде или версии или реализации на языке высокого уровня алгоритм дает сбой, если x и y используют одно и то же место хранения, поскольку значение, хранящееся в этом месте, будет обнулено первой инструкцией XOR, а затем останется нулевым; он не будет «поменяться местами сам с собой». Это не то же самое, как если бы x и y имели одинаковые значения. Проблема возникает только тогда, когда x и y используют одно и то же место хранения, и в этом случае их значения уже должны быть равны. То есть, если x и y используют одно и то же место хранения, то строка:

X := X XOR Y

устанавливает x равным нулю (поскольку x = y, поэтому X XOR Y равно нулю) и устанавливает y равным нулю (поскольку он использует одно и то же место хранения), в результате чего x и y теряют свои исходные значения.

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

Бинарная операция XOR над битовыми строками длины $N$ проявляет следующие свойства (где $\oplus$ обозначает XOR): ^[а]

Л1. Коммутативность : $A\oplus B=B\oplus A$
Л2. Ассоциативность : $(A\oplus B)\oplus C=A\oplus (B\oplus C)$
Л3. Идентичность существует : существует битовая строка 0 (длины N ) такая, что $A\oplus 0=A$ для любого $A$
Л4. Каждый элемент является своим обратным : для каждого $A$ , $A\oplus A=0$ .

Предположим, что у нас есть два разных регистра. R1 и R2 как показано в таблице ниже, с начальными значениями A и B соответственно. Мы последовательно выполняем приведенные ниже операции и сокращаем наши результаты, используя перечисленные выше свойства.

Шаг	Операция	Зарегистрироваться 1	Зарегистрироваться 2	Снижение
0	Начальное значение	$A$	$B$	—
1	`R1 := R1 XOR R2`	$A\oplus B$	$B$	—
2	`R2 := R1 XOR R2`	$A\oplus B$	$(A\oplus B)\oplus B=A\oplus (B\oplus B)$ $=A\oplus 0$ $=A$	Л2 Л4 Л3
3	`R1 := R1 XOR R2`	$(A\oplus B)\oplus A=(B\oplus A)\oplus A$ $=B\oplus (A\oplus A)$ $=B\oplus 0$ $=B$	$\ A$	Л1 Л2 Л4 Л3

Интерпретация линейной алгебры

Поскольку XOR можно интерпретировать как двоичное сложение, а пару битов можно интерпретировать как вектор в двумерном векторном пространстве над полем с двумя элементами , шаги алгоритма можно интерпретировать как умножение на матрицы 2×2 над полем с двумя элементами. поле с двумя элементами. Для простоты предположим, что сначала x и y представляют собой отдельные биты, а не битовые векторы.

Например, шаг:

X := X XOR Y

который также имеет неявное:

Y := Y

соответствует матрице $\left({\begin{smallmatrix}1&1\\0&1\end{smallmatrix}}\right)$ как

{\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}={\begin{pmatrix}x+y\\y\end{pmatrix}}.

Тогда последовательность операций выражается так:

{\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}1&0\\1&1\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}

(работаем с двоичными значениями, поэтому $1+1=0$ ), которая выражает элементарную матрицу переключения двух строк (или столбцов) через трансвекции (сдвиги) добавления одного элемента к другому.

Чтобы обобщить ситуацию, когда X и Y являются не отдельными битами, а битовыми векторами длины n , эти матрицы 2 × 2 заменяются 2 n × 2 n, блочными матрицами такими как $\left({\begin{smallmatrix}I_{n}&I_{n}\\0&I_{n}\end{smallmatrix}}\right).$

Эти матрицы работают со значениями, а не с переменными (с местами хранения), поэтому эта интерпретация абстрагируется от проблем места хранения и проблемы того, что обе переменные совместно используют одно и то же место хранения.

Пример кода

Функция C , реализующая алгоритм обмена XOR:

void XorSwap(int *x, int *y) 
{
  if (x == y) return;
  *x ^= *y;
  *y ^= *x;
  *x ^= *y;
}

Код сначала проверяет, различны ли адреса, и использует защитное предложение для досрочного выхода из функции, если они равны. Без этой проверки, если бы они были равны, алгоритм сбрасывался бы в тройку. *x ^= *x в результате получается ноль.

Алгоритм обмена XOR также можно определить с помощью макроса:

#define XORSWAP_UNSAFE(a, b)                                                   \
  ((a) ^= (b), (b) ^= (a),                                                     \
   (a) ^= (b)) /* Doesn't work when a and b are the same object - assigns zero \
                  (0) to the object in that case */
#define XORSWAP(a, b)                                                         \
  ((&(a) == &(b)) ? (a) /* Check for distinct addresses */                    \
                  : XORSWAP_UNSAFE(a, b))

Причины уклонения на практике

В современных архитектурах ЦП метод XOR может быть медленнее, чем использование временной переменной для замены. По крайней мере, на последних процессорах x86, как AMD, так и Intel, перемещение между регистрами регулярно приводит к нулевой задержке. (Это называется устранением MOV.) Даже если нет доступного для использования архитектурного регистра, XCHG Инструкция будет по крайней мере такой же быстрой, как три операции XOR вместе взятые. Другая причина заключается в том, что современные процессоры стремятся выполнять инструкции параллельно через конвейеры команд . В методе XOR входные данные каждой операции зависят от результатов предыдущей операции, поэтому они должны выполняться в строго последовательном порядке, сводя на нет любые преимущества параллелизма на уровне команд . ^[3]

Псевдонимы

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

Аналогичные проблемы возникают при вызове по имени , как и в Jensen's Device , где подкачка i и A[i] через временную переменную дает неправильные результаты из-за связанных аргументов: замена через temp = i; i = A[i]; A[i] = temp меняет значение для i во втором утверждении, что затем приводит к неправильному i ценность для A[i] в третьем заявлении.

Вариации

Основной принцип алгоритма обмена XOR может быть применен к любой операции, соответствующей критериям L1–L4, указанным выше. Замена XOR сложением и вычитанием дает несколько разные, но в основном эквивалентные формулировки. Например: ^[4]

void AddSwap( unsigned int* x, unsigned int* y )
{
    *x = *x + *y;
    *y = *x - *y;
    *x = *x - *y;
}

В отличие от замены XOR, этот вариант требует, чтобы базовый процессор или язык программирования использовали такой метод, как модульная арифметика или большие числа, чтобы гарантировать, что вычисление X + Y не может вызвать ошибку из-за целочисленного переполнения . Поэтому на практике он встречается еще реже, чем обмен XOR.

Однако реализация AddSwap выше на языке программирования C всегда работает даже в случае целочисленного переполнения, поскольку, согласно стандарту C, сложение и вычитание беззнаковых целых чисел следуют правилам модульной арифметики , т.е. выполняются в циклической группе $\mathbb {Z} /2^{s}\mathbb {Z}$ где $s$ это количество битов unsigned int. Действительно, корректность алгоритма следует из того, что формулы $(x+y)-y=x$ и $(x+y)-((x+y)-y)=y$ выполняются в любой абелевой группе . Это обобщает доказательство алгоритма замены XOR: XOR — это одновременно сложение и вычитание в абелевой группе. $(\mathbb {Z} /2\mathbb {Z} )^{s}$ (что является прямой суммой s копий $\mathbb {Z} /2\mathbb {Z}$ ).

Это не справедливо при работе с signed int тип (по умолчанию для int). Переполнение знакового целого числа является неопределенным поведением в C, и поэтому модульная арифметика не гарантируется стандартом, что может привести к неверным результатам.

Последовательность действий в AddSwap может быть выражено через матричное умножение как:

{\begin{pmatrix}1&-1\\0&1\end{pmatrix}}{\begin{pmatrix}1&0\\1&-1\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}

Заявление о регистрации распределения

требуется алгоритм замены XOR В архитектурах, где отсутствует специальная инструкция замены, поскольку она позволяет избежать дополнительного временного регистра, для оптимального распределения регистров . Это особенно важно для компиляторов, использующих статическую форму одиночного присваивания для распределения регистров; эти компиляторы иногда создают программы, которым необходимо поменять местами два регистра, когда ни один из них не свободен. Алгоритм подкачки XOR позволяет избежать необходимости резервировать дополнительный регистр или переносить какие-либо регистры в основную память. ^[5] Вариант сложения/вычитания также можно использовать для той же цели. ^[6]

Этот метод распределения регистров особенно актуален для компиляторов шейдеров графического процессора . В современных архитектурах графических процессоров разделение переменных обходится дорого из-за ограниченной пропускной способности памяти и высокой задержки памяти, тогда как ограничение использования регистров может повысить производительность за счет динамического разделения файла регистров . Поэтому алгоритм замены XOR требуется некоторым компиляторам графического процессора. ^[7]

См. также

Симметричная разница
Связанный список XOR
Шифр Фейстеля (алгоритм обмена XOR представляет собой вырожденную форму шифра Фейстеля)

Примечания

^ Первые три свойства, а также существование обратного для каждого элемента, являются определением абелевой группы . Последним свойством является утверждение, что каждый элемент является инволюцией , то есть имеет порядок 2, что верно не для всех абелевых групп.

Ссылки

^ «Магия XOR» . Cs.umd.edu. Архивировано из оригинала 1 апреля 2014 г. Проверено 2 апреля 2014 г.
^ «Обмен значений с помощью XOR» . Graphics.stanford.edu . Проверено 2 мая 2014 г.
^ Амарасингхе, Саман; Лейзерсон, Чарльз (2010). «6.172 Проектирование производительности программных систем, Лекция 2» . MIT OpenCourseWare . Массачусетский технологический институт. Архивировано из оригинала 25 января 2015 г. Проверено 27 января 2015 г.
^ Уоррен, Генри С. (2003). Хакерское удовольствие . Бостон: Аддисон-Уэсли. п. 39. ИСБН 0201914654 .
^ ПЕРЕЙРА, Фернандо Маньо Кинтао; Палсберг, Йенс (2009). «Удаление SSA после выделения записи» (PDF) . Строительный компилятор . Конспекты лекций по информатике. 5501 : 158–173. дои : 10.1007/978-3-642-00722-4_12 . ISBN 978-3-642-00721-7 . Проверено 17 апреля 2022 г.
^ Хак, Себастьян; Грунд, Дэниел; Гус, Герхард (2006). «Распределение регистров для программ в форме SSA» . Конструкция компилятора . Конспекты лекций по информатике. 3923 : 247–262. дои : 10.1007/11688839_20 . ISBN 978-3-540-33050-9 .
^ Эбботт, Коннор; Шюрманн, Даниэль. «Распределение регистров на основе SSA для архитектур графических процессоров» (PDF) . Проверено 17 апреля 2022 г.

[3] Первые три свойства, а также существование обратного для каждого элемента, являются определением абелевой группы . Последним свойством является утверждение, что каждый элемент является инволюцией , то есть имеет порядок 2, что верно не для всех абелевых групп.

[1] «Магия XOR» . Cs.umd.edu. Архивировано из оригинала 1 апреля 2014 г. Проверено 2 апреля 2014 г.

[2] «Обмен значений с помощью XOR» . Graphics.stanford.edu . Проверено 2 мая 2014 г.

[4] Амарасингхе, Саман; Лейзерсон, Чарльз (2010). «6.172 Проектирование производительности программных систем, Лекция 2» . MIT OpenCourseWare . Массачусетский технологический институт. Архивировано из оригинала 25 января 2015 г. Проверено 27 января 2015 г.

[5] Уоррен, Генри С. (2003). Хакерское удовольствие . Бостон: Аддисон-Уэсли. п. 39. ИСБН 0201914654 .

[6] ПЕРЕЙРА, Фернандо Маньо Кинтао; Палсберг, Йенс (2009). «Удаление SSA после выделения записи» (PDF) . Строительный компилятор . Конспекты лекций по информатике. 5501 : 158–173. дои : 10.1007/978-3-642-00722-4_12 . ISBN 978-3-642-00721-7 . Проверено 17 апреля 2022 г.

[7] Хак, Себастьян; Грунд, Дэниел; Гус, Герхард (2006). «Распределение регистров для программ в форме SSA» . Конструкция компилятора . Конспекты лекций по информатике. 3923 : 247–262. дои : 10.1007/11688839_20 . ISBN 978-3-540-33050-9 .

[8] Эбботт, Коннор; Шюрманн, Даниэль. «Распределение регистров на основе SSA для архитектур графических процессоров» (PDF) . Проверено 17 апреля 2022 г.

[1]

[2]

[а]

[3]

[4]

[5]

[6]

[7]