Come funziona lo scambio di variabili XOR?

Question

Qualcuno può spiegarmi come funziona lo scambio XOR di due variabili senza variabile temporanea?

void xorSwap (int *x, int *y)
{
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

Capisco COSA fa, ma qualcuno può guidarmi attraverso la logica di come funziona?

Answer 1

Puoi vedere come funziona effettuando la sostituzione:

x1 = x0 xor y0
y2 = x1 xor y0
x2 = x1 xor y2

Sostituendo,

x1 = x0 xor y0
y2 = (x0 xor y0) xor y0
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0)

Perché xor è completamente associativo e commutativo:

y2 = x0 xor (y0 xor y0)
x2 = (x0 xor x0) xor (y0 xor y0) xor y0

Dal x xor x == 0 per qualsiasi x,

y2 = x0 xor 0
x2 = 0 xor 0 xor y0

E poiché x xor 0 == x per qualsiasi x,

y2 = x0
x2 = y0

E lo scambio è fatto.

Answer 2

Altre persone l'hanno spiegato, ora voglio spiegare perché è stata una buona idea, ma ora non lo è.

Ai tempi in cui avevamo semplici CPU a ciclo singolo o multiplo, era più economico usare questo trucco per evitare costose dereferenze di memoria o versare registri nello stack. Tuttavia, ora abbiamo CPU con pipeline enormi. La pipeline del P4 variava da 20 a 31 (circa) fasi nelle loro pipeline, in cui qualsiasi dipendenza tra la lettura e la scrittura in un registro poteva causare il blocco dell'intero processo. Lo xor swap ha alcune dipendenze molto pesanti tra A e B che in realtà non contano affatto ma bloccano la pipeline in pratica. Una pipeline bloccata provoca un percorso di codice lento e se questo scambio è nel tuo ciclo interno, ti sposterai molto lentamente.

Nella pratica generale, il tuo compilatore può capire cosa vuoi veramente fare quando esegui uno scambio con una variabile temp e può compilarlo in una singola istruzione XCHG. L'uso di xor swap rende molto più difficile per il compilatore indovinare il tuo intento e quindi molto meno probabile ottimizzarlo correttamente. Per non parlare della manutenzione del codice, ecc.

Answer 3

Mi piace pensarci graficamente piuttosto che numericamente.

