XOR交换算法
目录
XOR交换算法
在计算机编程中，独占或交换（有时简称为XOR交换）是一种使用独占或位操作来交换两个变量的值的算法，而不使用通常需要的临时变量。该算法主要是一种新奇的做法，也是展示独占或运算特性的一种方式。它有时被当作程序优化来讨论，但几乎没有任何情况下，通过排他性操作的交换会比标准的、明显的技术带来好处。
XOR交换算法的算法
传统的互换需要使用一个临时存储变量。然而，使用XOR交换算法，就不需要临时存储。该算法如下。请注意，在某些架构上，XOR指令的xxx个操作数指定了操作结果的目标位置，从而阻止了这种互换性。该算法通常对应于三条机器码指令，在下表中的三行中用相应的伪码和汇编指令表示。在上面的System/370汇编代码示例中，R1和R2是不同的寄存器，每个XR操作将其结果留在xxx个参数中命名的寄存器中。使用x86汇编，X和Y的值在寄存器eax和ebx中（分别），xor将操作结果放在xxx个寄存器中。
然而，在伪代码或高级语言版本或实现中，如果x和y使用相同的存储位置，则算法失败，因为存储在该位置的值将被xxx条XOR指令清零，然后保持为零；它不会与自身互换。这与x和y有相同的值是不一样的。只有当x和y使用相同的存储位置时才会出现问题，在这种情况下，它们的值必须已经相等。也就是说，如果x和y使用相同的存储位置，那么这一行。X:=XORY将x设为零（因为x=y，所以XXORY为零），并将y设为零（因为它使用相同的存储位置），导致x和y失去它们的原始值。
正确性证明
在长度为N的比特串上的二进制操作XORN上的二进制操作表现出以下特性（这里指的是假设我们有两个不同的寄存器R1和R2，初始值分别为A和B。
我们依次进行下面的操作，并利用上面列出的属性还原我们的结果。
线性代数解释
由于XOR可以解释为二进制加法，一对比特可以解释为场上二维矢量空间中的一个矢量，有两个元素，所以算法中的步骤可以解释为场上2×2矩阵的乘法，有两个元素。为简单起见，最初假设x和y都是单比特，而不是比特向量。为了推广到X和Y不是单一比特，而是长度为n的比特向量，这些2×2的矩阵被2n×2n的块状矩阵所取代，而不是对变量（有存储位置）进行操作的，因此这种解释抽象了存储位置的问题，也抽象了变量的问题。