Échanger la valeur de deux variables sans utiliser la troisième variable

Question

Une des questions très délicates posées lors d'un entretien.

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

Généralement, pour échanger les valeurs de deux variables, nous avons besoin d'une troisième variable :

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

Maintenant, l'exigence est d'échanger les valeurs de deux variables sans utiliser la troisième variable.

Answer 1

Utilisation de la 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 ce test ?

Le test consiste à s'assurer que x et y ont des emplacements mémoire différents (plutôt que des valeurs différentes). Cela est dû au fait que (p xor p) = 0 et si x et y partagent le même emplacement mémoire, lorsque l'un est mis à 0, les deux sont mis à 0. Lorsque *x et *y sont tous deux égaux à 0, toutes les autres opérations xor sur *x et *y seront égales à 0 (puisqu'elles sont identiques), ce qui signifie que la fonction mettra tous deux *x et *y à 0.

S'ils ont les mêmes valeurs mais pas le même emplacement 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 la plupart des cas, non. Le compilateur optimisera la variable temporaire et, étant donné que le swapping est une procédure courante, il devrait produire le code machine optimal pour votre plate-forme.

Prenez par exemple ce programme de test rapide écrit en C.

#include <stdlib.h>
#include <math.h>

#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 xor prend

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

Alors que la version avec la variable temporaire prend :

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

Answer 2

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 un inverse bien défini pour toutes les valeurs pour lesquelles l'opération est définie. Par exemple, * et / fonctionnent jusqu'à ce que A ou B soit égal à 0.

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

Answer 3

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

Answer 4

Personne n'a suggéré d'utiliser std::swap mais pas encore.

std::swap(a, b);

I n'utilisent pas de variables temporaires et selon le type de a et b l'implémentation peut avoir une spécification qui ne le fait pas non plus. L'implémentation 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 ça, 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'intervieweur à cette réponse peut en dire long sur le poste à pourvoir.

Answer 5

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

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

Ici, il faut faire attention aux débordements et aux sous-exécutions, mais sinon, cela fonctionne tout aussi bien. Vous pouvez même l'essayer sur des flottants/doubles au cas où XOR n'est pas autorisé sur ceux-ci.