Questo può essere fatto con qualsiasi operazione binaria invertibile come XOR o addizione. Quindi potresti anche scrivere:

 a ← a + b
 b ← a - b
 a ← a - b

O più in generale, supponiamo che per alcuni operatori binari (associativi, commutativi) # ci sia un'identità i tale che

x # i = i # x = x

e che per ogni valore x esiste un valore x' tale che

x # x' = i

Quindi puoi scambiare due valori usando quell'operatore:

a ← a # b
b ← a # b'
a ← a # b'

Per aggiunta, x' = -x , ma per XOR abbiamo x XOR x = 0 in modo che x' = x , in modo che:

a ← a XOR b
b ← a XOR b'
a ← a XOR b'

riduce a

a ← a XOR b
b ← a XOR b
a ← a XOR b

More specifically, how was this derived? Was it a mere coincidence that XOR such and such values does this? This question applies to all bitwise operators.

Queste operazioni bit a bit corrispondono a noti elementi elementari operazioni da algebra superiore che descriverò brevemente.

Aritmetica modulare

Il primo elemento importante è modulare aritmetica -che è un tipo speciale di calcoli a quoziente anello . Anche se non lo fai sospetto che tu abbia già familiarità con casi speciali di modulare aritmetica.

Se scegliamo un intero positivo N che chiamiamo modulo possiamo calcolare su residui modulo N che è proprio come il calcolo con numeri normali e fingendo di N = 0 . Tutto il solito calcolo le regole sui numeri interi sono ancora valide, con due disposizioni:

• Per i residui a = b modulo N significa che gli interi a e b differiscono un multiplo di N .

• Per i residui modulo N la relazione m × a = m × b non implica che a = b anche se m è diverso da zero modulo N . [RSA]

Ma i restanti rapporti usuali rimangono validi. Esaminiamo alcuni esempi.

• Se il 2 gennaio è un giovedì, febbraio 2 è domenica perché identifichiamo i giorni con i residui modulo 7 e, avendo gennaio 31 giorni, scriviamo

  2 + 31 = 2 + 4 × 7 + 3 = 2 + 3 = 5

  in modo che il 2 febbraio sia lo stesso giorno della settimana del 5 gennaio, una domenica.

• A scuola impariamo a riassumere le cifre dei numeri per verificare se siamo noi ha funzionato bene una moltiplicazione. In realtà stiamo calcolando residui modulo 9, in modo che 10 = 1, e verificare che il nostro la moltiplicazione è corretta modulo 9. (Naturalmente, questo non lo è infallibile, ad es. non vedremmo se eravamo fuori da 9).

• Quando calcoliamo su bit, calcoliamo sui residui modulo 2 e il l'aggiunta è XOR , la moltiplicazione è AND . Quindi

  a XOR b = a + b

  a AND b = a × b

  NOT a = 1 XOR a = 1 + a = 1 - a (che è la definizione "buona" di NOT)

  a OR B = a + b + a × b

Come esercizio, puoi verificare che a OR b sia NOT(NOT a AND NOT b) di espandendo l'espressione algebrica corrispondente. È altresì interessante notare che "l'operazione facile" è XOR e non OR .

[RSA]: come nota a margine, il sistema RSA si basa sulla teoria nultiplicativa di residui modulo N dove N è il prodotto di due numeri primi.

Algebra lineare

Algebra lineare sistematizza calcoli su coordinate. A un livello elementare, esso viene insegnato con le coordinate nell'anello R di numeri reali e applicato alla geometria e alla meccanica. Ring è il termine matematico per a insieme di coefficienti, su cui possiamo calcolare proprio come su interi. Così, sì, i set di residui modulo un dato N sono anche anelli, e possono anche essere come coefficienti per fare algebra lineare.

Ora lascia B essere l'anello di residui modulo 2, cioè 0, 1 dotato di addizione e moltiplicazione come sopra. Un registro macchina, diciamo in un 8 macchina bit, ma 8 potrebbe essere qualsiasi altro numero, può essere visto come un Vettore a 8 dimensioni con voci in B , in modo che a XOR b = a + b , dove l'aggiunta considerata è l'aggiunta di di vettori con le voci in B . (Se consideri a e b come rappresentazione di 2-complementi di alcuni numeri interi, a XOR b non ha nulla a che fare con la somma di questi numeri interi).

XOR-Swap

