Les opérations bit à bit/L'échange de deux variables
Si je vous demande d'échanger le contenu de deux entiers a et b, vous allez certainement écrire un code similaire à celui-ci :
int t = a ;
a = b ;
b = t ;
Mais il est possible d'échanger les valeurs de deux registres/variables, sans utiliser de registre/variable temporaire ! Pour cela, il existe différentes méthodes assez simples.
L'échange de deux variables par addition et soustraction
modifierLa première méthode alternative qui utilise des additions et soustractions. Il faut effectuer ces opérations dans l'ordre suivant :
- ;
- ;
- .
Pour comprendre plus profondément pourquoi cette méthode marche, il suffit de regarder à chaque étape ce que l'on trouve dans A et dans B.
| Étape | Variable A | Variable B |
|---|---|---|
| Avant l'opération | A | B |
| Première étape | A - B | B |
| Seconde étape | A - B | B + (A - B) = A |
| Troisième étape | A - (A - B) = B | A |
Cependant, il y a un risque de débordement au niveau de l'addition, qui fait que cette technique fonctionne mal avec certaines opérandes. Cette technique utilise de plus des opérations arithmétiques, qui sont plus lentes que les opérations logiques sur de nombreux processeurs. Bref : il n'y a pas vraiment de raisons d'utiliser cette méthode. Son seul intérêt est d'économiser un registre, mais cette économie ne compense pas le fait que le code avec addition/soustraction est plus lent.
Le Stupid XOR trick
modifier
Une autre méthode se base sur les particularités de l'instruction XOR et est connue sous le nom de stupid XOR trick chez nos amis anglo-saxons. Il est en effet possible d'échanger le contenu de deux registres/variables A et B en effectuant les opérations suivante, dans l'ordre :
- ;
- ;
- .
Le code source correspondant, en C/C++, est un joli oneliner :
x ^= y ^= x ^= y ;
Cette technique était utilisée comme optimisation sur les anciens processeurs, sur lesquels les opérations bit à bit étaient plus rapides que les opérations arithmétiques. Mais les processeurs modernes peuvent échanger facilement deux registres très rapidement par simple renommage, en une seule instruction pouvant prendre un seul cycle d'horloge. En conséquence, cette méthode n'est utile que sur les anciens processeurs et les petits microcontrôleurs qui ne possèdent que très peu de registres, dans un objectif d'optimisation certain.
Fonctionnement du trick
modifierLe fonctionnement de cette méthode se base sur le fait que . Faites les calculs vous-même : . Pour comprendre plus profondément pourquoi cette méthode marche, il suffit de regarder à chaque étape ce que l'on trouve dans A et dans B.
| Étape | Variable A | Variable B |
|---|---|---|
| Avant l'opération | A | B |
| Première étape | B | |
| Seconde étape | ||
| Troisième étape |
Vu que XOR est associatif, commutatif, distributif, on peut alors supprimer les parenthèses. Les identités et nous permettent alors de simplifier fortement les expressions. Les simplifications précédentes donnent :
| Étape | Variable A | Variable B |
|---|---|---|
| Avant l'opération | A | B |
| Première étape | B | |
| Seconde étape | ||
| Troisième étape |
Ce qui se simplifie en :
| Étape | Variable A | Variable B |
|---|---|---|
| Avant l'opération | A | B |
| Première étape | B | |
| Seconde étape | A | |
| Troisième étape | B | A |
Comme on le voit, nos données ont bien étés inversées.
Piège avec les pointeurs
modifierIl faut faire attention au cas où des pointeurs sont utilisés pour adresser indirectement les variables à échanger, par exemple si une fonction est créée pour procéder à l'échange, comme celle-ci :
void exchangeIntegers(int* px, int* py)
{
*px ^= *py ^= *px ^= *py ;
}
Dans le cas où l'on passe deux adresses différentes, aucun problème ne se produit :
int a = 5;
int b = 10;
exchangeIntegers(&a, &b);
Dans le cas où l'on passe deux adresses identiques, la variable pointée est remise à zéro (a XOR a) :
int a = 5;
exchangeIntegers(&a, &a);
Ce n'est pas l'effet voulu par la fonction. Il faut donc soit utiliser la technique de la variable intermédiaire qui n'a pas ce problème, soit vérifier les adresses passées en paramètres.
void exchangeIntegers(int* px, int* py)
{
if (px != py) *px ^= *py ^= *px ^= *py ;
}