« Les opérations bit à bit/L'échange de deux variables » : différence entre les versions

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
Ligne 43 : Ligne 43 :
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.
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.


==Stupid XOR trick==
==Le ''Stupid XOR trick''==


[[File:XOR Swap - color coded.svg|vignette|Stupid XOR Trick.]]
[[File:XOR Swap - color coded.svg|vignette|Stupid XOR Trick.]]

Version du 24 octobre 2021 à 23:41

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.

Échange par addition et soustraction

La 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.

Etape 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.

Le Stupid XOR trick

Stupid XOR Trick.

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 ;

Toutefois il faut faire attention quand les variables utilisées sont indirectement accédées à travers des pointeurs ou des références : il ne faut pas que les deux pointeurs ou références pointent la même adresse mémoire, sinon le contenu est perdu et remis à zéro.

Cette technique est utilisée comme optimisation, notamment en assembleur, car les anciens processeurs effectuent les opérations arithmétiques, comme l'addition et la soustraction utilisées par la première technique, plus lentement que les opérations binaires comme le XOR utilisé par la deuxième. Tandis que 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 reste utile 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.

Le 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.

Etape 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 :

Etape Variable A Variable B
Avant l'opération A B
Première étape B
Seconde étape
Troisième étape

Ce qui se simplifie en :

Etape 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

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