Scambio tramite XOR

Nella programmazione, lo scambio tramite XOR (in inglese XOR swap) è un algoritmo che utilizza l'operazione bit a bit di disgiunzione esclusiva per scambiare i valori di due variabili senza utilizzare una variabile temporanea, normalmente necessaria.

Utilizzo dell'algoritmo di scambio tramite XOR per scambiare due nibble tra due variabili senza utilizzare una terza variabile

L'algoritmo

Lo scambio convenzionale richiede l'uso di una variabile temporanea in cui mettere il valore, tuttavia utilizzando lo scambio tramite XOR questa non è necessaria. L'algoritmo è il seguente^[1]:

X := Y XOR X;
Y := X XOR Y;
X := Y XOR X;

Poiché l'XOR è un'operazione commutativa, sia X XOR Y che Y XOR X possono essere utilizzati in modo intercambiabile in una qualsiasi delle tre righe precedenti. Si noti che in alcune architetture il primo operando dell'istruzione XOR specifica la posizione di destinazione in cui viene memorizzato il risultato dell'operazione, impedendo questa intercambiabilità. L'algoritmo corrisponde in genere a tre istruzioni in codice macchina, rappresentate dalle istruzioni, in pseudocodice o assembly, riportate nelle tre righe della seguente tabella:

Pseudocodice	Assembly IBM System/370	Assembly x86	Assembly RISC-V
X := X XOR Y	XR R1,R2	xor eax, ebx	xor x10, x11
Y := Y XOR X	XR R2,R1	xor ebx, eax	xor x11, x10
X := X XOR Y	XR R1,R2	xor eax, ebx	xor x10, x11

Nell'esempio in assembly System/370, R1 ed R2 sono registri distinti e ogni operazione XR salva il suo risultato nel registro indicato come primo argomento. Utilizzando l'assembly x86, i valori X e Y si trovano rispettivamente nei registri eax ed ebx, mentre xor inserisce il risultato dell'operazione nel primo registro. Nell'assembly RISC-V, i valori X e Y sono nei registri X10 e X11, e xor salva il risultato dell'operazione nel primo registro (come nell'esempio dell'assembly x86)

Tuttavia, in tutte le versioni, l'algoritmo fallisce se X e Y utilizzano la stessa posizione di memoria, poiché il valore archiviato in tale posizione verrà azzerato dalla prima istruzione xor e poi rimarrà uguale a zero; non verrà "scambiato con se stesso". Ciò non equivale a dire che X e Y hanno gli stessi valori, significa solo che il problema si verifica solo quando X e Y utilizzano la stessa posizione di memoria, nel qual caso i loro valori devono essere già uguali. Vale a dire, se X e Y utilizzano la stessa posizione di memoria, allora la riga:

X := X XOR Y

imposta X su zero (perché X = Y, quindi X XOR Y è zero) e imposta Y su zero (poiché utilizza la stessa posizione di memoria), facendo sì che X e Y perdano i loro valori originali.