Pour commencer en douceur, nous allons tenter de résoudre un problème simple: Comment intervertir le contenu de deux variables? Opération triviale à première vue, mais dès qu'on se penche dessus pour la première fois, on se fait forcément avoir. Un développeur C aura tôt fait d'écrire ceci

/* int a,b */
int buffer = a;
a = b;
b = buffer;

Ce code est d'une élégance toute relative, et l'on voit difficilement comment se passer du tampon pour faire cet échange. Pour les amateurs de one-liners, on pourrait l'écrire sous la forme

/* int a,b */
int buffer; b = (buffer = a, a = b, buffer);

Notez bien la présence des parenthèses pour supprimer toute ambigüité avec une affectation triple.

En pratique, cette méthode consiste à pousser une des variables sur la pile et à l'écraser par l'autre; on termine ensuite l'échange lors de la récupération de la première variable sur la pile. Sous x86, on aurait cette forme-ci en assembleur

mov eax, a
push eax ;buffer =a
mov eax, b
mov a, eax ;a = b
pop eax
mov b, eax ;b = buffer

Tout cela n'est pas très joli. Certes, certains langages supportent ces échanges; c'est le cas de Lua par exemple où il est possible d'écrire directement la ligne suivante

a, b = b, a

En fait, comme beaucoup de langages à machines virtuelles, Lua utilise une pile pour stocker les valeurs retournées et les assigner. Si l'on désassemble la ligne précédente à l'aide de luac, on obtient

1 [3] GETGLOBAL 0 -2 ; b
2 [3] GETGLOBAL 1 -1 ; a
3 [3] SETGLOBAL 1 -2 ; b
4 [3] SETGLOBAL 0 -1 ; a

Lua place les deux variables sur la pile à l'aide de la mnémonique GETGLOBAL puis effectue les affectations à l'aide de SETGLOBAL. Notez qu'il s'agit dans ce cas là de la méthode la plus rapide proposée par Lua; cependant, quand vous êtes sur de l'assembleur, vous pourriez sur certaines architectures et dans certaines conditions privilégier d'autres techniques.

Maintenant, voyons comment jouer un peu avec de l'arithmétique pour faire notre échange. Nous allons pour cela utiliser l'opération OU-Exclusif qui possède une propriété intéressante

a = (a xor b) xor b

Grâce à cela, il est possible de réécrire notre échange en C de la façon suivante

a = a ^ b; //a = a xor b
b = b ^ a; //b = b xor (a xor b) = a
a = a ^ b; //a = (a xor b) xor a = b

Et pour les amateurs d'assembleur, on obtient alors le code suivant

mov eax, a
xor b, eax
mov eax, b
xor a, eax
mov eax, a
xor b, eax

Maintenant, quels sont les avantages réels d'une telle méthode? Sur x86, après désassemblage, on observe que le code naïf en C est à la fois le plus petit, et selon toute vraisemblance le plus rapide si l'on se limite au décompte des accès mémoire nécessaires. Cependant, la méthode du OU-Exclusif présente l'avantage d'être applicable sans avoir besoin de pile ni de mémoire tampon, ce que l'on n'a pas toujours sous la main. Pour finir, si votre machine ne dispose pas de l'opération OU-Exclusif, une machine virtuelle par exemple, il existe une technique similaire à base d'additions et de soustractions que je vous laisse le soin de trouver.

partie II