Ouvrir le menu principal

Les opérations bit à bit/Les subtilités du XOR

< Les opérations bit à bit

Dans cette partie, nous allons voir ce qu'il est possible de faire avec l'instruction XOR. Les techniques suivantes se basent sur les propriétés de l'opération XOR. Pour rappel, nous avons vu au premier chapitre que : et . Ces deux propriétés sont assez importantes, surtout la dernière. La première méthode a été utilisée dans le chapitre sur les masques, aussi nous ne l'utiliserons pas plus.

Sections

Inégalité des signes de deux entiersModifier

Déterminer si deux entiers ont des signes différents peut sembler trivial, mais vous n'aurez peut-être pas pensé que cela pouvait se faire avec une seule comparaison. Un code naïf pour résoudre ce problème devrait utiliser plusieurs comparaisons : une expression pour vérifier si la première variable est positive et l'autre négative (deux comparaisons), et une autre expression pour vérifier l'inverse (deux comparaisons, encore). Le code qui correspond serait le suivant :

int SignUnequals (int a , int b)
{
    return ( a >= 0 && b < 0 ) || ( a < 0 && b >= 0 ) 
}

Mais l'opération XOR permet de faire cette vérification en une seule comparaison. Pour comprendre pourquoi, il faut rappeler que le bit de poids fort donne le signe du nombre, peu importe la représentation des nombres utilisée. Cela fonctionne non seulement en signe-magnitude, mais aussi en complément à 1 ou à 2. Lorsque l'on fait un XOR entre deux nombres, les deux "bits de signe" seront XORés, comme tous les autres bits. OR, l'opération XOR renvoie un 1 si les deux bits sont différents et un 0 s'ils sont égaux ! Ainsi, après avoir XORé les deux nombres, le bit de poids fort dira si les deux bits de signe étaient égaux ou non. Il faudra juste comparer sa valeur avec 1 et/ou 0. Pour cela, on pourrait penser utiliser le code suivant :

int SignUnequals (int a , int b)
{
    return ((a ^ b) >> 31) & 1 ;
}

Mais il y a plus simple encore : on peut déduire le signe du résultat (et donc la valeur du bit de signe) en comparant avec 0 ! Si le résultat a pour bit de signe 1, il est négatif, donc inférieur à 0. Si ce bit de signe vaut 0, le résultat est supérieur ou égal à 0. On peut donc remplacer la sélection du bit de signe assez simplement par une comparaison avec 0. Ce qui donne le code suivant :

int SignUnequals (int a , int b)
{
    return (a ^ b) < 0 ;
}

Émulation d'instructionsModifier

L'instruction XOR permet parfois d'émuler certaines opérations plus complexes. Elle permet notamment d'émuler des transferts entre registres/variables ou des initialisations de registres. Son utilisation première est notamment la mise à 0 d'un registre ou d'une variable.

Mise à zéro rapideModifier

Initialiser une variable à 0 est une opération extrêmement courante. En conséquence, il vaut mieux la rendre la plus rapide possible. S'il n'y a pas de méthode particulière pour cela dans les langages de haut-niveau, les compilateurs ont cependant quelques possibilités d'optimisation. Il y a en effet plusieurs méthodes pour mettre un registre à 0 en assembleur, certaines n'étant compatibles qu'avec certains processeurs. Certains processeurs ont une instruction machine pour mettre à 0 un registre : c'est alors la solution idéale dans la (quasi-)totalité des cas. Sur les architectures n'ayant pas cette instruction, on peut utiliser une instruction MOV (ou équivalent). On peut l'utiliser en adressage immédiat : on place alors la constante 0 dans le registre. D'autres processeurs possèdent un registre spécial, qui conserve en permanence la valeur 0 et n'est pas accessible en écriture. Il suffit alors d'effectuer un MOV de ce registre vers le registre à initialiser. Mais il existe une dernière solution : faire un XOR entre le registre et lui-même. C'est notamment ce qui est fait sur les architectures x86. L'utilisation d'une opération XOR peut permettre d'utiliser moins de cycles d'horloge (exécution plus rapide) et/ou économiser de la mémoire (encodage plus court).

