Как работает замена переменных XOR?

Question

Может кто-нибудь объяснить мне, как работает обмен XOR двух переменных без временной переменной?

void xorSwap (int *x, int *y)
{
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

Я понимаю, ЧТО это делает, но может ли кто-нибудь рассказать мне о том, как это работает?

Answer 1

Вы можете увидеть, как это работает, выполнив подстановку:

x1 = x0 xor y0
y2 = x1 xor y0
x2 = x1 xor y2

Подставив

x1 = x0 xor y0
y2 = (x0 xor y0) xor y0
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0)

Поскольку xor полностью ассоциативен и коммутативен:

y2 = x0 xor (y0 xor y0)
x2 = (x0 xor x0) xor (y0 xor y0) xor y0

С x xor x == 0 для любого х,

y2 = x0 xor 0
x2 = 0 xor 0 xor y0

А поскольку x xor 0 == x для любого х,

y2 = x0
x2 = y0

И обмен сделан.

Answer 2

Другие люди объяснили это, теперь я хочу объяснить, почему это была хорошая идея, но сейчас это не так.

В те времена, когда у нас были простые одно- или многоцикловые процессоры, этот трюк был дешевле, чтобы избежать дорогостоящих разыменований памяти или разливов регистров в стек. Однако теперь у нас есть процессоры с массивными конвейерами. Конвейер P4 варьировался от 20 до 31 (или около того) этапов в своих конвейерах, где любая зависимость между чтением и записью в регистр могла привести к остановке всего этого. У свопа xor есть несколько очень сильных зависимостей между A и B, которые на самом деле не имеют значения, но на практике тормозят конвейер. Остановленный конвейер вызывает медленный путь к коду, и если этот обмен происходит в вашем внутреннем цикле, вы будете двигаться очень медленно.

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

Answer 3

Мне нравится думать об этом графически, а не численно.

Допустим, вы начинаете с х = 11 и у = 5 В двоичном формате (и я собираюсь использовать гипотетическую 4-битную машину), здесь x и y

       x: |1|0|1|1|   -> 8 + 2 + 1
       y: |0|1|0|1|   -> 4 + 1

Теперь для меня XOR - это инвертированная операция, и выполнение ее дважды - это зеркало:

     x^y: |1|1|1|0|
 (x^y)^y: |1|0|1|1|   <- ooh!  Check it out - x came back
 (x^y)^x: |0|1|0|1|   <- ooh!  y came back too!

Answer 4

Вот тот, который должно быть немного легче, чтобы впасть:

int x = 10, y = 7;

y = x + y; //x = 10, y = 17
x = y - x; //x = 7, y = 17
y = y - x; //x = 7, y = 10

Теперь можно немного легче понять трюк XOR, если понять, что ^ можно представить как + или - . Так же, как:

x + y - ((x + y) - x) == x 

, так:

x ^ y ^ ((x ^ y) ^ x) == x

Answer 5

Причина, по которой это работает, в том, что XOR не теряет информацию. Вы можете сделать то же самое с обычным сложением и вычитанием, если можете игнорировать переполнение. Например, если пара переменных A, B изначально содержит значения 1,2, вы можете поменять их местами следующим образом:

 // A,B  = 1,2
A = A+B // 3,2
B = A-B // 3,1
A = A-B // 2,1

Кстати, есть старая хитрость для кодирования двухстороннего связанного списка в одном «указателе». Предположим, у вас есть список блоков памяти по адресам A, B и C. Первое слово в каждом блоке, соответственно:

 // first word of each block is sum of addresses of prior and next block
 0 + &B   // first word of block A
&A + &C   // first word of block B
&B + 0    // first word of block C

Если у вас есть доступ к блоку A, он дает вам адрес B. Чтобы добраться до C, вы берете «указатель» в B и вычитаете A, и так далее. Это работает так же хорошо назад. Чтобы бегать по списку, вам нужно сохранить указатели на два последовательных блока. Конечно, вы бы использовали XOR вместо сложения / вычитания, поэтому вам не придется беспокоиться о переполнении.

Вы можете распространить это на "связанную сеть", если хотите повеселиться.

Answer 6

Большинство людей меняют местами две переменные x и y, используя временную переменную, например:

tmp = x
x = y
y = tmp

Вот изящный трюк программирования, чтобы поменять два значения без необходимости использовать временную температуру:

