Как устроен xor обмен

Обменять значения двух переменных местами, что может быть проще.

Обмен с помощью дополнительной переменной

Посмотрим на классический способ, используя дополнительную переменную

Вот как визуально выглядит этот способ

Теперь попробуем сделать тоже, но без дополнительной переменной

Используя сложение

Способ обмена используя сложение выглядит так

Рассмотрим более подробно почему этот способ работает

Мы представили b = a + b - b и a = b + a - a. Точно также можно заменить сложение и вычитание на умножение и деление, хотя такой способ не несет никаких преимуществ, а выполняется дольше.

Используя исключающее или

Еще один способ, который можно часто встретить с помощью операции исключающего или (XOR). Выглядит он так

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

Есть несколько логических оператора в любом языке, особо важные - И и ИЛИ. Выражение с оператором И истинно, когда его левый и правый операнды возвращают true. Я пойду в кино, если будет тепло И будет интересный фильм. Выражение с оператором ИЛИ истинно, когда хотя бы один операнд возвращает true. Я могу доехать до центра на автобусе 9 ИЛИ 51.

Обобщив эти операторы можно с помощью таблицы истинности для and и or

Есть еще один очень полезный оператор - исключающее или. Его особенность в том, что он равен true только тогда, когда операнды разные (true и false, false и true). Это все еще оператор ИЛИ, но он исключает одинаковые значения операндов.

Исключающее или можно применять к 2-м числам, тогда этот оператор будет применен к каждой паре разрядов чисел. Например 10 (в двоичном виде 1010) ^ 6 (в двоичном виде 0110) будет равно 12 (в двоичном виде 1100). Мы производим операцию не над числами, а над каждым разрядом - в данном случае понадобится 4 операции xor.

Посмотрим на некоторые особенности оператора xor

• Идемпотентность. Если применить оператор xor к любому числу и 0, мы получим это число (a ^ 0 = a). Значение разряда числа может быть 0 и 1, при применении 0^0 мы получим 0, а при 1^0 получим 1. Значит итоговое число будет равно не нулевому значению.
• Самообратимость. Если применить оператор xor к одинаковым операндам, мы получим 0 (a ^ a = 0). Это довольно логично, ведь значения на одинаковых разрядах одинаковых чисел равны, значит мы во всем числе получим значения или 0 ^ 0, или 1 ^ 1, результат которых 0.

• Ассоциативность. Если мы возьмем 3 значения (a, b и c) и выполним оператор xor, то порядок чисел будет неважен. Другими словами (a ^ b) ^ c = a ^ (b ^ c). Здесь как и для умножения или сложения. Дело в том, что в данном случае операцию a ^ b ^ c можно представить как остаток от деления на 2 суммы всех значений, или ((a + b + c) % 2) (если вы знакомы с полным сумматором, вы поймете почему). Понятно, что в описанном выше случае порядок суммы неважен и складывать числа в скобках можно в любом порядке.
• Реверсивность. Если мы выполним (a ^ b) ^ b, то получим a. Почему? потому что мы можем заменить (a ^ b) ^ b на a ^ (b ^ b), a (b ^ b) на 0 (самообратимость), также a ^ 0 = a (Идемпотентность).

Этих свойств будет достаточно, чтобы разобраться в обмене с помощью xor.

Представим что у нас есть 2 числа A и B, которые мы хотим поменять местами используя xor. Заметим, что по свойству реверсивности мы можем представить B как B ^ A ^ A.

Intellij idea, например, достаточно умна чтобы подсказать нам:

Точно также мы можем представить A как A ^ B ^ B

Теперь мы имеем

• A = A ^ B ^ B = (A ^ B ) ^ B
• B = B ^ A ^ A = (A ^ B ) ^ A

В обоих выражениях есть A ^ B. Создадим отдельную переменную temp для этого выражения

• temp = A ^ B

теперь

• A = temp ^ B
• B = temp ^ A

Все что осталось, присвоить переменной значение другой переменной

1. сначала запомним temp = A ^ B
2. Значению В присваиваем значение А: B = temp ^ B. Теперь в В лежит значение А.
3. присваиваем А значение В: A = temp ^ A

Выглядит все это так

Остался один момент. Мы использовали временную переменную temp, без которой хотелось бы обойтись. Мы можем записать temp изначально в А. Посмотрим как это выглядит

1. сначала запомним temp в А: A = A ^ B
2. Значению В присваиваем значение А: B = А ^ B (напомню, в А сейчас находится A ^ B, в В - В, в итоге получаем (A ^ B) ^ (B)). Теперь в В лежит значение А
3. присваиваем А значение В. Но тут не все так очевидно. Сейчас А содержит (А ^ B), В содержит А (предыдущий шаг). Значит нам нужно опять выполнить A ^ B, Мы получим A ^ B, где на самом деле выполнится (A ^ B) ^ (A).

Выглядит это так

Второй вывод показывает, что А ^ В = 15. Да, возможно это выглядит запутанно, но все логично и каждое следующее утверждение вытекает из предыдущего.

Заключение

Обмен с помощью xor оператора стоит на 4 принципах оператора xor:

• идемпотентность
• самообратимость
• ассоциативность
• реверсивность