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的塊狀矩陣所取代，而不是對變量（有存儲位置）進行操作的，因此這種解釋抽象了存儲位置的問題，也抽象了變量的問題。