Comment échanger les valeurs des variables sans utiliser une troisième variable ?

Échanger les valeurs de variables sans troisième variable

L'une des questions classiques d'entretien est de savoir comment échanger les valeurs de deux variables sans utiliser une troisième variable comme espace de stockage temporaire . Généralement, cela se fait à l'aide d'une variable temporaire comme suit :

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

Cependant, cette approche nécessite une allocation et une manipulation de mémoire supplémentaires. Une solution alternative consiste à utiliser l'algorithme d'échange XOR.

L'algorithme d'échange XOR

L'algorithme d'échange XOR fonctionne en exploitant l'opération OU exclusif (XOR). L'opérateur XOR a la propriété qu'un XOR a renvoie toujours 0, tandis qu'un XOR b renvoie a si b vaut 0 et b si a vaut 0.

En utilisant cette propriété, nous pouvons échanger les valeurs de deux variables x et y comme suit :

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

Pourquoi fonctionne :

1. Vérification de l'emplacement mémoire : Nous vérifions d'abord si x et y ont des emplacements mémoire différents. Ceci est essentiel car s'ils partagent le même emplacement mémoire, l'échange ne fonctionnera pas.

2. Opérations XOR : Nous effectuons ensuite les opérations XOR suivantes dans l'ordre :

   • *x ^= *y : Ceci définit *x sur *x XOR *y.
   • *y ^= *x : Cela définit *y à *y XOR *x, qui est *x car *x XOR *x est 0.
   • *x ^= *y : Enfin, nous définissons *x sur *x XOR *y, qui est *y car *x XOR *x est 0.

À la suite de ces opérations, *x contient désormais la valeur originale de *y, et *y contient la valeur originale de *x.

Exemple de code

Voici un exemple de la façon d'utiliser l'algorithme d'échange XOR en C :

#include <stdio.h>

int main() {
    int a = 10;
    int b = 15;

    printf("Before swap: a = %d, b = %d\n", a, b);

    xorSwap(&a, &b);

    printf("After swap: a = %d, b = %d\n", a, b);

    return 0;
}</stdio.h>

Sortie :

Before swap: a = 10, b = 15
After swap: a = 15, b = 10

Considérations

Bien que l'algorithme d'échange XOR soit efficace et élimine le besoin d'un troisième variable, ce n’est pas toujours la solution la plus optimale. Dans de nombreux cas, le compilateur optimisera le code en utilisant la méthode plus traditionnelle avec une variable temporaire. Par conséquent, il est important de prendre en compte les exigences spécifiques de votre programme avant d'utiliser l'algorithme d'échange XOR.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!