scambiare due valori

[kappa85]

Un mio prof. ha affermato che è possibile scambiare i valori di due variabili (per esempio intere) senza usare variabili di appoggio nè altro spazio aggiuntivo, utilizzando solo 2 istruzioni... come si fa?

[andbin]

Un mio prof. ha affermato che è possibile scambiare i valori di due variabili (per esempio intere) senza usare variabili di appoggio nè altro spazio aggiuntivo, utilizzando solo 2 istruzioni... come si fa?Bastano 3 xor, anche in 1 istruzione unica:
#include <stdio.h>

int main (void)
{
int a=2, b=5;

printf ("%d %d\n", a, b);

a ^= b ^= a ^= b;

printf ("%d %d\n", a, b);

return 0;
}

[kappa85]

bellissimo! ma perchè funziona?:D non è che lo puoi spiegare....??:p

quoto.. e a livello di costi di esecuzione è più pesante di un normale scambio con un variabile temp?

[pisto]

l'idea è la stessa del RAID (almeno per quel che ne so di come funziona il raid), solo che il disco con lo xor degli altri è proprio un disco di dati stesso

[andbin]

Certo che posso spiegarlo. Si basa sull'utilizzo di una exclusive-or (XOR), che ha una proprietà particolare: è, per così dire "reversibile". Dato un valore A, se faccio lo xor con B, ottengo C e se a questo riapplico lo xor con B, riottengo A. In pratica: (A xor B) xor B = A

Per fare lo scambio tra 2 valori, la procedura per esteso è:
A = A xor B
B = A xor B
A = A xor B

Es. A=1 (0001 in binario) e B=8 (1000 in binario)

1) A=9 perché 0001 xor 1000 dà 1001
2) B=1 perché 1001 xor 1000 dà 0001
3) A=8 perché 1001 xor 0001 dà 1000

In C (e altri linguaggi) a = a^b si può scrivere a ^= b, ed essendo le assegnazioni associative da destra a sinistra, scrivere a ^= b ^= a ^= b è solo un modo più "figo" per realizzare la procedura sopra.

Dal punto di vista delle prestazioni, bisogna vedere se il compilatore è furbo o meno. Scambiare 2 valori usando un temporaneo richiede tecnicamente 3 assegnazioni, mentre con lo xor richiede 3 assegnazioni con xor.

Prendiamo questo sorgente:
#include <stdio.h>

int main (void)
{
int a, b, t;

scanf ("%d %d", &a, &b);

printf ("%d %d\n", a, b);

a ^= b ^= a ^= b;

printf ("%d %d\n", a, b);

t = a;
a = b;
b = t;

printf ("%d %d\n", a, b);

return 0;
}
Compilato con gcc su Linux attivando le ottimizzazioni, ottengo:
0x8048370 <main>: push %ebp
0x8048371 <main+1>: mov %esp,%ebp
0x8048373 <main+3>: sub $0x8,%esp
0x8048376 <main+6>: and $0xfffffff0,%esp
0x8048379 <main+9>: push %ecx
0x804837a <main+10>: lea 0xfffffffc(%ebp),%ecx
0x804837d <main+13>: push %ecx
0x804837e <main+14>: lea 0xfffffff8(%ebp),%edx
0x8048381 <main+17>: push %edx
0x8048382 <main+18>: push $0x80484b4
0x8048387 <main+23>: call 0x804827c <scanf>
0x804838c <main+28>: add $0xc,%esp
0x804838f <main+31>: mov 0xfffffffc(%ebp),%eax
0x8048392 <main+34>: push %eax
0x8048393 <main+35>: mov 0xfffffff8(%ebp),%ecx
0x8048396 <main+38>: push %ecx
0x8048397 <main+39>: push $0x80484ba
0x804839c <main+44>: call 0x804829c <printf>
0x80483a1 <main+49>: mov 0xfffffffc(%ebp),%edx
0x80483a4 <main+52>: mov 0xfffffff8(%ebp),%ecx
0x80483a7 <main+55>: xor %edx,%ecx
0x80483a9 <main+57>: xor %ecx,%edx
0x80483ab <main+59>: add $0xc,%esp
0x80483ae <main+62>: xor %edx,%ecx
0x80483b0 <main+64>: push %edx
0x80483b1 <main+65>: push %ecx
0x80483b2 <main+66>: push $0x80484ba
0x80483b7 <main+71>: mov %edx,0xfffffffc(%ebp)
0x80483ba <main+74>: mov %ecx,0xfffffff8(%ebp)
0x80483bd <main+77>: call 0x804829c <printf>
0x80483c2 <main+82>: mov 0xfffffff8(%ebp),%edx
0x80483c5 <main+85>: add $0xc,%esp
0x80483c8 <main+88>: mov 0xfffffffc(%ebp),%ecx
0x80483cb <main+91>: push %edx
0x80483cc <main+92>: push %ecx
0x80483cd <main+93>: push $0x80484ba
0x80483d2 <main+98>: mov %ecx,0xfffffff8(%ebp)
0x80483d5 <main+101>: mov %edx,0xfffffffc(%ebp)
0x80483d8 <main+104>: call 0x804829c <printf>
0x80483dd <main+109>: xor %eax,%eax
0x80483df <main+111>: leave
0x80483e0 <main+112>: retNel caso di xor, il compilatore, da bravo, ha emesso le 3 xor ma nel caso di utilizzo di un temporaneo, è stato abbastanza furbo da capire che si trattava di uno swap e quindi ha semplicemente fatto 2 mov per mettere nei 2 registri le variabili "al contrario". :D