Pour comprendre pourquoi cette solution fonctionne, il faut rappeler que l'on obtient 0 lorsque l'on XOR un bit avec lui-même :  . Si cela vaut pour un bit, cela s'applique aussi quand on effectue un XOR bit à bit sur un nombre : chacun de ses bits sera donc XORé avec lui-même, ce qui fait qu'un nombre XOR lui-même donnera toujours zéro. Cette propriété est utilisé par les compilateurs pour mettre à zéro un registre. Sur les architectures x86, cette solution est légèrement meilleure que celle utilisant un MOV avec adressage immédiat. Cette dernière solution demande d'intégrer une constante en adressage immédiat, qui prend facilement 8 à 16 bits. Un nom de registre est beaucoup plus court, ce qui fait que la solution avec un XOR donne des instructions plus petites. Sur d'autres processeurs, qui ne supportent pas l'adressage immédiat, la constante est lue depuis la mémoire. En comparaison, un XOR entre deux registres ne va rien charger en RAM et est donc plus rapide.

Émulation du MOVModifier

L'opération XOR permet d'émuler une instruction MOV sur les processeurs qui n'en disposent pas, comme certains processeurs MIPS. Le MOV est alors remplacé par une opération XOR à trois adresses, qui XOR le registre à copier avec zéro, et place le résultat dans le registre de destination. L'opération est d'autant plus utile que ces processeurs disposent d'un registre en lecture seule, qui contient toujours la valeur 0.

Pour résumer : MOV Ra -> Rb <=> Ra XOR 0 -> Rb

Échange de deux variablesModifier

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 soustractionModifier

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.

Stupid XOR trickModifier

 
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 était autrefois utilisée comme optimisation par quelques programmeurs, mais a perdu de sa superbe aujourd'hui. En effet, les processeurs modernes peuvent échanger facilement deux registres très rapidement, parfois en 0 cycle d'horloge. Quelques optimisations liées au renommage de registre permettent de réaliser cet échange en 0 cycles, bien plus rapidement qu'avec la méthode abordée. En conséquence, cette méthode est utilisable seulement sur les petits microcontrôleurs qui ne possèdent que très peu de registres, dans un objectif d'optimisation certain. Ce qui réduit largement son utilité...

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 pointeursModifier

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

Listes chainées XORModifier

 
Liste doublement chainée normale.
 
Liste chainée XOR.

La propriété   est aussi utilisée pour créer des listes doublement chainées plus économes en mémoire que la normale, appelées listes chainées XOR. Une liste doublement chainée normale stocke deux pointeurs : un vers le nœud suivant, et un vers le nœud précédent. Les XOR linked list permettent de ne pas stocker les deux pointeurs : à la place ils stockent un seul pointeur. Celui-ci contient le XOR entre le pointeur vers le prochain nœud, et le pointeur vers le nœud précédent. Ainsi, on gagne un petit peu de mémoire : au lieu de stocker deux pointeurs, on n'en stocke plus qu'un seul. La consommation mémoire est aussi identique à celle d'une liste simplement chainée.

Dans ce qui suit, le pointeur sur le nœud précédent sera noté P (pour Précédent), le pointeur contenu dans le nœud actuellement visité est appelé Ptr et le pointeur vers le nœud suivant sera noté S (pour Suivant). Pour rappel, le pointeur stocké dans le nœud est égal au XOR entre P et S :  . Traverser cette liste ne se fait que dans un sens : soit on part du début pour arriver à la fin, soit on va dans l'autre sens. Dans ce qui suit, on étudiera un parcours commençant par le début de la liste vers la fin de celle-ci. Obtenir le pointeur vers le prochain élément demande de faire un XOR entre le pointeur vers l’élément précédent avec le pointeur stocké dans le nœud. En effet,  . Ce calcul donne l'adresse du prochain nœud dans la liste. Le même raisonnement peut s'adapter dans le cas où l'on parcours la liste dans l'autre sens., si ce n'est qu'il faut XORer le pointeur de l’élément précédemment visité (qui correspond alors à Next) avec le pointeur stocké dans le nœud.