Échange de deux valeurs de variable sans utiliser de troisième variable

L’une des questions les plus délicates posées lors d’une interview.

Échangez les valeurs de deux variables comme a=10 et b=15 .

Généralement, pour échanger deux valeurs de variables, il faut une 3ème variable comme:

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

Maintenant, l’exigence est, échanger les valeurs de deux variables sans utiliser la 3ème variable.

Utilisation de l’ algorithme d’échange xor

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

Pourquoi le test?

Le test consiste à s’assurer que x et y ont des emplacements de mémoire différents (plutôt que des valeurs différentes). Ceci est dû au fait que (p xor p) = 0 et que si x et y partagent le même emplacement de mémoire, lorsque l’un est défini sur 0, les deux sont réglés sur 0. Lorsque les deux * x et * y sont 0, toutes les autres opérations xor * x et * y seront égaux à 0 (car ils sont identiques), ce qui signifie que la fonction définira à la fois * x et * y sur 0.

S’ils ont les mêmes valeurs mais pas le même emplacement de mémoire, tout fonctionne comme prévu

 *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 

Faut-il l’utiliser?

Dans les cas généraux, non. Le compilateur optimisera la variable temporaire et, étant donné que l’échange est une procédure courante, il doit générer le code machine optimal pour votre plate-forme.

Prenons par exemple ce programme de test rapide écrit en 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; } 

Compilé en utilisant:

 gcc -Os main.c -o swap 

La version de xor prend

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

Où la version avec la variable temporaire prend:

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

la forme générale est:

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

Cependant, vous devez potentiellement faire attention aux débordements et toutes les opérations n’ont pas d’inverse bien défini pour toutes les valeurs définies pour l’opération. par exemple * et / travail jusqu’à ce que A ou B soit 0

xor est particulièrement agréable car il est défini pour tous les ints et est son propre inverse

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

Personne n’a encore suggéré d’utiliser std::swap .

 std::swap(a, b); 

Je n’utilise aucune variable temporaire et, selon le type de a et b l’implémentation peut avoir une spécalisation non plus. La mise en œuvre doit être écrite en sachant si une «astuce» est appropriée ou non. Il ne sert à rien d’essayer de deviner.

Plus généralement, je voudrais probablement faire quelque chose comme cela, car cela fonctionnerait pour les types de classe permettant à ADL de trouver une meilleure surcharge si possible.

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

Bien entendu, la réaction de l’interviewer à cette réponse pourrait en dire long sur la vacance.

Comme cela a déjà été noté par manu, l’algorithme XOR est populaire et fonctionne pour toutes les valeurs entières (y compris les pointeurs, avec un peu de chance et de casting). Par souci d’exhaustivité, je voudrais mentionner un autre algorithme moins puissant avec addition / soustraction:

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

Ici, vous devez faire attention aux débordements / sous-stream, mais sinon cela fonctionne tout aussi bien. Vous pourriez même essayer ceci sur floats / doubles dans le cas où XOR n’est pas autorisé sur ceux-là.

Des questions stupides méritent des réponses appropriées:

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

Le seul bon usage du mot-clé register .

Avez-vous examiné l’ algorithme d’échange XOR ?

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

Puisque la solution originale est:

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

Vous pouvez en faire une doublure en utilisant:

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

Puis en faire un liner en utilisant:

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

Voici une autre solution mais un seul risque.

code:

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

toute valeur à l’emplacement a + 1 sera remplacée.

Si vous modifiez un peu la question pour demander 2 registres d’assemblage au lieu de variables, vous pouvez également utiliser l’opération xchg comme une option et l’opération de stack comme une autre.

Considérons a=10 , b=15 :

Utiliser l’addition et la soustraction

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

Utilisation de la division et de la multiplication

 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; } 

c’est l’algorithme d’échange XOR correct

 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; } } } 

vous devez vous assurer que les emplacements de mémoire sont différents et que les valeurs réelles sont différentes car A XOR A = 0

Vous pouvez le faire …. de manière simple … dans une seule ligne

 #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; } 

ou

 #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 meilleure réponse serait d’utiliser XOR et de l’utiliser sur une seule ligne serait cool.

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

x, y sont des variables et la virgule entre elles introduit les points de séquence pour ne pas devenir dépendante du compilateur. À votre santé!

Voyons un exemple c simple pour échanger deux nombres sans utiliser la troisième variable.

programme 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(); } 

Sortie:

Avant échange a = 10 b = 20 après échange a = 20 b = 10

Programme 2: Utiliser * et /

Voyons un autre exemple pour échanger deux nombres en utilisant * et /.

 #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(); } 

Sortie:

Avant échange a = 10 b = 20 après échange a = 20 b = 10

Programme 3: Utilisation de l’opérateur XOR au niveau du bit:

L’opérateur XOR au niveau du bit peut être utilisé pour échanger deux variables. Le XOR de deux nombres x et y renvoie un nombre qui a tous les bits sous la forme 1 partout où les bits de x et y diffèrent. Par exemple, XOR de 10 (en binary 1010) et 5 (en binary 0101) est 1111 et XOR de 7 (0111) et 5 (0101) est (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; 

Sortie:

Après l’échange: x = 5, y = 10

Programme 4:

Personne n’a encore suggéré d’utiliser std :: swap.

 std::swap(a, b); 

Je n’utilise aucune variable temporaire et, selon le type de a et b, l’implémentation peut avoir une spécialisation non plus. La mise en œuvre doit être écrite en sachant si une «astuce» est appropriée ou non.

Problèmes avec les méthodes ci-dessus:

1) L’approche basée sur la multiplication et la division ne fonctionne pas si l’un des nombres est 0 car le produit devient 0 quel que soit l’autre nombre.

2) Les deux solutions arithmétiques peuvent provoquer un débordement arithmétique. Si x et y sont trop grands, l’addition et la multiplication peuvent sortir de la plage entière.

3) Lorsque nous utilisons des pointeurs sur une variable et effectuons un échange de fonctions, toutes les méthodes ci-dessus échouent lorsque les deux pointeurs pointent vers la même variable. Regardons ce qui se passera dans ce cas si les deux pointent vers la même variable.

// Méthode basée sur le bit XOR

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

// Méthode basée sur l’arithmétique

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

Voyons le programme suivant.

 #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; } 

Sortie :

Après swap (& x, & x): x = 0

Échanger une variable avec elle-même peut être nécessaire dans de nombreux algorithmes standard. Par exemple, consultez cette implémentation de QuickSort où nous pouvons échanger une variable avec elle-même. Le problème ci-dessus peut être évité en mettant une condition avant l’échange.

 #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; } 

Sortie :

Après échange (& x, & x): x = 10

Echanger deux nombres en utilisant la troisième variable soit comme ceci,

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

Échanger deux nombres sans utiliser la troisième variable

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

Peut-être hors sujet, mais si vous savez ce que vous échangez une seule variable entre deux valeurs différentes, vous pourrez peut-être faire de la logique de tableau. Chaque fois que cette ligne de code est exécutée, la valeur sera échangée entre 1 et 2.

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

C’est très simple, mais cela peut déclencher un avertissement.

solution à une seule ligne pour échanger deux valeurs en langage c.

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