Алгоритм XOR SWAP

Изменено: . Разместил: FadeDemon | Меню
Количество просмотров2`034 / FD842-6-0

Вы когда-нибудь задумывались над способами, которыми можно обменять значения двух переменных местами? Я почти уверен, что если задумаетесь, то ваше воображение рисовало третью переменную, в которую мы сначала положим значение первой, потом первую перезапишем второй, и временное значение положим во вторую. Примерно так. Ну, можно еще функцию, например, сделать, которая сама будет разрешать все эти тонкости. И в этом совершенно ничего нет плохого, но…


…А теперь, внимание, вопрос: а можно ли обменять значение двух переменных так, чтобы третью явно или косвенно не использовать?


Оказывается, можно. И сделать это можно с помощью... (сюрприз!) трёх операций побитового XOR. Причем, в языках вроде Си, Делфи или Паскаля, обмениваемое значение может быть любое (целое число, вещественное, указатель, даже при некоторых ухищрениях массив): операции XOR без разницы, чьими битами оперировать.


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


Код: C++
A = A ^ B;
B = B ^ A;
A = A ^ B;

И что меня по началу поразило, это на самом деле работает. А секрет на самом деле прост, распишем по шагам:


1. В переменную A записывается результат побитового исключающего ИЛИ переменной A с переменной B. А означает это, что в A все биты, которые в B были единичками – инвертируются. То-есть, в A как-бы есть частички обоих переменных (эк я грубо выразился).


2. В B записывается результат A XOR B, а это значит... Что у нас в A? Там у нас предыдущий результат A XOR B, а если мы сделаем с этим результатом еще раз XOR B, то этим действием, из этого результата часть доставшую от B мы выпилим (поскольку все знаем, что X XOR X = 0). В результате, в B попадает то, что изначально было в A, в совершено девственной, нетронутой форме. Мистика.


3. Ну и продолжая мысль, переменной A снова присваиваем A XOR B, и делаем это зачем? А затем, чтобы из A выбить ненужную нам частичку, XORнув ее, так сказать, с B, в котором у нас первоначальное значение A, и как следствие, мы получим первоначальное значение B.


После всех этих манипуляций, с очень удивлённым лицом мы можем заметить, что переменные таки на самом деле поменялись местами. Сразу это понять сложно, у меня лично вызвало ассоциацию с квантовой механикой, где A играла роль этакой квантово-сцепленной пары, исключая ненужные части которой, мы получали нужные.


На ассемблере, это выглядит еще элегантнее (обмениваем в данном случае регистры eax и edx):


Код:
xor eax, edx
xor edx, eax
xor eax, edx

А для Си-подобных языков (и самого Си в том числе) существует еще и однострочная конструкция:


Код: C++
x ^= (y ^= (x ^= y));

Надо заметить, что в наше время такой алгоритм можно использовать разве что в случаях, когда реально нет возможности использовать третью переменную, да на древних микроконтроллерах, в которых нету аналогов инструкции XCHG, позволяющей обменивать содержимое двух регистров (такая команда есть в x86), или в соревнованиях по непонятливости кода. Но тем не менее, вау-эффект от познания такой, казалось бы элементарной вещи, особенно если раньше вы о ней не догадывались, может заставить вашу челюсть столкнуться с клавиатурой. Лично моя челюсть, не удержалась…

QR-код
Интересное
Паяльная станция из спичек и желудей В общем, взглянув задумчиво на свой 40-ваттный паяльник, вспомнив что у меня валяется термопара от сдохшего мультиметра, и накопав в закромах кое-какой хлам, решил я быстренько превратить сей паяльник в некоторое подобие паяльной станции, с удобным миниатюрным жалом, и регулировкой температуры.

Читать »»
Случайные фото