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]

Originariamente inviato da 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?

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]

Originariamente inviato da Antonio23

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

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

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>:   ret

Nel 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".

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]

Originariamente inviato da 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>:   ret

Nel 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".

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.

[sirus]

Sono commosso...