Categoria: curiosità

Nel post precedente ho postato un piccolo “trucchettino”: come fare lo swap di due numeri senza usare una variabile d’appoggio, che ha suscitato non poca curiosità da parte degli affezionati (grazie 🙂 ) che seguono questo blog.

Da più di una persona mi è arrivata la richiesta di spiegare passo passo i passaggi della procedura esposta. ***SPOILER***: se ancora ci state ragionando sopra e non volete sapere la situazione, non proseguite la lettura.

La metodologia esposta si basa sull’algoritmo detto di XOR Swap, ossia sull’applicazione dell’operatore XOR bit per bit ai numeri. La tabella di verità dell’operatore XOR è:

In buona sostanza quindi, l’algoritmo si basa sulla proprietà dell’operatore XOR tale per cui

(x ^ y) ^ x = y

Riprendiamo quindi l’esempio numerico dell’altra volta:

int x = 7, y = 5;

Trasformando in binario:

x = 111

y = 101

Ora applichiamo le operazioni, ricordandoci di applicare lo XOR bit per bit, quindi il primo bit del primo numero con il primo bit del secondo numero, e così via:

x = x ^ y = 111 ^ 101 = 010

y = y ^ x = 101 ^ 010 = 111

x = x ^ y = 010 ^ 111 = 101

Alla fine otteniamo quindi:

x = 101

y = 111

Ossia… lo swap dei due valori iniziali! Resta di stucco… è un barbatrucco! 🙂

Che ne dite, me la merito una birretta? Il widget per le donazioni con PayPal è in alto a destra 😉

L’altra settimana, ad un amico neo-programmatore, ho posto questo quesito: “Scrivimi il codice per effettuare lo swap di due variabili senza usarne una terza di appoggio” (vecchio quesito che mi aveva posto a suo tempo il mio professore di Ingegneria del Software).

Ovviamente, non era consentito cercare la soluzione in Internet! 🙂

La soluzione “classica” prevede l’uso di una variabile di appoggio, quindi:

int x = 7, y = 5, z;

z = x;

x = y;

y = z;

E fin qui tutto chiaro 🙂 Ma come farlo senza utilizzare “z”?

Dopo una settimana, è stata “gettata la spugna” da parte del mio amico quindi vi pubblico qui la soluzione: