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

StackOverflow https://stackoverflow.com/questions/249423

Вопрос

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

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

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

Это было полезно?

Решение

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

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

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

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

Допустим, вы начинаете с х = 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!

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

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

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

Большинство людей меняют местами две переменные 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), чтобы получить этот & # 8220; гибрид & # 8221; и мы храним его обратно в х. XOR - отличный способ сохранить информацию, потому что вы можете удалить ее, выполнив XOR снова.

     

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

     

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

<Ч>
  

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

ADD 3 A // add 3 to register A
  

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

     

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

     

Поскольку мы не привыкли думать о плохом, пренебрегаемом АЛУ, своп XOR кажется волшебным, поскольку в нем нет явной временной переменной. Некоторые машины имеют одношаговую команду обмена 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 - это коммутативный итак , 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 ассоциативен
= a 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 выше)

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top