Différences entre les versions de « Les opérations bit à bit/Les subtilités du XOR »

m
m
 
Pour résumer : MOV Ra -> Rb <=> Ra XOR 0 -> Rb
 
==É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 :
 
<syntaxhighlight lang="c">
int t = a ;
a = b ;
b = t ;
</syntaxhighlight>
 
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 :
 
* <math>A = A - B</math> ;
* <math>B = A + B</math>;
* <math>A = B - A</math>.
 
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.
 
{|class="wikitable"
|-
!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.
 
===Stupid XOR trick===
 
[[File:XOR Swap - color coded.svg|vignette|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 :
 
* <math>A = A \oplus B</math> ;
* <math>B = A \oplus B</math>;
* <math>A = A \oplus B</math>.
 
Le code source correspondant, en C/C++, est un joli oneliner :
 
<syntaxhighlight lang="c">
x ^= y ^= x ^= y ;
</syntaxhighlight>
 
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 <math> ( x \oplus y ) \oplus y = x </math>. Faites les calculs vous-même : <math> ( x \oplus y ) \oplus y = x \oplus ( y \oplus y ) = x \oplus 0 = x</math>. 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.
 
{|class="wikitable"
|-
!Etape
!Variable A
!Variable B
|-
|Avant l'opération
|A
|B
|-
|Première étape
|<math>A \oplus B</math>
|B
|-
|Seconde étape
|<math>A \oplus B</math>
|<math>(A \oplus B) \oplus B</math>
|-
|Troisième étape
|<math>((A \oplus B) \oplus B) \oplus (A \oplus B)</math>
|<math>(A \oplus B) \oplus B</math>
|}
 
Vu que XOR est associatif, commutatif, distributif, on peut alors supprimer les parenthèses. Les identités <math>a \oplus a = 0</math> et <math>a \oplus 0 = a</math> nous permettent alors de simplifier fortement les expressions. Les simplifications précédentes donnent :
 
{|class="wikitable"
|-
!Etape
!Variable A
!Variable B
|-
|Avant l'opération
|A
|B
|-
|Première étape
|<math>A \oplus B</math>
|B
|-
|Seconde étape
|<math>A \oplus B</math>
|<math>(A \oplus B) \oplus B</math>
|-
|Troisième étape
|<math>((A \oplus B) \oplus B) \oplus (A \oplus B)</math>
|<math>(A \oplus B) \oplus B</math>
|}
 
Ce qui se simplifie en :
 
{|class="wikitable"
|-
!Etape
!Variable A
!Variable B
|-
|Avant l'opération
|A
|B
|-
|Première étape
|<math>A \oplus B</math>
|B
|-
|Seconde étape
|<math>A \oplus B</math>
|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 :
<syntaxhighlight lang="c">
void exchangeIntegers(int* px, int* py)
{
*px ^= *py ^= *px ^= *py ;
}
</syntaxhighlight>
 
Dans le cas où l'on passe deux adresses différentes, aucun problème ne se produit :
<syntaxhighlight lang="c">
int a = 5;
int b = 10;
exchangeIntegers(&a, &b);
</syntaxhighlight>
 
Dans le cas où l'on passe deux adresses identiques, la variable pointée est remise à zéro (a XOR a) :
<syntaxhighlight lang="c">
int a = 5;
exchangeIntegers(&a, &a);
</syntaxhighlight>
 
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.
<syntaxhighlight lang="c">
void exchangeIntegers(int* px, int* py)
{
if (px != py) *px ^= *py ^= *px ^= *py ;
}
</syntaxhighlight>
 
==Listes chainées XOR==
38 132

modifications