§ XOR

Как-то давно я увидел интересный приемчик, который позволяет обменять 2 числа, не используя при этом каких-то специальных возможностей, и дополнительного места в памяти. Алгоритм приводился вот в таком виде:
B = A ^ B
A = A ^ B
B = 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!
Обмен произошел успешно и я это доказал, и рад такому незначительному, но эффектному событию!

§ Пример

Теперь пришло время для того, чтобы показать, что это реально работает:
A = 4
B = 8
B = A ^ B = 4 ^ 8 = 12
A = A ^ B = 4 ^ 12 = 8
B = A ^ B = 8 ^ 12 = 4
То есть на выходе получаем A=8, B=4, хотя на входе было A=4, B=8.
19 фев, 2021
© 2007-2022 Таффи кродеться беспокойно