§ XOR

Как-то давно я увидел интересный приемчик, который позволяет обменять 2 числа, не используя при этом каких-то специальных возможностей, и дополнительного места в памяти. Алгоритм приводился вот в таком виде:

1B = A ^ B
2A = A ^ B
3B = A ^ B

Все это интересно, но я решил докопаться до истины и понять, почему этот алгоритм вообще работает. Все оказалось намного проще, чем бы я мог подумать и вот почему. Дело в том, что XOR обладает одной уникальной возможностью:
X ^ X = 0
Где X - это любое число. Получается, что применяя таким образом XOR, можно обнулять значения. А это удобно!

§ Вывод

Тогда приступим. Первый шаг алгоритма дает следующее:

• B = A ^ B

В данном случае ничего особенного. Просто присвоили новому значению B результат A xor B и все. Но дальше уже начинается та самая магия, о которой много пишут в художественных книгах про героев:

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

А поскольку B у нас было ранее A ^ B, то получается, что A принимает на самом деле значение B, а не A. То есть уже виден процесс обмена значениями!
И все завершает последний штрих:

• B = A ^ B

Дело в том, что в A сейчас на самом деле хранится не A, а B, а как мы помним, в B хранится A ^ B:

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

То есть B ^ B успешно аннулируется и получается, что по итогу в B будет хранится A!
Обмен произошел успешно и я это доказал, и рад такому незначительному, но эффектному событию!

§ Пример

Теперь пришло время для того, чтобы показать, что это реально работает:

1A = 4
2B = 8
3B = A ^ B = 4 ^ 8 = 12
4A = A ^ B = 4 ^ 12 = 8
5B = A ^ B = 8 ^ 12 = 4

То есть на выходе получаем A=8, B=4, хотя на входе было A=4, B=8.