Scambiare due valori variabili senza utilizzare la terza variabile

Una delle domande molto difficili poste in un’intervista.

Scambia i valori di due variabili come a=10 b=15 .

Generalmente per scambiare due valori di variabili, abbiamo bisogno di 3 variabili come:

 temp=a; a=b; b=temp; 

Ora il requisito è, scambiare i valori di due variabili senza utilizzare la terza variabile.

Utilizzando l’ algoritmo xor swap

 void xorSwap (int* x, int* y) { if (x != y) { //ensure that memory locations are different *x ^= *y; *y ^= *x; *x ^= *y; } } 

Perché il test?

Il test deve garantire che x e y abbiano posizioni di memoria diverse (piuttosto che valori diversi). Questo perché (p xor p) = 0 e se entrambi xey condividono la stessa posizione di memoria, quando uno è impostato su 0, entrambi sono impostati su 0. Quando entrambi * x e * y sono 0, tutte le altre operazioni xor su * x e * y saranno uguali a 0 (poiché sono uguali), il che significa che la funzione imposterà sia * x sia * y impostato su 0.

Se hanno gli stessi valori ma non la stessa posizione di memoria, tutto funziona come previsto

 *x = 0011 *y = 0011 //Note, x and y do not share an address. x != y *x = *x xor *y //*x = 0011 xor 0011 //So *x is 0000 *y = *x xor *y //*y = 0000 xor 0011 //So *y is 0011 *x = *x xor *y //*x = 0000 xor 0011 //So *x is 0011 

Dovrebbe essere usato?

In generale, no. Il compilatore ottimizzerà la variabile temporanea e dato che lo swapping è una procedura comune dovrebbe produrre il codice macchina ottimale per la tua piattaforma.

Prendiamo ad esempio questo rapido programma di test scritto in C.

 #include  #include  #define USE_XOR void xorSwap(int* x, int *y){ if ( x != y ){ *x ^= *y; *y ^= *x; *x ^= *y; } } void tempSwap(int* x, int* y){ int t; t = *y; *y = *x; *x = t; } int main(int argc, char* argv[]){ int x = 4; int y = 5; int z = pow(2,28); while ( z-- ){ # ifdef USE_XOR xorSwap(&x,&y); # else tempSwap(&x, &y); # endif } return x + y; } 

Compilato usando:

 gcc -Os main.c -o swap 

La versione xor prende

 real 0m2.068s user 0m2.048s sys 0m0.000s 

Dove la versione con la variabile temporanea prende:

 real 0m0.543s user 0m0.540s sys 0m0.000s 

la forma generale è:

 A = A operation B B = A inverse-operation B A = A inverse-operation B 

tuttavia è necessario prestare attenzione agli overflow e inoltre non tutte le operazioni hanno un’inversione ben definita per tutti i valori definiti dall’operazione. es. * e / lavoro fino a quando A o B è 0

xor è particolarmente piacevole in quanto è definito per tutti gli inti ed è la sua inversa

 a = a + b b = a - b // b = a a = a - b 

Nessuno ha ancora suggerito l’uso di std::swap .

 std::swap(a, b); 

Non utilizzo alcuna variabile temporanea e, a seconda del tipo di b l’implementazione potrebbe avere una specalizzazione che non lo possiede. L’implementazione dovrebbe essere scritta sapendo se un “trucco” è appropriato o meno. Non ha senso cercare di indovinare.

Più in generale, probabilmente vorrei fare qualcosa di simile, dato che funzionerebbe per i tipi di classi che consentono ad ADL di trovare un sovraccarico migliore se ansible.

 using std::swap; swap(a, b); 

Naturalmente, la reazione dell’intervistatore a questa risposta potrebbe dire molto sul posto vacante.

Come già notato da manu, l’algoritmo XOR è un metodo popolare che funziona per tutti i valori interi (che include quindi puntatori, con un po ‘di fortuna e cast). Per completezza, vorrei menzionare un altro algoritmo meno potente con addizione / sottrazione:

 A = A + B B = A - B A = A - B 

Qui devi fare attenzione a traboccamenti / underflow, ma altrimenti funziona altrettanto bene. Si potrebbe anche provare questo su float / raddoppia nel caso XOR non è consentito su quelli.

Domande stupide meritano risposte adeguate:

 void sw2ap(int& a, int& b) { register int temp = a; // ! a = b; b = temp; } 

L’unico buon uso della parola chiave del register .

Hai esaminato l’ algoritmo di scambio XOR ?

 #include #include void main() { int a,b; clrscr(); cout< <"\n==========Vikas=========="; cout<<"\n\nEnter the two no=:"; cin>>a>>b; cout< <"\na"<
		      	

Poiché la soluzione originale è:

 temp = x; y = x; x = temp; 

Puoi renderlo un due liner usando:

 temp = x; y = y + temp -(x=y); 

Quindi rendilo un solo liner usando:

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

Ecco un’altra soluzione, ma un singolo rischio.

codice:

 #include  #include  void main() { int a =10 , b =45; *(&a+1 ) = a; a =b; b =*(&a +1); } 

qualsiasi valore in posizione a + 1 sarà sostituito.

Se si modifica un po ‘la domanda da porre riguardo a 2 registri di assemblaggio anziché a variabili, è ansible utilizzare anche l’operazione xchg come un’opzione e l’operazione di stack come un’altra.

Considerare a=10 , b=15 :

Utilizzo di addizione e sottrazione

 a = a + b //a=25 b = a - b //b=10 a = a - b //a=15 

Utilizzando divisione e moltiplicazione

 a = a * b //a=150 b = a / b //b=10 a = a / b //a=15 
 #include  int main() { int a, b; printf("Enter A :"); scanf("%d",&a); printf("Enter B :"); scanf("%d",&b); a ^= b; b ^= a; a ^= b; printf("\nValue of A=%d B=%d ",a,b); return 1; } 

questo è l’algoritmo di scambio XOR corretto

 void xorSwap (int* x, int* y) { if (x != y) { //ensure that memory locations are different if (*x != *y) { //ensure that values are different *x ^= *y; *y ^= *x; *x ^= *y; } } } 

è necessario assicurarsi che le posizioni di memoria siano diverse e anche che i valori effettivi siano diversi perché A XOR A = 0

Puoi farlo …. in modo semplice … all’interno di una linea logica

 #include  int main() { int a, b; printf("Enter A :"); scanf("%d",&a); printf("Enter B :"); scanf("%d",&b); int a = 1,b = 2; a=a^b^(b=a); printf("\nValue of A=%d B=%d ",a,b); return 1; } 

o

 #include  int main() { int a, b; printf("Enter A :"); scanf("%d",&a); printf("Enter B :"); scanf("%d",&b); int a = 1,b = 2; a=a+b-(b=a); printf("\nValue of A=%d B=%d ",a,b); return 1; } 
 public void swapnumber(int a,int b){ a = a+b-(b=a); System.out.println("a = "+a +" b= "+b); } 

La migliore risposta sarebbe usare XOR e usarlo in una riga sarebbe fantastico.

  (x ^= y), (y ^= x), (x ^= y); 

x, y sono variabili e la virgola tra di loro introduce i punti di sequenza in modo che non diventi dipendente dal compilatore. Saluti!

Vediamo un semplice esempio di c per scambiare due numeri senza usare la terza variabile.

programma 1:

 #include #include main() { int a=10, b=20; clrscr(); printf("Before swap a=%db=%d",a,b); a=a+b;//a=30 (10+20) b=ab;//b=10 (30-20) a=ab;//a=20 (30-10) printf("\nAfter swap a=%db=%d",a,b); getch(); } 

Produzione:

Prima dello scambio a = 10 b = 20 Dopo lo scambio a = 20 b = 10

Programma 2: Utilizzo di * e /

Vediamo un altro esempio per scambiare due numeri usando * e /.

 #include #include main() { int a=10, b=20; clrscr(); printf("Before swap a=%db=%d",a,b); a=a*b;//a=200 (10*20) b=a/b;//b=10 (200/20) a=a/b;//a=20 (200/10) printf("\nAfter swap a=%db=%d",a,b); getch(); } 

Produzione:

Prima dello scambio a = 10 b = 20 Dopo lo scambio a = 20 b = 10

Programma 3: utilizzo dell’operatore XOR bit a bit:

L’operatore XOR bit a bit può essere utilizzato per scambiare due variabili. Lo XOR di due numeri xey restituisce un numero che ha tutti i bit come 1 dove i bit di xey differiscono. Ad esempio, XOR di 10 (In binario 1010) e 5 (In binario 0101) è 1111 e XOR di 7 (0111) e 5 (0101) è (0010).

 #include  int main() { int x = 10, y = 5; // Code to swap 'x' (1010) and 'y' (0101) x = x ^ y; // x now becomes 15 (1111) y = x ^ y; // y becomes 10 (1010) x = x ^ y; // x becomes 5 (0101) printf("After Swapping: x = %d, y = %d", x, y); return 0; 

Produzione:

Dopo lo scambio: x = 5, y = 10

Programma 4:

Nessuno ha ancora suggerito l’uso di std :: swap.

 std::swap(a, b); 

Non uso alcuna variabile temporanea e, a seconda del tipo di aeb, l’implementazione potrebbe avere una specializzazione che non lo possiede. L’implementazione dovrebbe essere scritta sapendo se un “trucco” è appropriato o meno.

Problemi con i metodi di cui sopra:

1) L’approccio basato sulla moltiplicazione e sulla divisione non funziona se uno dei numeri è 0 in quanto il prodotto diventa 0 indipendentemente dall’altro numero.

2) Entrambe le soluzioni aritmetiche possono causare un overflow aritmetico. Se x e y sono troppo grandi, l’addizione e la moltiplicazione possono uscire dall’intero intervallo.

3) Quando utilizziamo puntatori a una variabile e facciamo uno swap di funzione, tutti i metodi precedenti falliscono quando entrambi i puntatori puntano alla stessa variabile. Diamo un’occhiata a cosa accadrà in questo caso se entrambi puntano alla stessa variabile.

// Metodo basato su XOR bit a bit

 x = x ^ x; // x becomes 0 x = x ^ x; // x remains 0 x = x ^ x; // x remains 0 

// Metodo basato su aritmetica

 x = x + x; // x becomes 2x x = x – x; // x becomes 0 x = x – x; // x remains 0 

Vediamo il seguente programma.

 #include  void swap(int *xp, int *yp) { *xp = *xp ^ *yp; *yp = *xp ^ *yp; *xp = *xp ^ *yp; } int main() { int x = 10; swap(&x, &x); printf("After swap(&x, &x): x = %d", x); return 0; } 

Uscita :

Dopo lo scambio (& x, & x): x = 0

Scambiare una variabile con se stesso può essere necessario in molti algoritmi standard. Ad esempio, vedi questa implementazione di QuickSort dove possiamo scambiare una variabile con se stessa. Il problema precedente può essere evitato mettendo una condizione prima dello scambio.

 #include  void swap(int *xp, int *yp) { if (xp == yp) // Check if the two addresses are same return; *xp = *xp + *yp; *yp = *xp - *yp; *xp = *xp - *yp; } int main() { int x = 10; swap(&x, &x); printf("After swap(&x, &x): x = %d", x); return 0; } 

Uscita :

Dopo lo scambio (& x, & x): x = 10

Scambiare due numeri usando la terza variabile è come questo,

 int temp; int a=10; int b=20; temp = a; a = b; b = temp; printf ("Value of a", %a); printf ("Value of b", %b); 

Scambiare due numeri senza utilizzare la terza variabile

 int a = 10; int b = 20; a = a+b; b = ab; a = ab; printf ("value of a=", %a); printf ("value of b=", %b); 

Forse fuori tema, ma se sai cosa stai scambiando una singola variabile tra due valori diversi, potresti essere in grado di fare una logica di array. Ogni volta che viene eseguita questa riga di codice, si scambierà il valore tra 1 e 2.

 n = [2, 1][n - 1] 
 a = a + b - (b=a); 

È molto semplice, ma potrebbe generare un avvertimento.

soluzione a linea singola per lo scambio di due valori in linguaggio c.

 a=(b=(a=a+b,ab),ab); 
 second_value -= first_value; first_value += second_value; second_value -= first_value; second_value *= -1;