Supponiamo che inizi con x = 11 e y = 5 In binario (e userò un'ipotetica macchina a 4 bit), ecco xey

       x: |1|0|1|1|   -> 8 + 2 + 1
       y: |0|1|0|1|   -> 4 + 1

Ora per me, XOR è un'operazione invertita e farlo due volte è un mirror:

     x^y: |1|1|1|0|
 (x^y)^y: |1|0|1|1|   <- ooh!  Check it out - x came back
 (x^y)^x: |0|1|0|1|   <- ooh!  y came back too!

Answer 4

Eccone uno che dovrebbe essere leggermente più facile da grok:

int x = 10, y = 7;

y = x + y; //x = 10, y = 17
x = y - x; //x = 7, y = 17
y = y - x; //x = 7, y = 10

Ora, si può capire un po 'più facilmente il trucco XOR capendo che ^ può essere pensato come + o - . Proprio come:

x + y - ((x + y) - x) == x 

, quindi:

x ^ y ^ ((x ^ y) ^ x) == x

Answer 5

Il motivo per cui funziona perché XOR non perde informazioni. Potresti fare la stessa cosa con l'aggiunta e la sottrazione ordinarie se potessi ignorare l'overflow. Ad esempio, se la coppia di variabili A, B contiene originariamente i valori 1,2, è possibile scambiarli in questo modo:

 // A,B  = 1,2
A = A+B // 3,2
B = A-B // 3,1
A = A-B // 2,1

A proposito c'è un vecchio trucco per codificare un elenco collegato a 2 vie in un unico "puntatore". Supponiamo di avere un elenco di blocchi di memoria agli indirizzi A, B e C. La prima parola in ogni blocco è, rispettivamente:

 // first word of each block is sum of addresses of prior and next block
 0 + &B   // first word of block A
&A + &C   // first word of block B
&B + 0    // first word of block C

Se hai accesso al blocco A, ti dà l'indirizzo di B. Per arrivare a C, prendi il " pointer " in B e sottrarre A e così via. Funziona altrettanto bene all'indietro. Per scorrere l'elenco, è necessario mantenere i puntatori a due blocchi consecutivi. Ovviamente useresti XOR al posto di addizioni / sottrazioni, quindi non dovresti preoccuparti di overflow.

Puoi estenderlo a un "link web" " se vuoi divertirti un po '.

Answer 6

Molte persone scambiano due variabili xey usando una variabile temporanea, in questo modo:

tmp = x
x = y
y = tmp

Ecco un trucco di programmazione pulito per scambiare due valori senza la necessità di una temp:

x = x xor y
y = x xor y
x = x xor y

Maggiori dettagli in Scambia due variabili usando XOR

  

Sulla linea 1 combiniamo xey (usando XOR) per ottenere questo & # 8220; ibrido & # 8221; e lo memorizziamo nuovamente in x. XOR è un ottimo modo per salvare le informazioni, perché puoi rimuoverle eseguendo di nuovo un XOR.

     

On line 2. Abbiamo XOR l'ibrido con y, che cancella tutte le informazioni y, lasciandoci solo con x. Salviamo questo risultato in y, quindi ora sono stati scambiati.

     

Nell'ultima riga, x ha ancora il valore ibrido. Lo XOR di nuovo con y (ora con il valore originale di x) per rimuovere tutte le tracce di x dall'ibrido. Questo ci lascia con y e lo scambio è completo!

---

  

Il computer ha in realtà un & # 8220; temp implicito & # 8221; variabile che memorizza i risultati intermedi prima di riscriverli in un registro. Ad esempio, se aggiungi 3 a un registro (in pseudocodice in linguaggio macchina):

ADD 3 A // add 3 to register A

  

L'ALU (Arithmetic Logic Unit) è in realtà ciò che esegue l'istruzione 3 + A. Prende gli ingressi (3, A) e crea un risultato (3 + A), che la CPU quindi memorizza nel registro originale di A & # 8217; Quindi, abbiamo usato ALU come spazio temporaneo temporaneo prima di avere la risposta finale.

     

Diamo per scontati i dati temporanei impliciti di ALU, ma sono sempre lì. In modo simile, l'ALU può restituire il risultato intermedio di XOR nel caso di x = x xor y, a quel punto la CPU lo memorizza nel registro originale di x.

     

Poiché non siamo abituati a pensare alla povera e trascurata ALU, lo scambio XOR sembra magico perché non ha una variabile temporanea esplicita. Alcune macchine hanno un'istruzione XCHG di scambio in 1 passaggio per scambiare due registri.

Answer 7

@VonC ha ragione, è un trucco matematico pulito . Immagina parole a 4 bit e vedi se questo aiuta.

word1 ^= word2;
word2 ^= word1;
word1 ^= word2;


word1    word2
0101     1111
after 1st xor
1010     1111
after 2nd xor
1010     0101
after 3rd xor
1111     0101

Answer 8

Fondamentalmente ci sono 3 passaggi nell'approccio XOR:

a ’= a XOR b (1)
b '= a' XOR b (2)
a "= a" XOR b "(3)

Per capire perché questo funziona innanzitutto notare che:

1. XOR produrrà un 1 solo se esattamente uno dei suoi operandi è 1 e l'altro è zero;
2. XOR è commutativo quindi a XOR b = b XOR a;
3. XOR è associativo quindi (a XOR b) XOR c = a XOR (b XOR c); e
4. a XOR a = 0 (questo dovrebbe essere ovvio dalla definizione in 1 sopra)

Dopo il passo (1), la rappresentazione binaria di a avrà 1 bit solo nelle posizioni di bit in cui aeb hanno bit opposti. Questo è (ak = 1, bk = 0) o (ak = 0, bk = 1). Ora quando effettuiamo la sostituzione nel passaggio (2) otteniamo:

b ’= (a XOR b) XOR b
    = a XOR (b XOR b) perché XOR è associativa
   = uno XOR 0 a causa di [4] sopra
   = a causa della definizione di XOR (vedi 1 sopra)

Ora possiamo sostituire il passaggio (3):

a ”= (a XOR b) XOR a
    = (b XOR a) XOR a perché XOR è commutativo
    = b XOR (a XOR a) perché XOR è associativa
    = b XOR 0 a causa di [4] sopra
    = b a causa della definizione di XOR (vedi 1 sopra)

Informazioni più dettagliate qui: Necessario e sufficiente

Answer 9

Come nota a margine ho reinventato questa ruota in modo indipendente diversi anni fa sotto forma di scambio di numeri interi facendo:

a = a + b
b = a - b ( = a + b - b once expanded)
a = a - b ( = a + b - a once expanded).

(Questo è menzionato sopra in un modo difficile da leggere),

Lo stesso ragionamento si applica agli swap xor: a ^ b ^ b = ae a ^ b ^ a = a. Poiché xor è commutativo, x ^ x = 0 e x ^ 0 = x, questo è abbastanza facile da vedere dal

= a ^ b ^ b
= a ^ 0
= a

e

= a ^ b ^ a 
= a ^ a ^ b 
= 0 ^ b 
= b

Spero che questo aiuti. Questa spiegazione è già stata fornita ... ma non molto chiaramente imo.