Ora diamo un'occhiata troppo stridente all'algoritmo XOR-Swap. Noi inizia con a e b e scrivo a[k] e b[k] i valori di a e b a i vari passaggi degli algoritmi.

a[1] ← a[0] + b[0]

b[1] ← a[1] + b[0]

a[2] ← b[1] + a[1]

Si noti che per questi vettori con voci in B abbiamo,

b[1] = a[0] + 2× b[0] = a[0]

a[2] = b[1] + a[1] = 2 × a[0] + b[0] = b[0]

Quindi, alla fine del nostro calcolo, b contiene il valore iniziale di a e a contiene il valore iniziale di b .

"Perché funziona l'algoritmo?" è un concetto soggettivo e principalmente basato sull'opinione, quindi non sentirti male se questa domanda viene messa in attesa. Ma il strettamente correlato "Come funziona?" si può rispondere, quindi avrò un tentativo.

Prima di tutto, XOR è speciale in quanto conserva tutte le informazioni che hai inserito: esegue il mapping da 1 a 0 e da 0 a 1 (se applicato a 1) e da 0 a 0 e 1 a 1 (se applicato a 0). Questo è importante, perché senza quella proprietà il trucco non potrebbe funzionare. Ad esempio, logico AND è non informazioni-preservanti: se tu AND 0 ad un valore, otterrai sempre 0 indipendentemente dal lato sinistro, quindi non puoi ricostruire il valore input dall'output.

Inoltre, è ciclico : se tu XOR lo stesso valore a un numero due, ottieni il numero originale. Questo non è difficile da vedere, perché ogni 0 del numero diventa 1 e quindi torna di nuovo a 0 e viceversa. Questo è anche fondamentale per il trucco per funzionare.

Dopo il primo passaggio, a è stato sovrascritto con un valore diverso, ma le informazioni su quel valore sono ancora presenti. Il valore originale è quello che otterresti se applicassi nuovamente XOR b , ed è ciò che accade nel secondo passaggio. Il terzo passo ripete questo trucco per b , ma poiché b è già stato modificato nel secondo passaggio, il a = a XOR b finale esegue efficacemente due operazioni XOR, finendo esattamente con il valore originale di b .

Questo è il più vicino possibile a spiegare perché penso che il metodo funzioni, ma nota che per acquisire una comprensione intuitiva di tali trucchi, niente batte effettivamente l'esecuzione del calcolo da solo. Scegli un paio di numeri binari a due cifre, prendi un pezzo di carta e datti da fare. Ancora meglio, ottieni tutte 16 combinazioni di numeri binari a due cifre e calcola tutti i 48 passaggi sulla carta. È quasi impossibile non capire il flusso di informazioni XOR dopo quello.

perché funzionano gli algoritmi bit a bit? perché qualcuno l'ha trovato e ha dimostrato di aver funzionato per tutti i valori.

se ricordi che a^b = b^a e a^a=0 e a^0=a allora puoi espandere l'algoritmo come:

a'=a^b;
b'=a'^b;
a''=a'^b';

o

b'=(a^b)^b=a^(b^b)=a;
a''=((a^b)^b)^(a^b)=a^b^b^a^b=a^a^b=b;

Detto questo credo che sia inutile nei linguaggi moderni perché l'ottimizzatore riconoscerà "temp var swap" ( tmp=a;a=b;b=tmp; ) e ottimizzerà secondo necessità.

Inoltre sulle architetture RISC è necessario caricare le variabili in un registro prima di poterle xorare e se si dispone di entrambi i registri è sufficiente scriverli in posizioni opposte. Ciò significa che è utile solo se c'è un xor diretto sulle posizioni e non c'è una posizione extra per memorizzare il temporaneo.

But, why does it work?

Poiché XOR funziona a bit, è sufficiente assumere che a e b siano solo un bit lungo. In questo caso, XOR è la stessa cosa dell'aggiunta modulo 2. Ora se a[0] e b[0] denotano il valore di a e b prima del calcolo e a[1] e b[1] loro valore dopo, abbiamo (modulo 2):

 a[1] = b[0] + 2*a[0] = b[0]
 b[1] = a[0] + 2*b[0] = a[0]

Se sei in uno stato d'animo pedante, puoi racchiudere tutto questo in una frase: stiamo calcolando in uno spazio vettoriale di due caratteristiche e XOR è solo l'aggiunta di vettori .