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

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

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

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

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

допустим, вы начинаете с 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 = 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 вместо сложения/subtration, поэтому вам не придется беспокоиться о переполнении.

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

большинство людей поменяли бы две переменные 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, после чего процессор сохраняет его в исходном регистре X.

поскольку мы не привыкли думать о бедных, забытых ALU, своп XOR кажется волшебным, потому что у него нет явной временной переменной. Некоторые машины имеют 1-ступенчатую инструкцию exchange 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

в основном есть 3 шага в подходе XOR:

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 это ассоциативные так (исключающее или б) исключающее ИЛИ с = исключающее ИЛИ (XOR с Б С); и
4. A XOR a = 0 (это должно быть очевидно из определения в 1 выше)

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

b ' = (A XOR b) XOR b
= исключающее ИЛИ (XOR с б б) потому что XOR ассоциативен
= A XOR 0 из-за [4] выше
= a из-за определения XOR (см. 1 выше)

теперь мы можем заменить в Шаг (3):

a " = (a XOR b) XOR a
= (б гаммирования а) исключающее ИЛИ исключающее ИЛИ, а потому является коммутативной
= b XOR (A XOR a) потому что XOR ассоциативно
= b XOR 0 из-за [4] выше
= b из-за определения XOR (см. 1 выше)

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

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

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

надеюсь, что это помогает. Это объяснение уже с учетом... но не очень четко ИМО.