x = x xor y
y = x xor y
x = x xor y

Подробнее в Поменяйте местами две переменные, используя XOR

В строке 1 мы объединяем x и y (используя XOR), чтобы получить этот «гибрид», и сохраняем его обратно в x. XOR - отличный способ сохранить информацию, потому что вы можете удалить ее, выполнив XOR снова.

В строке 2. Мы XOR гибрид с y, который аннулирует всю информацию y, оставляя нас только с x. Мы сохраняем этот результат обратно в y, так что теперь они поменялись местами.

В последней строке x по-прежнему имеет гибридное значение. Мы снова сделаем XOR с помощью y (теперь с исходным значением x), чтобы удалить все следы x из гибрида. Это оставляет нас с y, и обмен завершен!

---

На самом деле компьютер имеет неявную переменную «temp», в которой хранятся промежуточные результаты перед их записью в регистр. Например, если вы добавляете 3 в регистр (в псевдокоде на машинном языке):

ADD 3 A // add 3 to register A

АЛУ (Арифметическая Логическая Единица) - это то, что выполняет инструкцию 3 + А. Он принимает входные данные (3, A) и создает результат (3 + A), который CPU затем сохраняет обратно в исходный регистр A. Таким образом, мы использовали АЛУ в качестве временного пустого места до того, как получили окончательный ответ.

Мы принимаем неявные временные данные АЛУ как должное, но они всегда есть. Аналогичным образом, ALU может вернуть промежуточный результат XOR в случае x = x xor y, после чего центральный процессор сохраняет его в исходном регистре x.

Поскольку мы не привыкли думать о плохом, пренебрегаемом АЛУ, своп XOR кажется волшебным, потому что у него нет явной временной переменной. Некоторые машины имеют одношаговую команду XCHG для обмена двумя регистрами.

Answer 7

@ VonC правильно, это изящный математический прием. Вообразите 4-битные слова и посмотрите, поможет ли это.

word1 ^= word2;
word2 ^= word1;
word1 ^= word2;


word1    word2
0101     1111
after 1st xor
1010     1111
after 2nd xor
1010     0101
after 3rd xor
1111     0101

Answer 8

В принципе, в подходе XOR есть 3 шага:

a ’= a XOR b (1)
b ’= a’ XOR b (2)
a ”= a’ XOR b ’(3)

Чтобы понять , почему это работает, сначала отметьте, что:

1. XOR выдаст 1, только если ровно один из его операндов равен 1, а другой равен нулю;
2. XOR является коммутативным , поэтому a XOR b = b XOR a;
3. XOR является ассоциативным , поэтому (a XOR b) XOR c = a XOR (b XOR c); и
4. a XOR a = 0 (это должно быть очевидно из определения в 1 выше)

После шага (1) двоичное представление a будет иметь 1 бит только в тех битовых позициях, где a и b имеют противоположные биты. Это либо (ak = 1, bk = 0), либо (ak = 0, bk = 1). Теперь, когда мы выполняем замену на шаге (2), мы получаем:

b ’= (a XOR b) XOR b
= a XOR (b XOR b), потому что XOR ассоциативен
= XOR 0 из-за [4] выше
= a из-за определения XOR (см. 1 выше)

Теперь мы можем подставить в шаг (3):

a ”= (a XOR b) XOR a
= (b XOR a) XOR a, потому что XOR коммутативен
= b XOR (a XOR a), потому что XOR является ассоциативным
= b XOR 0 из-за [4] выше
= b из-за определения XOR (см. 1 выше)

Более подробная информация здесь: Необходимые и достаточные

Answer 9

В качестве примечания я несколько лет назад заново изобрел это колесо самостоятельно в виде замены целых чисел, выполнив:

a = a + b
b = a - b ( = a + b - b once expanded)
a = a - b ( = a + b - a once expanded).

(это упомянуто выше трудным для чтения способом),

Точно такие же рассуждения применимы к xor-свопам: a ^ b ^ b = a и a ^ b ^ a = a. Поскольку xor коммутативен, x ^ x = 0 и x ^ 0 = x, это довольно легко увидеть, поскольку

= a ^ b ^ b
= a ^ 0
= a

и

= a ^ b ^ a 
= a ^ a ^ b 
= 0 ^ b 
= b

Надеюсь, это поможет. Это объяснение уже было дано ... но не очень четко имо.