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

Двоичный арифметический алгоритм

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

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

Алгоритм

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

X := Y XOR X ; // Выполняем операцию XOR над значениями и сохраняем результат в X Y := X XOR Y ; // Выполняем операцию XOR над значениями и сохраняем результат в Y X := Y XOR X ; // Выполняем операцию XOR над значениями и сохраняем результат в X

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

Псевдокод	Сборка IBM System/370	x86 сборка	Сборка RISC-V
`X := X XOR Y`	`XR R1,R2`	`xor eax, ebx`	`xor x10, x11`
`Y := Y XOR X`	`XR R2,R1`	`xor ebx, eax`	`xor x11, x10`
`X := X XOR Y`	`XR R1,R2`	`xor eax, ebx`	`xor x10, x11`

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

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

X := X XOR Y

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

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

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

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

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

Шаг	Операция	Регистрация 1	Регистрация 2	Снижение
0	Начальное значение	$А$	$Б$	—
1	`R1 := R1 XOR R2`	$A\oplus B$	$Б$	—
2	`R2 := R1 XOR R2`	$A\oplus B$	$(A\oplus B)\oplus B=A\oplus (B\oplus B)$ $=A\oplus 0$ $=А$	Л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$ $=Б$	$\ А$	Л1 Л2 Л4 Л3

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

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

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

X := X XOR 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)) /* Не работает, если a и b являются одним и тем же объектом —  в этом случае объекту присваивается ноль \ (0) */ #define XORSWAP(a, b) \  ((&(a) == &(b)) ? (a) /* Проверка на наличие различных адресов */  \   : XORSWAP_UNSAFE(a, b))

Причины избегания на практике

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

Алиасинг

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

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

Вариации

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

void AddSwap ( беззнаковое целое * x , беззнаковое целое * y ) { * x = * x + * y ; * y = * x - * y ; * x = * x - * y ; }

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

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

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

Смотрите также

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

Примечания

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

Ссылки

^ "The Magic of XOR". Cs.umd.edu. Архивировано из оригинала 2014-04-01 . Получено 2014-04-02 .
^ "Обмен значениями с помощью XOR". graphics.stanford.edu . Получено 2014-05-02 .
^ Амарасингхе, Саман; Лейзерсон, Чарльз (2010). "6.172 Performance Engineering of Software Systems, Lecture 2". MIT OpenCourseWare . Массачусетский технологический институт. Архивировано из оригинала 25-01-2015 . Получено 27 января 2015 г.
^ Уоррен, Генри С. (2003). Hacker's delight . Бостон: Addison-Wesley. С. 39. ISBN 0201914654.
^ Перейра, Фернандо Маньо Кинтао; Палсберг, Йенс (2009). «Устранение SSA после распределения регистра» (PDF) . Конструкция компилятора . Конспекты лекций по информатике. Том. 5501. С. 158–173 . doi :10.1007/978-3-642-00722-4_12. ISBN 978-3-642-00721-7. Получено 17 апреля 2022 г. .
^ Хак, Себастьян; Грунд, Дэниел; Гус, Герхард (2006). «Распределение регистров для программ в форме SSA». Конструкция компилятора . Конспект лекций по информатике. Том 3923. С. 247–262 . doi : 10.1007/11688839_20 . ISBN 978-3-540-33050-9.
^ Эбботт, Коннор; Шюрманн, Дэниел. «Распределение регистров на основе SSA для архитектур графических процессоров» (PDF) . Получено 17 апреля 2022 г.

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

[1] "The Magic of XOR". Cs.umd.edu. Архивировано из оригинала 2014-04-01 . Получено 2014-04-02 .

[2] "Обмен значениями с помощью XOR". graphics.stanford.edu . Получено 2014-05-02 .

[4] Амарасингхе, Саман; Лейзерсон, Чарльз (2010). "6.172 Performance Engineering of Software Systems, Lecture 2". MIT OpenCourseWare . Массачусетский технологический институт. Архивировано из оригинала 25-01-2015 . Получено 27 января 2015 г.

[5] Уоррен, Генри С. (2003). Hacker's delight . Бостон: Addison-Wesley. С. 39. ISBN 0201914654.

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

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

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