Bisogna comunque valutare architettura per architettura. La tecnica del XOR è sicuramente valida ad esempio su microcontrollori in cui magari non si vuole usare un temporaneo e magari, fortunatamente, una XOR ha lo stesso costo di una MOV.

[Marco Giunio Silano]

Certo che posso spiegarlo. Si basa sull'utilizzo di una exclusive-or (XOR), che ha una proprietà particolare: è, per così dire "reversibile". Dato un valore A, se faccio lo xor con B, ottengo C e se a questo riapplico lo xor con B, riottengo A. In pratica: (A xor B) xor B = A

Per fare lo scambio tra 2 valori, la procedura per esteso è:
A = A xor B
B = A xor B
A = A xor B

Es. A=1 (0001 in binario) e B=8 (1000 in binario)

1) A=9 perché 0001 xor 1000 dà 1001
2) B=1 perché 1001 xor 1000 dà 0001
3) A=8 perché 1001 xor 0001 dà 1000

In C (e altri linguaggi) a = a^b si può scrivere a ^= b, ed essendo le assegnazioni associative da destra a sinistra, scrivere a ^= b ^= a ^= b è solo un modo più "figo" per realizzare la procedura sopra.

Dal punto di vista delle prestazioni, bisogna vedere se il compilatore è furbo o meno. Scambiare 2 valori usando un temporaneo richiede tecnicamente 3 assegnazioni, mentre con lo xor richiede 3 assegnazioni con xor.

Prendiamo questo sorgente:
#include <stdio.h>

int main (void)
{
int a, b, t;

scanf ("%d %d", &a, &b);

printf ("%d %d\n", a, b);

a ^= b ^= a ^= b;

printf ("%d %d\n", a, b);

t = a;
a = b;
b = t;

printf ("%d %d\n", a, b);

return 0;
}
Compilato con gcc su Linux attivando le ottimizzazioni, ottengo:
0x8048370 <main>: push %ebp
0x8048371 <main+1>: mov %esp,%ebp
0x8048373 <main+3>: sub $0x8,%esp
0x8048376 <main+6>: and $0xfffffff0,%esp
0x8048379 <main+9>: push %ecx
0x804837a <main+10>: lea 0xfffffffc(%ebp),%ecx
0x804837d <main+13>: push %ecx
0x804837e <main+14>: lea 0xfffffff8(%ebp),%edx
0x8048381 <main+17>: push %edx
0x8048382 <main+18>: push $0x80484b4
0x8048387 <main+23>: call 0x804827c <scanf>
0x804838c <main+28>: add $0xc,%esp
0x804838f <main+31>: mov 0xfffffffc(%ebp),%eax
0x8048392 <main+34>: push %eax
0x8048393 <main+35>: mov 0xfffffff8(%ebp),%ecx
0x8048396 <main+38>: push %ecx
0x8048397 <main+39>: push $0x80484ba
0x804839c <main+44>: call 0x804829c <printf>
0x80483a1 <main+49>: mov 0xfffffffc(%ebp),%edx
0x80483a4 <main+52>: mov 0xfffffff8(%ebp),%ecx
0x80483a7 <main+55>: xor %edx,%ecx
0x80483a9 <main+57>: xor %ecx,%edx
0x80483ab <main+59>: add $0xc,%esp
0x80483ae <main+62>: xor %edx,%ecx
0x80483b0 <main+64>: push %edx
0x80483b1 <main+65>: push %ecx
0x80483b2 <main+66>: push $0x80484ba
0x80483b7 <main+71>: mov %edx,0xfffffffc(%ebp)
0x80483ba <main+74>: mov %ecx,0xfffffff8(%ebp)
0x80483bd <main+77>: call 0x804829c <printf>
0x80483c2 <main+82>: mov 0xfffffff8(%ebp),%edx
0x80483c5 <main+85>: add $0xc,%esp
0x80483c8 <main+88>: mov 0xfffffffc(%ebp),%ecx
0x80483cb <main+91>: push %edx
0x80483cc <main+92>: push %ecx
0x80483cd <main+93>: push $0x80484ba
0x80483d2 <main+98>: mov %ecx,0xfffffff8(%ebp)
0x80483d5 <main+101>: mov %edx,0xfffffffc(%ebp)
0x80483d8 <main+104>: call 0x804829c <printf>
0x80483dd <main+109>: xor %eax,%eax
0x80483df <main+111>: leave
0x80483e0 <main+112>: retNel caso di xor, il compilatore, da bravo, ha emesso le 3 xor ma nel caso di utilizzo di un temporaneo, è stato abbastanza furbo da capire che si trattava di uno swap e quindi ha semplicemente fatto 2 mov per mettere nei 2 registri le variabili "al contrario". :D

Bisogna comunque valutare architettura per architettura. La tecnica del XOR è sicuramente valida ad esempio su microcontrollori in cui magari non si vuole usare un temporaneo e magari, fortunatamente, una XOR ha lo stesso costo di una MOV.

:ave:

[sirus]

Sono commosso... :cry: