Введение
Бинарный арифметический алгоритм
В компьютерном программировании, обмен с использованием исключающего ИЛИ (иногда сокращенно XOR swap) — это алгоритм, использующий битовую операцию исключающего ИЛИ для обмена значениями двух переменных без использования временной переменной, которая обычно необходима. Алгоритм представляет собой, прежде всего, курьезность и способ демонстрации свойств операции исключающего ИЛИ. Иногда его обсуждают как оптимизацию программы, но практически нет случаев, когда обмен с помощью исключающего ИЛИ дает преимущество перед стандартным, очевидным способом.
Причины избегания на практике
На современных архитектурах процессоров техника XOR может оказаться медленнее, чем использование временной переменной для обмена значениями. По крайней мере, на современных процессорах x86 от AMD и Intel, перемещение данных между регистрами обычно не вносит задержек. (Это называется оптимизацией MOV, исключающей перемещения.) Даже если нет доступных архитектурных регистров, инструкция XCHG будет как минимум такой же быстрой, как три операции XOR, выполненные последовательно. Дополнительная причина заключается в том, что современные процессоры стремятся выполнять инструкции параллельно, используя конвейерную обработку. В технике XOR входные данные каждой операции зависят от результатов предыдущей, поэтому они должны выполняться строго последовательно, что сводит на нет преимущества параллелизма на уровне инструкций.
Алиасинг
Обмен с использованием XOR также усложняется на практике из-за псевдонимов. Если предпринята попытка обменять содержимое какой-либо ячейки памяти с самой собой, то эта ячейка будет обнулена, и её значение будет потеряно. Поэтому обмена с использованием XOR не следует применять бездумно в языках высокого уровня, если существует вероятность псевдонимов. Эта проблема не возникает, когда данный метод используется в ассемблере для обмена содержимым двух регистров. Аналогичные проблемы возникают при передаче аргументов по имени, как, например, в устройстве Дженсена, где обмен переменных i и A[i] через временную переменную приводит к неверным результатам из-за взаимосвязи аргументов: обмен через temp = i; i = A[i]; A[i] = temp изменяет значение i во втором операторе, что затем приводит к использованию неверного значения i для A[i] в третьем операторе.
Заявление о регистрации распределения
На архитектурах, не имеющих выделенной инструкции обмена, поскольку она позволяет избежать использования дополнительного временного регистра, алгоритм обмена с помощью XOR необходим для оптимального распределения регистров. Это особенно важно для компиляторов, использующих статическую форму однозначного присваивания для распределения регистров; такие компиляторы иногда генерируют программы, которым требуется поменять значения двух регистров, когда нет доступных регистров. Алгоритм обмена с помощью XOR позволяет избежать необходимости резервирования дополнительного регистра или сброса каких-либо регистров в основную память. Для той же цели можно также использовать вариант с сложением/вычитанием. Этот метод распределения регистров особенно актуален для компиляторов шейдеров GPU. На современных архитектурах GPU сброс переменных в память обходится дорого из-за ограниченной пропускной способности и высокой задержки памяти, в то время как ограничение использования регистров может повысить производительность благодаря динамическому разделению файла регистров. Поэтому алгоритм обмена с помощью XOR требуется некоторым компиляторам GPU.