XORvariables交换如何工作？
有人可以向我解释如何交换两个variables没有临时variables的作品？
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
交换完成。
其他人已经解释了，现在我想解释一下为什么这是一个好主意，但现在不是。
早在我们有简单的单周期或多周期CPU的时候，使用这个技巧便宜得多，以避免代价高昂的内存失效或溢出寄存器到堆栈。 但是，我们现在拥有大规模pipe道的CPU。 P4的pipe道范围从他们的pipe道中有20到31（或者更多）的阶段，在这个阶段，读写寄存器之间的任何依赖都可能导致整个事情停顿。 xor swap在A和B之间有一些非常重要的依赖关系，实际上根本没有关系，但是在实践中会拖延pipe道。 停滞的pipe道会导致代码path变慢，如果这个交换在你的内部循环中，你将会非常缓慢地移动。
在一般的实践中，你的编译器可以找出当你用tempvariables进行交换时你真正想要做什么，并且可以把它编译成一个XCHG指令。 使用xor swap会使编译器难以猜测你的意图，因此不太可能正确地优化它。 代码维护等等
我喜欢用graphics而不是数字来思考它。
假设你以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不会丢失信息。 如果你可以忽略溢出，你可以用普通的加法和减法来做同样的事情。 例如，如果variables对A，B最初包含值1,2，则可以像这样交换它们：
// A,B = 1,2 A = A+B // 3,2 B = AB // 3,1 A = AB // 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来代替添加/修饰，所以你不必担心溢出。
如果你想获得一些乐趣，你可以把它扩展到一个“链接的networking”。
大多数人会使用临时variables交换两个variablesx和y，如下所示：
tmp = x x = y y = tmp
这是一个简洁的编程技巧，可以在不需要温度的情况下交换两个值：
x = x xor y y = x xor y x = x xor y
在使用XOR交换两个variables的更多细节
在第一行，我们结合x和y（使用异或）来获得这个“混合”，我们把它存回x。 XOR是保存信息的好方法，因为您可以通过再次执行XOR来移除它。
在第二行。我们用y来异或混合，这就消除了所有的y信息，只剩下x。 我们把这个结果保存到y中，所以现在他们已经交换了。
在最后一行，x仍然具有混合价值。 我们再次用y（现在用x的原始值）对它进行异或运算，以消除混合中的所有x的痕迹。 这使我们与Ÿ，交换完成！
计算机实际上有一个隐含的“临时”variables，在将其写回寄存器之前存储中间结果。 例如，如果将3添加到寄存器（以机器语言伪代码）：
ADD 3 A // add 3 to register A
ALU（算术逻辑单元）实际上是执行指令3 + A的东西。 它将input（3，A）并创build一个结果（3 + A），然后CPU将其存储回A的原始寄存器。 所以，在我们做出最终答案之前，我们使用ALU作为暂时的临时空间。
我们把ALU隐含的临时数据视为理所当然，但总是存在的。 以类似的方式，ALU可以在x = x xor y的情况下返回XOR的中间结果，此时CPU将其存储在x的原始寄存器中。
因为我们不习惯考虑穷人，忽略了ALU，XOR交换看起来很神奇，因为它没有明确的临时variables。 有些机器有一步交换XCHG指令交换两个寄存器。
@VonC是对的，这是一个整洁的math技巧。 想象一下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方法有三个步骤：
a'= a XOR b（1）
b'= a'XOR b（2）
a“= a'XOR b'（3）
要理解为什么这个工作首先注意到：
- 只有当它的一个操作数是1，另一个是零时，XOR才会产生1。
- XOR是可交换的，所以XOR b = b XOR a;
- XOR是关联的 （a XOR b）XOR c = a XOR（b XOR c）; 和
- XOR a = 0（这应该从上面1中的定义中显而易见）
在步骤（1）之后，a的二进制表示仅在a和b具有相反位的位置处具有1位。 即（ak = 1，bk = 0）或（ak = 0，bk = 1）。 现在当我们在步骤（2）中进行replace时，我们得到：
b'=（a XOR b）XOR b
= XOR（b XOR b），因为XOR是关联的
=因为上面的[4] XOR 0
=由于XOR的定义（见上面1 ）
现在我们可以代入步骤（3）：
a“=（a XOR b）XOR a
=（b XOR a）XOR a，因为XOR是可交换的
= b XOR（一个XOR a），因为XOR是关联的
= b因为上面的[4]，XOR 0
= b由于定义异或（见上面1 ）
更详细的信息在这里： 必要和充足
作为一个侧面说明，我几年前以交换整数的forms独立地重新devise了这个方法：
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
希望这可以帮助。 这个解释已经被给出了，但是不是很清楚。
