[C++] Scambio di numeri con bitwise

[ZfreS]

Nel libro da cui studio c'è un esempio di utilizzo dell'operatore bitwise xor. Dati due interi x1 e x2 per scambiarli bisogna effettuare queste operazioni:

Codice:

x1 = x1^x2
x2=x1^x2
x1=x1^x2


Potreste spiegarmi come funziona? Perchè facendo queste operazioni ottengo i numeri scambiati?

[Super Squirrel]

Dalla tabella di verità dello XOR

A B | C
0 0 | 0
1 0 | 1
0 1 | 1
1 1 | 0

si evince che

$C=Ao+BrArr{(Co+A=B),(Co+B=A):}$

Quindi ponendo

Codice:

x1 = A
x2 = B
C = A ^ B

le ultime due equazioni da te scritte diventano

Codice:

x2 = C ^ B = A
x1 = C ^ A = B

[ZfreS]

Ma perhè possiamo dedurre questo?
$C=Ao+BrArr{(Co+A=B),(Co+B=A):}$

[Super Squirrel]

Dalla tabella di verità, che ricopre tutti i casi possibili, puoi facilmente verificare che quell'implicazione è sempre vera.

[ZfreS]

Ok. Ora devo capire come fa a scambiare i numeri. Prendiamo per esempio $a=3$ $b=5$ che in binario sono $a=0011$ e $b=0101$. La prima istruzione è $a = a^b$ ovvero $a = 0011^0101$ $a=0110=6$. La seconda istruzione è: $b = a^b$ ovvero $b = 0110^0101$ $b=0011=3$ e infine la terza istruzione è: $a = a^b$ ovvero
$a = 0110^0011$ $a = 0101=5$. I numeri effettivamente risultano scambiati, ma non capisco come mai facendo proprio lo xor con queste istruzioni si ottiene il risultato. Cosa avviene a livello dei bit?

[Super Squirrel]

Non sono sicuro di aver capito bene la domanda, ad ogni modo quanto detto in precedenza, se vale per 2 singoli bit, varrà anche per 2 sequenze di bit (che nel caso specifico rappresentano 2 variabili intere).

[vict85]

Non usare il simbolo ^ in mathjax o non si capisce nulla. Se vuoi usare un simbolo simile in mathjax dovresti scrivere \(\wedge\) (\wedge), ma lo sconsiglio perché quel simbolo è usato in matematica per indicare la congiunzione logica. Wiki sembra suggerire un specie di \(\vee\) con un puntino sopra. Ma nella lista mette anche \(\veebar\) (\veebar) e \(\oplus\) (\oplus) che sono presenti nella lista dei Simboli Latex supportati dal sito.

La prima cosa che devi considerare è che lo xor viene fatto bit a bit e che quindi ti basta che lo scambio funzioni per un singolo bit. Se lo fa funzionerà automaticamente per ogni "array di bit".

E' abbastanza semplice verificare che lo xor gode della proprietà commutativa e associativa. Inoltre ha la proprietà che \(a \oplus a = \mathbf{0}\) per ogni \(a\in \mathbb{Z}_2^{32}\) e che \(a \oplus \mathbf{0} = a\).

Venendo al tuo problema. Vuoi dimostrare le seguenti due cose:

1. \(a \oplus b \oplus a = b\) . Questo si dimostra così:
   \[ a\oplus b\oplus a = a\oplus a\oplus b = \mathbf{0}\oplus b = b\]
2. \(a \oplus b \oplus b = a\) si dimostra in modo simile.

[ZfreS]

Perfetto vict, grazie mille per la spiegazione!

[vict85]

Un piccolo consiglio informatico: impara quella cosa e poi dimenticala. Il compilatore applicherà l'ottimizzazione da solo il più delle volte e, come avrai notato, non è la successione di istruzioni più leggibile che esista.

[ZfreS]

Ho capito, grazie per il consiglio!