Xor Swap: scambiare il valore di due variabili senza variabile d'appoggio
Scritto da Andrea Giacomin in Programmazione, tags: C, Java, ProgrammazioneEvidentemente non ho niente di meglio da fare nel giorno di natale. 
Vediamo un po' a cosa serve questo algoritmo.
Se avete un po' di basi di programmazione sapreste che scambiare il valore contenuto in due variabili è un operazione comunissima. Il modo più semplice per effettuare questa operazione è di usare una variabile d'appoggio per contenere uno dei due valori e poi fare lo scambio.
tmp := A A := B B := tmp
Direi quasi banale, no? Senonché questo modo prevede la creazione di una variabile temporanea. Esiste tuttavia un algoritmo che fa lo stesso lavoro e non richiede nessuna variabile temporanea. Sto parlando dello Xor Swap, il nome deriva appunto da scambio con OR esclusive ( operazione bit a bit XOR ). Vediamo l'algoritmo:
X := X XOR Y Y := X XOR Y X := X XOR Y
Il bello di questo algoritmo è l'efficienza e la facilità nel ricordarlo. Vediamone un'implementazione in Java ed in C.
public static void main(String[] args)
{
int x = 10;
int y = 20;
System.out.println("x = " + x + " y = " + y);
x = x^y;
y = x^y;
x = x^y;
System.out.println("x = " + x + " y = " + y);
} //[main]
void xorSwap (int *x, int *y)
{
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
Altri articoli che ti potrebbero interessare:
Articoli (RSS)