Как работает переопределение переменных 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) 

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

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 для любых х,

y2 = x0 
x2 = y0 

И замена делается.

Answer 2

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

tmp = x 
x = y 
y = tmp 

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

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

Подробнее подробнее в Swap two variables using XOR

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

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

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

---

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

ADD 3 A // add 3 to register A 

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

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

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

Answer 3

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

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 4

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

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

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

Answer 5

@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 6

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

а '= а XOR B (1)
Ь' = а»исключающее б (2)
а» = а»XOR Ь»(3)

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

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

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

Ь»= (а ​​XOR б) XOR б
= а XOR (б XOR б) потому, что XOR ассоциативно
= а XOR 0 из [4] выше
= а за счет определения XOR (см 1 выше)

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

а»= (а ​​исключающее ИЛИ б) XOR A
= (b XOR a) XOR a, поскольку XOR является comm utative
= Ь XOR (а исключающее а), так как исключающее ИЛИ ассоциативно
= B XOR 0 из [4] выше
= Ь в связи с определением XOR (см 1 выше)

Более подробная информация здесь : Necessary and Sufficient

Answer 7

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

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

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

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

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

Answer 8

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

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. Так как исключающая коммутативность х^х = 0 и х^0 = х, это довольно легко увидеть, так как

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

и

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

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

Answer 9

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

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

 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!