Как работает переопределение переменных XOR?

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

 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 для любого x,

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

А так как x xor 0 == x для любого x,

 y2 = x0 x2 = y0 

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

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

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

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

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

Предположим, вы начинаете с x = 11 и y = 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! 

Вот один из них, который должен быть немного проще:

 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 

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

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

BTW есть старый трюк для кодирования двухстороннего связанного списка в одном «указателе». Предположим, у вас есть список блоков памяти по адресам 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 вместо добавления / субтракции, поэтому вам не пришлось бы беспокоиться о переполнении.

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

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

 tmp = x x = y y = tmp 

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

 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 

ALU (Арифметическая логическая единица) на самом деле выполняет команду 3 + A. Он принимает входы (3, A) и создает результат (3 + A), который затем сохраняется в исходном регистре A. Итак, мы использовали ALU как временное пространство для царапин, прежде чем мы получили окончательный ответ.

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

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

@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 

В основном подход XOR состоит из 3 шагов:

a ‘= a XOR b (1)
b ‘= a’ XOR b (2)
a “= a ‘XOR b’ (3)

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

1. XOR будет производить 1, только если один из его операндов равен 1, а другой равен нулю;
2. XOR является коммутативным, поэтому XOR b = b XOR a;
3. XOR ассоциативно, поэтому (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 ассоциативно
= a XOR 0 из-за [4] выше
= a из-за определения XOR (см. выше)

Теперь мы можем заменить на Шаг (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 (см. выше)

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

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

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

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

Точно такие же рассуждения применимы к xor swaps: 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 

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