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.
L'algoritmo
modificaLo 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.
Note
modifica- ^ Bit Twiddling Hacks, su graphics.stanford.edu. URL consultato il 16 febbraio 2025.
