Les opérations bit à bit/Version imprimable

Les opérations bit à bit

Une version à jour et éditable de ce livre est disponible sur Wikilivres,
une bibliothèque de livres pédagogiques, à l'URL :
https://fr.wikibooks.org/wiki/Les_op%C3%A9rations_bit_%C3%A0_bit

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la Licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans Texte de dernière page de couverture. Une copie de cette licence est incluse dans l'annexe nommée « Licence de documentation libre GNU ».

Les opérations bit à bit

Pour commencer ce livre, nous devons d'abord parler des opérations logiques : que sont-elles, à quoi servent-elles ? Ces opérations logiques travaillent sur des suites de bits d'une longueur fixe, des nombres pour simplifier. Ces opérations modifient directement l'écriture binaire d'un nombre, la suite de bits correspondante. Il en existe de deux types, les instructions bit à bit et les instructions de décalage, que nous allons voir l'une après l'autre. Pour les connaisseurs, nous allons voir quelques opérations iconiques, comme les décalages et les rotations, mais aussi comment concevoir une unité de calcul 2 à 3 bits, les masques et quelques autres opérations.

Les opérations bit à bit proprement dit

Les instructions logiques les plus courantes sont au nombre de 4 : le NON, le ET, le OU, et le XOR. Toutes ces instructions vont travailler sur des bits individuels d'un ou de deux nombres, et leur faire subir une opération bien précise. Cette opération prend deux bits (un seul pour le NON) et donne un résultat codé sur un bit. Le fonctionnement de cette opération peut être définie par ce qu'elle fait sur un bit, son comportement étant résumé dans un tableau qu'on appelle la table de vérité. Leur résultat n'est pas vraiment interprétable mathématiquement, ou alors avec un sens vraiment idiosyncratique. La plus simple est clairement l'opération NOT, qui inverse tous les bits d'un nombre. Mais il est aussi possible de prendre deux nombres, de faire un ET/OU/XOR entre les bits de même poids, et de renvoyer le tout en guise de résultat. Formellement, ce sont les seuls types d'opérations bits à bit : l'inversion des bits d'un nombre, un ET entre deux nombres, un OU entre deux nombres, et un XOR entre deux nombres (avec leurs dérivées, tel un NAND ou un NOR).

L’opération d'inversion (NOT)

L'inversion bit à bit va inverser tous les bits d'un nombre : les 0 deviennent des 1, et les 1 deviennent des 0. Exemple : le nombre 01110011 va devenir 10001100.

La table de vérité du NOT est celle-ci :

Bit A	Résultat (NOT A)
0	1
1	0

Le NOT d'un bit et/ou d'un nombre sera noté comme ceci : ${\overline {a}}$.

Notation
dans ce livre	${\overline {x}}$
quelques autres notations	$NOT(x)$	$\neg x$	$\sim x$

On peut remarquer qu'inverser deux fois de suite un bit redonne le bit initial. Autrement dit, ${\overline {\overline {a}}}=a$.

La droite Δ d’équation x = − 1/2 partage le domaine des opérations bit à bit en deux moitiés, contenant chacune 2^31 nombres entiers. L’opérateur NOT transforme un entier n donné en – (n + 1), en inversant les valeurs de ses trente-deux bits. La symétrie d’axe Δ donne une image mentale de cette inversion des bits.

Le résultat de cette opération dépend de l'encodage du nombre. Plus précisément, l'interprétation du résultat n'est pas la même selon que le nombre inversé soit non-signé, en complément à 1, en complément à 2, etc.

• Pour un entier en complément à 1, le NOT sert à obtenir l'opposé d'un nombre : dit autrement, ${\overline {x}}=-x$.
• Pour un entier en complément à deux, le NOT donne l'opposé d'un nombre auquel on aurait retranché 1 : ${\overline {x}}=-x-1$.
• Pour un entier non-signé, le NOT va donner la valeur ${\overline {x}}=2^{n}-1-x$.

Le dernier résultat est facile à comprendre. On sait que la somme ${\overline {x}}+x$ donne un nombre de n bits dont tous les bits sont à 1. Un tel nombre vaut exactement, par définition, $2^{n}-1$. On a donc ${\overline {x}}+x=2^{n}-1$, ce qui donne le résultat précédent avec quelques manipulations algébriques triviales. L'image de droite montre ce que fait l'opérateur NOT sur un entier en complément à deux.

L'opération ET (AND)

Vient ensuite le ET bit à bit, aussi appelé AND bit à bit. Celui-ci prend deux nombres en opérandes et donne un nombre comme résultat. Sur ces deux nombres, il va prendre les bits qui sont à la même place et va effectuer dessus une petite opération qui donnera le bit du résultat. Cette opération est un simple AND binaire. Ce AND binaire prend deux bits, A et B, et fonctionne comme ceci :

Bit a	Bit b	Résultat
0	0	0
0	1	0
1	0	0
1	1	1

Cet opérateur AND bit à bit est symbolisé comme ceci : $a.b$. Le symbole de l'opérateur ET ressemble à celui d'un produit car l'opérateur donne effectivement le résultat de la multiplication bit à bit.

Exemple : $1100.1010=1000$

Notation
dans ce livre	$a.b$
quelques autres notations	a AND b	a & b	$a\land b$

L'instruction AND bit à bit est commutative : $a.b=b.a$

Elle est aussi associative : $(a.b).c=a.(b.c)$

Elle est aussi distributive avec le OR bit à bit : $(a+b).c=(c.b)+(c.a)$

On peut aussi remarquer qu'elle dispose de la propriété d'idempotence : $a.a=a$

Petite remarque : $a.0=0$

De plus, $a.{\overline {a}}=0$

L'opération OU (OR)

Vient ensuite le OR bit à bit. Il fonctionne comme le AND bit à bit sauf qu'il effectue un OR binaire entre les bits du nombre. Ce OR binaire prend deux bits, A et B, et fonctionne comme ceci :

Bit a	Bit b	Résultat
0	0	0
0	1	1
1	0	1
1	1	1

Cet opérateur OR bit à bit est symbolisé comme ceci : $a+b$. Pour éviter toute ambiguïté en présence d'addition, nous utiliserons parfois le symbole $|$ dans la suite du cours.

Exemple : $1100+1010=1110$

Notation
dans ce livre	$a+b$ (a ne pas confondre avec l'addition !)
dans ce livre	$a|b$
quelques autres notations	a OR b	$a\lor b$

L'opérateur OR est commutatif : $a+b=b+a$

Il est aussi associatif : $(a+b)+c=a+(b+c)$

Il est aussi distributif avec le AND bit à bit : $(a.b)+c=(c+b).(c+a)$

On peut aussi remarquer qu'il dispose de la propriété d'idempotence : $a+a=a$

Petite remarque : $a+0=a$

L'opération OU exclusif (XOR)

Vient ensuite le OU exclusif bit à bit, appelé XOR en anglais (eXclusive OR). Il fonctionne comme le AND et le OR bit à bit sauf qu'il effectue un XOR binaire entre les bits du nombre. Ce XOR binaire prend deux bits, A et B, et fonctionne comme ceci :

Bit a	Bit b	Résultat
0	0	0
0	1	1
1	0	1
1	1	0

Le résultat est 0 quand les deux bits sont égaux, et 1 quand les deux bits sont différents.

Cet opérateur XOR bit à bit est symbolisé comme ceci : $a\oplus b$ comme une addition bit à bit sans retenue.

Exemple : $1100\oplus 1010=0110$

Notation
dans ce livre	$a\oplus b$
quelques autres notations	a XOR b	a^b

L'opérateur XOR est commutatif : $a\oplus b=b\oplus a$

Il est aussi associatif : $(a\oplus b)\oplus c=a\oplus (b\oplus c)$

Petite remarque : $a\oplus 0=a$

Autre remarque : $a\oplus a=0$

Les décalages et rotations

À côté des opérations précédentes, on trouve les opérations de décalage, qui décalent un nombre binaire de un ou plusieurs rangs vers la gauche ou la droite. A priori, cette opération n'a rien de compliqué, à un détail près : lorsqu'on décale un nombre, certains bits sont inconnus, ce qui laisse des vides qu'il faut combler. Pour résoudre ce petit problème, il existe diverses solutions, qui donnent naissance à plusieurs types de décalages : les décalages logiques, les décalages arithmétiques et les rotations.

Les décalages logiques

L'idée la plus immédiate serait de remplir ces vides avec des zéros, ce qui donne un décalage logique. Pour un décalage vers la gauche, l'opération similaire en décimal serait d'ajouter des zéros à la fin d'un nombre, ce qui serait équivalent à multiplier par 10, 100, 1000, bref : par une puissance de 10. Un décalage à droite reviendrait en binaire à décaler la position de la virgule d'un cran vers la gauche et à oublier ce qu'il y a après la virgule, ce qui revient à diviser par une puissance de dix. Cette logique vaut aussi pour le décalage en binaire, si on se rappelle toutefois qu'on doit compter en base 2. Un décalage logique à gauche correspond donc à une multiplication ou division par 2, 4, 8, 16, ..., bref, par une puissance de deux.

Décalage logique à gauche.

Décalage logique à droite.

L'utilité principale des opérations de décalage est donc qu'elles permettent de faire simplement des multiplications ou divisions par $2^{n}$, pour les entiers non signés. Précisément, un décalage vers la gauche de $n$ rangs est équivalent à une multiplication par $2^{n}$, alors que le décalage vers la droite qui revient à diviser un nombre entier par $2^{n}$. Cette propriété est souvent utilisée par certains compilateurs, qui préfèrent utiliser des instructions de décalages (qui sont des instructions très rapides) à la place d'instructions de multiplication ou de division qui ont une vitesse qui va de moyenne (multiplication) à particulièrement lente (division). Il faut cependant signaler que lorsqu'on effectue un décalage à droite, certains bits de notre nombre vont sortir du résultat et être perdus : le résultat est tronqué ou arrondi vers zéro. Plus précisément, le résultat d'un décalage à droite de n rangs sera égal à la partie entière du résultat de la division par $2^{n}$.

Le tableau ci-dessous indique les notations utilisées pour les décalages.

Notation
	Décalage à gauche	Décalage à droite
dans ce livre	$x<<n$	$x>>n$
quelques autres notations	$SHL^{n}(x)$	$SHR^{n}(x)$

Les décalages arithmétiques

Décalage arithmétique.

Le décalage logique ne donne cependant pas de bons résultats avec des nombres signés négatifs : on obtient un résultat qui n'a pas grand sens mathématiquement. Il faut dire que le bit de signe est alors remplacé par un zéro, ce qui peut inverser le signe du résultat. Une solution intuitive est de conserver le bit de signe, de ne pas le décaler. Mais en faisant cela, que mettre dans le bit situé juste avant le bit de poids fort après décalage ? On pourrait penser mettre un zéro dedans, mais cela ne donnerait pas le bon résultat avec les nombres négatifs. La solution est en fait de recopier le bit de signe dans ce bit. Tout se passe comme si on faisait le décalage normalement, comme un décalage logique, mais que le bit de poids fort était cependant conservé au lieu d'être remplacé par un zéro. Ce faisant, le bit de signe est conservé et le décalage est malgré tout effectué correctement.

En faisant cela, on obtient un décalage qui effectue correctement des multiplications/divisions par $2^{n}$ sur des nombres signés. De tels décalages sont appelés décalages arithmétiques (arithmetical shift en anglais). La différence avec un décalage logique est la méthode d'arrondi des nombres négatifs. Avec les décalages arithmétiques, les nombres négatifs sont arrondis vers moins l'infini. Pour donner un exemple, 92 sera arrondi en 4, tandis que −92 sera arrondi en −5.

Les rotations de bits

Les rotations sont identiques aux décalages, à part que les bits qui sortent du nombre sont ceux qui rentrent pour combler les vides.

Rotation à gauche.

Rotation à droite.

Ces opérations sont très utiles en cryptographie, et sont notamment très utilisées dans certains algorithmes de chiffrement. Les rotations sont aussi très utiles dans certains cas particuliers dans lesquels on doit manipuler des données bits par bits. Par exemple, un calcul du nombre de bits à 1 dans un nombre peut s'implémenter de façon naïve avec des instructions de rotation.

Le tableau ci-dessous indique les notations utilisées pour les rotations.

Notation
Rotation à gauche	Rotation à droite
$ROTL^{n}(x)$	$ROTR^{n}(x)$

Quelques règles de calcul utiles

Dans la suite du cours, nous ferons souvent usage de quelques équations qui mélangerons les différentes opérations bit à bit. Ne vous étonnez donc pas si vous voyez des équations de ce style :

${\overline {a}}.b.\left[(c+{\overline {d}})\oplus (d+a)\right]$

Il existe quelques règles mathématiques qui nous permettront de simplifier de telles équations.

Les règles pour les expressions booléennes

Commençons par les règles qui impliquent uniquement des opérations bit à bit/booléens. Nous en avons déjà vu la plus grande partie plus haut, en parlant de la distributivité et de l'associativité des différents opérateurs. En voici la liste complète :

Commutativité	$a+b=b+a$ $a.b=b.a$ $a\oplus b=b\oplus a$
Associativité	$(a+b)+c=a+(b+c)$ $(a.b).c=a.(b.c)$ $(a\oplus b)\oplus c=a\oplus (b\oplus c)$
Distributivité	$(a+b).c=(c.b)+(c.a)$ $(a.b)+c=(c+b).(c+a)$
Idempotence	$a.a=a$ $a+a=a$
Élément nul	$a.0=0$ $a+1=1$
Élément Neutre	$a.1=a$ $a+0=a$ $a\oplus 0=a$
Loi de De Morgan	${\overline {a}}+{\overline {b}}={\overline {a.b}}$ ${\overline {a}}.{\overline {b}}={\overline {a+b}}$
Complémentarité	${\overline {\overline {a}}}=a$ $a+{\overline {a}}=1$ $a.{\overline {a}}=0$ $a\oplus {\overline {a}}=1$ $a\oplus a=0$ $a\oplus 1={\overline {a}}$

Les règles pour les expressions booléennes et arithmétiques

Il est parfaitement possible de mixer des opérations booléennes avec des opérations arithmétiques. Par exemple, on peut se demander ce que vaut ${\overline {x-y}}$, un calcul qui sera notamment beaucoup utilisé dans la suite du cours. Les règles qui régissent les mélanges/interactions entre opérations mathématiques et opérateurs bit à bit dépendent du codage des nombres, notamment pour les nombres signés. Nous allons supposer que les nombres signés sont codés en complètement à deux. Les règles qui en découlent sont résumées dans le tableau suivant :

Addition	$x+y=(x.y)<<1+(x\oplus y)$ $x+y=(x|y)<<1-(x\oplus y)$ $x+y=(x|y)+(x.y)$ ${\overline {x+y}}={\overline {x}}-y$
Soustraction	$x-y=x+{\overline {y}}+1$ $x-y=(x.{\overline {y}})-({\overline {x}}.y)$ $x-y=(x\oplus y)-\left[({\overline {x}}.y)<<1\right]$ ${\overline {x-y}}={\overline {x}}+y$
Opposé	$-y={\overline {y}}+1$ $-y={\overline {y-1}}$ ${\overline {y}}=-y-1$ $-{\overline {y}}=y+1$ ${\overline {-y}}=y-1$

Les équations pour l'opposé et la soustraction peuvent se déduire assez facilement de l'équation $-y={\overline {y}}+1$, définition de l'opposée d'un nombre en complètement à deux. En guise d'exercice, vous pouvez tenter d'en déduire l'équation ${\overline {x-y}}={\overline {x}}+y$. Si vous utilisez les règles sur les opérateurs booléens, vous devriez y arriver sans trop de peine.

Les règles pour les expressions booléennes et comparaisons

Il est parfaitement possible de comparer des expressions booléennes, et certaines égalités ou inégalités sont toujours vraies. On peut rapidement se rendre compte que :

$x.y\leq x\oplus y\leq x|y$

Pour les opérations mathématiques, les relations suivantes sont importantes à connaître :

$x|y\geq max(x,y)$ ;

$x.y\leq min(x,y)$ ;

$abs(x-y)\leq x\oplus y$.

Les masques

Dans ce chapitre, nous allons aborder la technique dite des masques. Elle permet de mettre à 0 ou à 1 certains bits dans un nombre. Les bits à modifier peuvent être choisis et il est possible de modifier certains bits sans toucher aux autres. Nous allons d'abord voir les masques proprement dit, mais aussi à quoi cette technique peut servir. Dans ce qui va suivre, nous allons d'abord voir comment modifier un bit dans un nombre, sans toucher aux autres. Nous verrons notamment les champs de bits et quelques autres applications.

Modifier un bit

Modifier des bits individuellement dans un nombre demande naturellement d'utiliser des opérations bit à bit. Suivant ce que l'on veut faire, l'instruction utilisée sera différente, mais le principe reste le même. Il suffit d'effectuer une instruction bit à bit entre notre nombre, et une constante bien précise.

Mettre un bit à 1

Tout d'abord, nous allons voir comment mettre à 1 un bit dans un nombre. Pour cela, nous allons utiliser une opération bit à bit entre le nombre en question, et un nombre appelé masque qui indique les bits à mettre à 1. Si le bit du masque est à 0, cela signifie que le bit du nombre, situé à la même place, ne doit pas être modifié. Mais si le bit du masque est à 1, le bit du nombre devra être mis à 1. Par exemple, pour modifier le 4éme bit d'un nombre en partant de la droite, le masque est une constante dont le 4éme bit en partant de la droite est 1, et le reste des bits est à 0, soit la constante : 000000001000.

Nous allons devoir trouver quelle opération bit à bit convient. Rien de compliqué au demeurant : il suffit d'écrire la table de vérité de cette opération et de reconnaître la porte logique.

Nombre	Masque	OURésultat
0	0	0
0	1	1
1	0	1
1	1	1

On remarque que l’opération bit à bit à effectuer est un OU.

Mettre un bit à 0

Mettre un bit à 0 dans un nombre fonctionne sur le même principe que mettre un bit à 1 : on effectue une opération bit à bit entre le nombre en question et un masque qui indique quels bits mettre à 0. Encore une fois, écrire la table de vérité de l'opération nous donne l'opération bit à bit à effectuer. Il s’avère que c'est un ET bit à bit.

Nombre	Masque	ETRésultat
0	0	0
0	1	0
1	0	0
1	1	1

On peut se demander à quoi peut bien servir de mettre à 0 certains bits. L'utilité première est d'accéder à un bit particulier dans un nombre, ou à des groupes de bits. Un cas classique est celui de la sélection du bit de signe, pour calibrer certaines opérations arithmétiques. Dans ce cas, on va mettre à zéro les bits inutiles avant d'effectuer un décalage pour caler ces bits à droite. Mais d'autres utilisations plus importantes existent. Par exemple, vous avez peut-être déjà entendu parler des masques de sous-réseau, dans des cours sur le protocole IP. Ceux-ci permettent de mettre à 0 certaines bits d'une adresse IP pour obtenir une adresse de sous-réseau. L'obtention de l'adresse de sous-réseau s'effectue avec un simple ET entre l'adresse IP et le masque de sous-réseau. Et ce n'est là qu'un exemple parmi tant d'autres !

Inverser un bit

Le même raisonnement que pour les deux opérations précédentes vaut aussi pour ce qui est de l'inversion d'un bit. On obtient alors l'opération XOR à partir de la table de vérité.

Nombre	Masque	XORRésultat
0	0	0
0	1	1
1	0	1
1	1	0

Les champs de bits

Dans certains cas précis, il arrive que certaines informations soient codées sur un nombre limité de bits, qui peuvent être rassemblés dans un seul entier. De telles structures, formées en concaténant des bits dans un seul entier, sont appelées des champs de bits. Pour donner un exemple d'utilisation, supposons que j'ai regroupé plusieurs bits, dont chacun a une signification bien précise. Par exemple, je peux regrouper les droits d'accès dans un fichier dans un nombre : un des bits du nombre me dira alors si je peux écrire dans le fichier, un autre me dira si je peux le lire, un autre si… Bref, si jamais je veux modifier mes droits en écriture de mon fichier, je dois mettre un bit bien précis à 1 ou à 0 (suivant la situation). Cela peut se faire facilement en utilisant une instruction bit à bit entre ce nombre et une constante bien choisie.

Un autre cas typique est celui où un développeur compacte plusieurs données dans un seul entier. Par exemple, prenons le cas d'une date, exprimée sous la forme jour/mois/année. Un développeur normal stockera cette date dans trois entiers : un pour le jour, un pour le mois, et un pour la date. Mais un programmeur plus pointilleux sera capable d'utiliser un seul entier pour stocker le jour, le mois, et l'année. Pour cela, il raisonnera comme suit :

• un mois comporte maximum 31 jours : on doit donc encoder tous les nombres compris entre 1 et 31, ce qui peut se faire en 5 bits ;
• une année comporte 12 mois, ce qui tient dans 4 bits ;
• et enfin, en supposant que l'on doive gérer les années depuis la naissance de Jésus jusqu'à l'année 2047, 11 bits peuvent suffire.

Dans ces conditions, notre développeur décidera d'utiliser un entier de 32 bits pour le stockage des dates :

• les 5 bits de poids forts serviront à stocker le jour ;
• les 4 bits suivant stockeront le mois ;
• et les bits qui restent stockeront l'année.

Dans cette situation, le développeur qui souhaite modifier le jour ou le mois d'une date devra modifier une partie des bits, tout en laissant les autres intacts. Encore une fois, cela peut se faire facilement en utilisant une instruction bit à bit entre ce nombre et une constante bien choisie.

Supposons que le développeur veuille récupérer le jour stocké dans cette date. Comment doit-il s'y prendre ? Rien de plus simple : il suffit de mettre tous les autres bits du nombre à zéro, et de décaler le tout pour placer le résultat sur le bit de poids faible. Il suffit juste de choisir le bon décalage, et la bonne constante. Toutefois, cette méthode a un défaut : les constantes utilisées sont souvent très longues, ce qui empêche d'utiliser le mode d'adressage immédiat pour celles-ci. Raccourcir ces constantes permet de gagner pas mal de place. On peut ruser un petit peu en effectuant le décalage avant la mise à zéro.

Le cas le plus simple est quand le développeur souhaite récupérer un seul bit. Par exemple, si je veux récupérer le 5 éme bit en partant de la droite dans le nombre 1111 0011. Il me suffit de mettre tous les bits à zéro, sauf le bit voulu. Pour cela, je dois effectuer un AND entre 1111 0011 et la constante 0001 0000. J'obtiens alors 0001 0000. Ensuite, un décalage logique de 4 rangs vers la droite me donnera le bit voulu : 0000 0001. Autre exemple : je décale mon nombre 1111 0011 de 4 rangs vers la droite. J'obtiens 0000 1111. Ensuite, je mets tous les bits à zéro, sauf le bit de poids faible. La constante à utiliser est alors 0000 0001. Dans cette situation, on remarque que la constante à utiliser est très courte : c'est 1. Cette constante est très courte, ce qui permet d'utiliser le mode d'adressage immédiat pour l'instruction AND. De quoi gagner quelques cycles.

Le poids de Hamming

Il arrive qu'on ait besoin de compter les bits d'un certain nombre. Par exemple, certaines application en cryptographie ont besoin de savoir combien de bits sont à 1 dans un nombre. Même chose pour la détection ou correction d'erreurs de transmission entre deux composants électroniques. Certaines de ces opérations, comme le poids de Hamming, se calculent fort bien avec des opérations bit à bit. Le poids de Hamming d'un nombre est le nombre de ses bits qui sont à 1. Ce calcul est souvent effectué quand on cherche à vérifier l'intégrité de données transmises ou stockées sur un support peu fiable et il est à la base d'un grand nombre de code de détection ou de correction d'erreurs usuels. Ce calcul est tellement fréquent que certains processeur disposent d'une instruction dédiée pour le calcul du poids de Hamming. Alors certes, ces architectures sont surtout des architectures anciennes, comme les SPARC, les CDC ou autres processeurs Cray. Mais à l'heure actuelle, les processeurs x86 possèdent une telle instruction, dans leurs extension SSE 4.1. Même chose pour les architectures ARM et Power PC. Ce calcul, s'il n'est pas effectué par le matériel, est pris en charge par un bout de code souvent rudimentaire. Si quelques compilateurs fournissent ainsi des opérateurs spécialisés pour faire ce calcul, le poids de Hamming n'est pas implémenté par la plupart des langages de programmation. Il faut dire que son utilisation essentiellement bas-niveau fait que la majorité des langages de haut-niveau actuel n'en a pas l'utilité.

Méthode itérative

Pour faire ce calcul, on pourrait penser naïvement à utiliser une simple boucle pour additionner les bits un par un. Le nombre d'itération est alors égal au nombre de bits du nombre, peu importe le nombre de 1. Le code, écrit en C, devrait être le suivant, pour un entier 32 bits :

unsigned HammingWeight (unsigned x)
{
    unsigned HammingWeight = 0 ;
    while (x > 0)
    {
        HammingWeight += x & 1 ;
        x = x >> 1 ;
    }
    return HammingWeight ;
}

Une autre version, un peu plus rapide, se base sur une boucle similaire. Elle consiste à mettre à 0 le 1 de poids faible (celui le plus à droite) à chaque tour de boucle. Pour cela, il suffit d'appliquer l'expression $x.(x-1)$, dont on expliquera le fonctionnement dans quelques chapitres. En faisant cela, à chaque itération, le poids de Hamming diminue donc de 1. Il suffit de compter le nombre d'itération avant d'arriver à 0 pour déterminer le poids de Hamming. Le nombre d'itération est alors plus faible qu'avec le code précédent : le nombre d'itération passe du nombre de bits total au nombre de bits à 1. Le nombre d’itérations dans le pire des cas est alors le même qu'avec le code précédent, mais le nombre moyen ou dans le meilleur des cas diminue fortement. Le code obtenu est alors le suivant :

unsigned HammingWeight (unsigned x)
{
    unsigned HammingWeight = 0 ;
    while (x > 0)
    {
        x = x & (x - 1) ;
        HammingWeight += 1 ;
    }
    return HammingWeight ;
}

Méthode par pré-calcul

On peut aussi faire le calcul octet par octet. Pour cela, il suffit d'utiliser un tableau où la case d'indice i contient le poids de Hamming de i. Il suffit ensuite d'utiliser ce tableau dans une boucle pour faire l'addition octet par octet. On peut même dérouler totalement la boucle, si l'on connait exactement le nombre d'octets de l'entier à traiter. Cette technique a cependant le défaut d'effectuer des accès à la mémoire, qui sont des opérations assez lentes.

unsigned HammingWeight (unsigned x)
{ 
    static char table[256] = { 0, 1, 1, 2, 1, 2, 2, ... , 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 } ; // Tableau qui contient les poids de Hamming de chaque octet

    FirstByte = x & 0xFF ;
    SecondByte = (x >> 8) & 0xFF ;
    ThirdByte = (x >> 16) & 0xFF
    ForthByte = (x >> 24) & 0xFF

    return table[FirstByte] + table[SecondByte] + table[ThirdByte] + table[ForthByte] ;
}

Méthode récursive (diviser pour régner)

Calcul récursif du poids de Hamming.

Une autre solution effectue ce calcul avec une fonction récursive, avec une approche par dichotomie. En découpant un nombre en deux morceaux, on sait que son poids de Hamming est égal à la somme des poids de Hamming des deux morceaux. Et le même raisonnement s'applique sur chaque morceau. Au final, les morceaux sont de plus en plus petits, jusqu'à obtenir des morceaux de 1 bit. Dans ce cas, je sais que la population count d'un morceau de 1 bit vaut 1 si le bit est à 1, et zéro s'il vaut zéro. En clair : la population count de 1 bit vaut… le bit en question. Cela signifie qu'il suffit d'additionner tous les bits du nombre pour obtenir le nombre de uns. Dans les deux cas, le code devrait donc faire le calcul en N cycles, N étant le nombre de bits du nombre. Mais il y a moyen de faire beaucoup plus rapide, avec un calcul en log(N) opérations ! Pour cela, il faut utiliser une méthode qui s'inspire de la méthode récursive, mais utilise des opérations bit à bit pour faire certains calculs en parallèle. La méthode en question est, à mon avis, le plus beau algorithme utilisant des opérations bit à bit au monde.

L’algorithme

Pour illustrer l'algorithme, nous allons prendre l'exemple d'un nombre sur 8 bits que nous noterons N. L'algorithme commence par grouper les bits du nombre par groupes de deux et les additionne dans deux variables. La première variable va stocker tous les bits à une position paire, les autres bits étant mis à zéro (...0x0x0x0x0x). L'autre variable va faire la même chose avec les bits en position impaire, mais décalé d'un rang vers la droite, histoire que les bits des deux variables soient sur la même colonne (...0x0x0x0x0x également). Les deux variables sont alors additionnées : variable 1 + variable2 >> 1.

La première étape effectue donc le calcul suivant :

• variable1 = N . 01010101
• variable2 = (N . 10101010) >> 1
• variable 1 + variable 2.

Au niveau de chaque paire de bits (00 ou 01) l'addition de la paire en position paire avec celle en position impaire donne le nombre de bits à 1 sans report de retenue au delà de la paire de bits.

Regardons en détail ce qui se passe sur les bits de N.

Variable	groupe de deux bits	groupe de deux bits	groupe de deux bits	groupe de deux bits
Nombre N	a7 a6	a5 a4	a3 a2	a1 a0
Variable1 0 a6 0 a4 0 a2 0 a0	0 a6	0 a4	0 a2	0 a0
Variable 2 >> 1	0 a7	0 a5	0 a3	0 a1
Variable 1 + Variable 2 >> 1	(a7 + a6)	(a5 + a4)	(a3 + a2)	(a1 + a0)

La seconde étape est similaire, si ce n'est qu'elle isole les groupes de deux bits créés à l'étape précédente deux à deux, et les additionne.

Variable	groupe de quatre bits	groupe de quatre bits
Opérande	(a7 + a6) (a5 + a4)	(a3 + a2) (a1 + a0)
Variable1	(a7 + a6) 00	(a3 + a2) 00
Variable 2 >> 2	00 (a5 + a4)	00 (a1 + a0)
Variable 1 + Variable 2 >> 2	(a7 + a6 + a5 + a4)	(a3 + a2 + a1 + a0)

Et on, poursuit ainsi de suite, jusqu'à obtenir la population count de notre nombre. Dans notre exemple, une troisième étape suffit pour obtenir le résultat.

Variable	groupe de huit bits
Opérande	(a7 + a6 + a5 + a4) (a3 + a2 + a1 + a0)
Variable1	0000 (a7 + a6 + a5 + a4)
Variable 2 >> 4	0000 (a3 + a2 + a1 + a0)
Variable 1 + Variable 2 >> 4	(a7 + a6 + a5 + a4 + a3 + a2 + a1 + a0)

Détermination des masques

L'algorithme commence par calculer des variables avec des groupes de bits en position paire et impaire, le reste des bits étant mis à 0. Il est évident que cela demande d'utiliser des masques pour mettre les bits inutiles à zéro. Dans le cas de la seconde variable, les bits doivent être décalés histoire d'être mis sur la même colonne que l'autre variable. On peut penser qu'il est naturel d'appliquer les masques avant des décalages, ce qui donne : variable1 = N . 01010101 et variable2 = N . 10101010. Dans ce cas, le calcul de variable2 et de variable1 ne s'effectuent pas avec les mêmes constantes. Ceci dit, il est aussi possible de faire le décalage de la seconde variable avant d'appliquer le masque. Dans ce cas, les masques des deux variables deviennent identiques. Pour le montrer, partons des calculs où le masque est appliqué avant le décalage :

• variable2 = (N . 10101010) >> 1
• variable2 = (N . 11001100) >> 2
• variable2 = (N . 11110000) >> 4

Vu que les décalages sont distributifs par rapport au AND, (a . b) >> n = (a >> n) . (b >> n), on obtient :

• variable2 = (N >> 1) . (10101010 >>1) = (N >> 1) . 01010101
• variable2 = (N >> 2) . (11001100 >>2) = (N >> 2) . 00110011
• variable2 = (N >> 3) . (11110000 >>4) = (N >> 3) . 00001111

Les constantes utilisées sont exactement les mêmes que celles utilisée dans le calcul de la première variable.

Cela a un avantage sur certaines architectures RISC où les constantes immédiates ont une taille limitée. En conséquence, si une constante dépasse cette taille, elle ne peut pas utiliser le mode d'adressage immédiat. À la place, la constante est placée dans la mémoire, et est chargée dans un registre à chaque utilisation. Le fait de réutiliser la même constante pour le calcul de variable1 et de variable2 permet ainsi de charger cette constante une seule fois, et la réutiliser depuis le registre lors du calcul de variable2. En utilisant deux constantes différentes, on aurait deux accès mémoire, ce qui aurait été bien plus lent.

Le code en C

Fort de ce qui a été dit précédemment, on trouve que le code de calcul du poids de Hamming est le suivant pour un entier de 32 bits :

unsigned HammingWeight (unsigned x)
{
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
    x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);

    return x ;
}

Il est possible de simplifier encore plus ce code, en supprimant quelques ET.

unsigned HammingWeight (unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

Bit de parité

Les données d'un ordinateur ne sont pas des plus sûres qui soit. Évidemment, ces données peuvent être corrompues par un tiers malveillant, contenir des virus, etc. Mais certaines données sont corrompues pour des raisons qui ne relèvent pas de la volonté de nuire. Par exemple, les transmissions de données via un réseau local ou internet peuvent subir des perturbations électromagnétiques entre leur envoi et leur réception. Évidemment, les câbles réseaux sont conçus pour limiter les erreurs, mais ils ne sont pas une protection magique, capable de supprimer les erreurs de transmission. Dans le même genre, les mémoires ne sont pas des dispositifs parfaits, capables de fonctionner sans erreur. Pour donner un exemple, on peut citer l'incident de Schaerbeek. Le 18 mai 2003, dans la petite ville belge de Schaerbeek, une défaillance temporaire d'une mémoire faussa les résultats d'une élection. Cette ville utilisait une machine à voter électronique, qui contenait donc forcément une mémoire. Et on constata un écart de 4096 voix en faveur d'un candidat entre le dépouillement traditionnel et le dépouillement électronique. Mais ce n'était pas une fraude : le coupable était un rayon cosmique, qui avait modifié l'état d'un bit de la mémoire de la machine à voter. Cet incident n'était pas trop grave : après tout, il a pu corriger l'erreur. Mais imaginez la même défaillance dans un système de pilotage en haute altitude... Mais qu'on se rassure : il existe des techniques pour détecter et corriger les erreurs de transmission, ou les modifications non-prévues de données. Pour cela, divers codes de détection et de correction d'erreur ont vu le jour. Ce chapitre vous parlera du code le plus simple qui soit : le bit de parité/imparité, et de ses variantes.

Bit de parité horizontal mono-dimensionnel

Le bit de parité est une technique utilisée dans un grand nombre de circuits électroniques, comme certaines mémoires RAM, ou certains bus (RS232, notamment). Il permet de détecter des corruptions qui touchent un nombre impair de bits. Si un nombre pair de bit est modifié, il sera impossible de détecter l'erreur avec un bit de parité. Il faut noter que ce bit de parité, utilisé seul, ne permet pas de localiser le bit corrompu. Ce bit de parité est ajouté aux bits à stocker. Avec ce bit de parité, le nombre stocké (bit de parité inclus) contient toujours un nombre pair de bits à 1. Ainsi, le bit de parité vaut 0 si le nombre contient déjà un nombre pair de 1, et 1 si le nombre de 1 est impair. Si un bit s'inverse, quelle qu'en soit la raison, la parité du nombre total de 1 est modifié : ce nombre deviendra impair si un bit est modifié. Et ce qui est valable avec un bit l'est aussi pour 3, 5, 7, et pour tout nombre impair de bits modifiés. Mais tout change si un nombre pair de bit est modifié : la parité ne changera pas. Ainsi, on peut vérifier si un bit (ou un nombre impair) a été modifié : il suffit de vérifier si le nombre de 1 est impair. Le bit d'imparité est similaire a bit de parité, si ce n'est que le nombre total de bits doit être impair, et non pair comme avec un bit de parité. Sa valeur est l'inverse du bit de parité du nombre : quand le premier vaut 1, le second vaut 0, et réciproquement. Mais celui-ci n'est pas meilleur que le bit de parité : on retrouve l'impossibilité de détecter une erreur qui corrompt un nombre pair de bits.

Reste que ce bit de parité doit être calculé, avec un morceau de code dédié qui prend un nombre et renvoie le bit de parité.

Poids de Hamming et bit de parité

Par définition, le bit de parité n'est autre que la parité du poids de Hamming. Par définition, le bit de parité a pour but de faire en sorte que la population count d'une donnée soit toujours pair : la donnée à laquelle on ajoute le bit de parité sera pair, et aura toujours son bit de poids faible à zéro. En conséquence, le bit de parité d'un nombre est égal au bit de poids faible de la population count d'un nombre. Et cette propriété permet de donner des algorithmes de calcul du bit de parité d'un nombre assez efficace. Son calcul demande donc simplement de calculer le poids de Hamming et de déterminer s'il est pair ou non. Vu que le calcul du poids de Hamming a une complexité logarithmique en le nombre de bits de la donnée d'entrée, le code qui va suivre sera aussi dans ce cas. Cet algorithme est parfois utilisé sur des systèmes qui ont peu de mémoire, quand on a déjà programmé une fonction pour le poids de Hamming : cela permet d'économiser un peu de mémoire programme. Mais cet algorithme n'est pas le plus efficace en terme de temps de calcul.

unsigned population_count (unsigned word) ;

unsigned parity_bit (unsigned word)
{
    return population_count (word) & 1 ;
}

Il est cependant possible d'obtenir un code plus simple, qui est plus rapide. Pour cela, il suffit de spécialiser le code pour le poids de Hamming, de manière à ce qu'il calcule uniquement le bit de parité. En conséquence, la suite de cette partie se contentera de reprendre les algorithmes pour calculer le code de Hamming et de les adapter pour le bit de parité.

Algorithme itératif

Nous allons commencer par adapter le code itératif du calcul du poids de Hamming. Pour faire simple, la structure générale du code est conservée, mais il nous faudra remplacer les additions par une autre opération. Pour savoir quelle est cette opération, nous allons voir un cas simple : le calcul de la parité d'un nombre de 2 bits. Le circuit étant simple, il suffit d'utiliser les techniques vues précédemment, avec la table de vérité. En écrivant la table de vérité du calcul, on remarque rapidement que la table de vérité est celle d'une porte XOR.

Bit 1	Bit 2	Bit de parité
0	0	0
0	1	1
1	0	1
1	1	0

Pour la suite, nous allons rajouter un troisième bit au nombre de 2 bits précédent. L'ajout de ce troisième bit modifie naturellement le bit de parité du nombre précédent. Dans ce qui va suivre, nous allons voir comment calculer le bit de parité final, à partir : du bit de parité du nombre de 2 bits, et du bit ajouté. On voit alors que la table de vérité est celle d'une porte XOR.

Bit de parité précédent	Bit ajouté	Bit de parité final
0	0	0
0	1	1
1	0	1
1	1	0

Chose assez intéressante, ce mécanisme fonctionne quel que soit le nombre de bits du nombre auquel on ajoute un bit. Ajouter un bit à un nombre modifie sa parité, celle-ci état alors égale à : bit ajouté XOR bit-parité du nombre. L’explication est relativement simple : ajouter n 0 ne modifie pas le nombre de 1, et donc le bit de parité, tandis qu'ajouter un 1 inverse le bit de parité. Ainsi, on déduit que le bit de parité peut se calculer simplement : il suffit de faire un XOR entre tous les bits du nombre. Effectué naïvement, il suffit d'enchainer des portes XOR les unes à la suite des autres. Mais en réfléchissant, on peut faire autrement. Prenons deux nombres et concaténons-les. On peut déduire facilement le bit de parité de la concaténation à partir des bits de parité de chaque nombre : il suffit de faire un XOR entre ces deux bits de parité.

Il suffit donc de faire un XOR de tous les bits pour calculer le bit de parité d'un nombre. L’algorithme de calcul du nombre de parité est alors assez évident.

unsigned parity_bit (unsigned word ,unsigned size)
{    
    unsigned parity_bit = 0 ;

    // on itère sur chaque bit du mot à traiter
    for(unsigned index = 0 ; index < size ; ++index)
    {
        //sélection du bit de poids faible
        unsigned temp = word & 1
        word = word >> 1 ;

        // XOR entre le bit sélectionné et le bit de parité des bits précédents.
        parity_bit = parity_bit ^ temp ;
    }

    return parity_bit ;
}

Cette solution a un temps de calcul qui est linéaire en le nombre de bits de la donnée dont on veut calculer le bit de parité. On peut faire mieux en utilisant d'autres propriétés du bit de parité. Naturellement, on peut travailler non sur des bits, mais aussi sur des octets. Prenons un mot de 16 bits, par exemple : il me suffit de faire un XOR entre les bits de parité de ces deux octets. Or, la parité d'un octet peut se pré-calculer et être stockée dans un tableau une fois pour toute, afin d'éviter de nombreux calculs. Ainsi, l'algorithme vu précédemment peut être amélioré pour traiter non pas un bit à la fois, mais plusieurs bits à la fois.

unsigned ParityBit (unsigned x)
{ 
    static char table[256] = { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ... , 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,} ; // Tableau qui contient les bits de parité de chaque octet

    FirstByte = x & 0xFF ;
    SecondByte = (x >> 8) & 0xFF ;
    ThirdByte = (x >> 16) & 0xFF
    ForthByte = (x >> 24) & 0xFF

    return table[FirstByte] ^ table[SecondByte] ^ table[ThirdByte] ^ table[ForthByte] ;
}

Algorithme récursif

On peut améliorer l'algorithme du dessus en utilisant la propriété suivante : si on concatène deux mots binaire, alors le bit de parité du mot obtenu est égal au XOR des bits de parité des deux mots concaténés. Cette propriété peut s'expliquer assez simplement. Pour cela, il suffit de regarder le nombre de bits à 1 dans chaque mot à concaténer.

Nombre de bits à 1 dans le mot binaire de gauche	Nombre de bits à 1 dans le mot binaire de droite	Nombre de bits à 1 dans le résultat
Pair	Pair	Pair
Pair	Impair	Impair
Impair	Pair	Impair
Impair	Impair	Pair

Si on remplace Pair et Impair par la valeur du bit de parité correspondant, on obtient exactement le fonctionnement d'une porte XOR.

On peut aussi inventer un autre algorithme du calcul du bit de parité, assez inefficace, basé sur une fonction récursive. Le principe est de couper le mot dont on veut la parité en deux morceaux. On calcule alors la parité de ces deux morceau, et on fait un XOR entre ces deux parités. Le code obtenu est alors celui-ci :

unsigned parity (unsigned word, size)
{
    if (word <= 1)
    {
        return word ;
    }
    else
    {
        unsigned gauche = word >> (size/2) ;
        unsigned droite = word % (size/2) ;
        return parity(gauche, size/2) ^ parity (droite, size/2)) ;
    }
}

Algorithme optimisé

Il est aussi possible de réutiliser l'algorithme de calcul du poids de Hamming, celui récursif basé sur des masques et des additions, pour calculer le bit de parité. La différence est que les bits ne doivent pas être additionnés, mais XORés. Fort de ce qui a été dit précédemment, on trouve que le code de calcul du bit de parité est le suivant pour un entier de 32 bits :

unsigned ParityBit (unsigned x)
{
    x = (x & 0x55555555) ^ ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) ^ ((x >> 2) & 0x33333333);
    x = (x & 0x0F0F0F0F) ^ ((x >> 4) & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) ^ ((x >> 8) & 0x00FF00FF);
    x = (x & 0x0000FFFF) ^ ((x >> 16) & 0x0000FFFF);

    return x ;
}

Il faut noter que cet algorithme est cependant simplifiable pour le calcul du bit de parité. L'usage des masques permet de XOR les bits de position paire et impaire, puis des groupes consécutifs de 2 bits, puis de 4 bits, etc. Mais pour le bit de parité, on peut effectuer le calcul dans l'autre sens. Pour des entiers de 64 bits, on peut commencer par XOR les 32 bits de poids fort avec les 32 bits de poids faible. Plus, sur les 32 bits du résultat, on peut XOR les 16 bits de poids fort et les 16 de poids faible. Et ainsi de suite... L'algorithme est donc plus simple, vu que l'on a pas besoin d'utiliser des masques, mais que l'on peut se contenter de décalages. Le code est donc le suivant :

unsigned ParityBit (unsigned x)
{
    x ^= (x >> 32) ;
    x ^= (x >> 16) ;
    x ^= (x >> 8) ;   
    x ^= (x >> 4) ;
    x ^= (x >> 2) ;
    x ^= (x >> 1) ;

    return x & 1 ;
}

Mot de parité

Si on peut calculer le bit de parité d'un mot, il est aussi possible de calculer des octets de parité pour un ensemble de Byte/mots machine. Le résultat de cette opération est ce qu'on appelle un mot de parité, une extension du bit de parité pour plusieurs nombres. On peut le voir comme l'équivalent d'un bit de parité pour un paquet de nombre. Cela sert sur les bus de communication entre composants, sur lesquels on peut envoyer plusieurs nombres à la suite, ou dans les mémoires qui stockent plusieurs nombres les uns à côté des autres. Il faut noter que le bit de parité peut être vu comme une spécialisation de la technique du mot de parité, où les blocs font tous 1 bit. Le calcul du mot de parité se calcule en disposant chaque nombre/bloc l'un au-dessus des autres, le tout donnant un tableau dont les lignes sont des nombres Le mot de parité se calcul en calculant le bit de parité de chaque colonne du tableau, et en le plaçant en bas de la colonne. Le résultat obtenu sur la dernière ligne est un octet de parité. Pour comprendre le principe, supposons que nous disposions de 8 entiers de 8 bits. Voici comment effectuer le calcul du mot de parité :

• 11000010 : nombre ;
• 10001000 : nombre ;
• 01001010 : nombre ;
• 10010000 : nombre ;
• 10001001 : nombre ;
• 10010001 : nombre ;
• 01000001 : nombre ;
• 01100101 : nombre ;
• ------------------------------------
• 10101100 : mot de parité.

L'avantage de cette technique est qu'elle permet de reconstituer un octet manquant. C'est cette technique qui est utilisée sur les disques durs montés en RAID 3, 5 6, et autres : si un disque dur ne fonctionne plus, on peut quand même reconstituer les données du disque dur manquant. Retrouver la donnée manquante est assez simple : il suffit de calculer la parité des nombres restants et de faire un XOR avec le mot de parité. Pour comprendre pourquoi cela fonctionne, il faut se souvenir que faire un XOR entre un nombre et lui-même donne 0. De plus, le mot de parité est égal au XOR de tous les nombres. Si on XOR un nombre avec le mot de parité, cela va annuler la présence de ce nombre (son XOR) dans le mot de parité : le résultat correspondra au mot de parité des nombres, nombre xoré exclu. Ce faisant, en faisant un XOR avec tous les nombres connus, ceux-ci disparaitrons du mot de parité, ne laissant que le nombre manquant.

Bit de parité multidimensionnel

On a vu que le bit de parité ne permet pas de savoir quel bit d'un nombre a été modifié. Mais il existe une solution pour que cela devienne possible, dans le cas où plusieurs nombres sont envoyés. Si on suppose qu'un seul bit a été modifié lors de la transmission du paquet de nombre, on peut détecter quel bit exact a été modifié. Pour cela, il suffit de coupler un mot de parité avec plusieurs bits de parité, un par nombre. Détecter l bit modifié est simple. Pour comprendre comment, il faut se souvenir que les nombres sont organisés en tableau, avec un nombre par ligne. Le bit modifié est situé à l'intersection d'une ligne et d'une colonne. Sa modification entraînera la modification du bit de parité de la ligne et de la colonne qui correspondent, respectivement un bit de parité sur la verticale, et un bit de parité dans le mot de parité. Les deux bits fautifs indiquent alors respectivement la ligne et la colonne fautive, le bit erroné est situé à l'intersection. Cette technique peut s'adapter non pas avec une disposition en lignes et colonnes, mais aussi avec des dimensions en plus où les nombres sont disposés en cube, en hyper-cube, etc.

Manipulations sur les bits de poids faible/fort

Dans cette section, nous allons voir comment effectuer certaines opérations qui manipulent certains bits de poids fort ou certains bits de poids faible. Mais avant de commencer, un petit point sur la terminologie de ce chapitre. Nous aurons à utiliser des expressions du type "le 1 de poids faible", "les 0 de poids faible" et quelques autres du même genre. Quand nous parlerons du 0 de poids faible, nous voudrons parler du premier 0 que l'on croise dans un nombre en partant de sa droite. Par exemple, dans le nombre 0011 1011, le 0 de poids faible est le troisième bit en partant de la droite. Quand nous parlerons du 1 de poids faible, c'est la même chose, mais pour le premier bit à 1. Par exemple, dans le nombre 0110 1000, le 1 de poids faible est le quatrième bit. Quant aux expressions "le 1 de poids fort" et "les 0 de poids fort" elles sont identiques aux précédentes, sauf qu'on parcourt le nombre à partir de sa gauche.

Par contre, les expressions "les 1 de poids faible" ou "les 0 de poids faible" ne parlent pas de la même chose. Quand nous voudrons parler des 1 de poids faible, au pluriel, nous voulons dire : tous les bits situés avant le 0 de poids faible. Par exemple, prenons le nombre 0011 0011 : les 1 de poids faible correspondent ici aux deux premiers bits en partant de la gauche. Même chose quand on parle des zéros de poids faible au pluriel. Quant aux expressions "les 1 de poids fort" ou "les 0 de poids fort" elles sont identiques aux précédentes, sauf qu'on parcourt le nombre à partir de sa gauche.

Avant de poursuivre, rappelons quelques trivias.

• La valeur maximale codable sur n bits, $2^{n}-1$, est encodée par un nombre dont tous les bits sont à 1.
• Les nombres de la forme 000...000 1111 1111, à savoir des nombres dont les x bits de poids faible sont à 1 et tous les autres valent 0, valent $2^{x}-1$.
• Les nombres de la forme 11111...0000 (où on a une suite consécutive de 1 dans les bits de poids fort et les x bits de poids faibles à 1) valent : $2^{n}-2^{x}=2^{n-x}$.

Valeurs particulières en binaire

Le schéma ci-dessus montre que l'on peut obtenir le troisième nombre en soustrayant les deux précédents. Ce qui permet de rapidement démontrer le troisième trivia.

Manipuler les bits de poids fort/faible avec un masque

Il y a quelques chapitres, nous avons vu que les masques permettent de remplacer certains bits d'un nombre soit par des 0, soit par des 1. Dans ce qui va suivre, nous allons voir ce qui se passe quand on fait cela soit pour les bits de poids fort, soit pour ceux de poids faible. Par bits de poids fort/faible, nous ne voulons pas parler d'un bit précis, mais des $n$ bits de poids faible/fort, le nombre $n$ pouvant être choisit arbitrairement. En tout, cela fait quatre possibilités :

• remplacer les bits de poids faible par des zéros ;
• remplacer les bits de poids faible par des 1;
• remplacer les bits de poids fort par des zéros;
• remplacer les bits de poids fort par des 1.

La dernière possibilité ne nous intéressera pas, parce qu'elle ne correspond pas à une opération utile. Par contre, les trois autres possibilités correspondent à des opérations utiles, surtout la troisième. Pour faire ces opérations, nous aurons besoin d'utiliser des masques pour sélectionner les $n$ bits de poids faible/fort. Pour cela, il faut utiliser un masque, comme nous l'avons vu dans les chapitres précédents. Le masque qui permet de sélectionner les $n$ bits de poids faible a ses $n$ bits de poids faible à 1 et les autres à zéro, ce qui fait qu'il est égal à $2^{n}-1$. Celui pour les sélectionner les bits de poids fort est l'inverse de ce masque. Par inverse du masque, on veut dire que les bits à 0 passent à 1 et réciproquement. Sous forme mathématique, cela donne :

• Pour mettre les n bits de poids faible à 1, l'opération à effectuer est un OU entre le masque et le nombre à masquer. Sous forme mathématique, cela donne :

$x+(2^{n}-1)$, le $+$ étant ici un OU logique.

• Pour sélectionner les n bits de poids faible et mettre les autres à zéro, l'opération est un ET entre le masque et le nombre.

$x.(2^{n}-1)$, le $.$ étant ici un ET logique.

• Pour mettre les n bits de poids faible à 0, il faut faire un ET avec l'inverse du masque.

$x.({\overline {2^{n}-1}})$

Sur les ordinateurs qui utilisent le complètement à deux pour coder les nombres signés, cette expression se simplifie en :

$x.(-2^{n})$

Masquage des n bits de poids faible

Les trois opérations donnent des résultats très différents, mais qui peuvent se comprendre assez facilement quand on connait les rudiments de la division. Et pour mieux comprendre, le mieux est de regarder ce qui se passe quand on effectue les opérations équivalentes en décimal. Les opérations équivalentes consistent à remplacer certains chiffres par des 0 ou par des 9. Par exemple, mettre à zéro les bits de poids faible revient en décimal à mettre à zéro les N derniers chiffres. Mettre à 1 les $n$ bits de poids faible revient en décimal à remplacer les n derniers chiffres par des 9. Et idem pour les bits de poids fort.

Manipuler les bits de poids fort : le calcul du modulo

Comme dit plus haut, les puissances de 10 ont en décimal le même rôle que les puissances de deux en binaire. Une division décimale par 10, 100, 1000, est en quelque sorte la même chose qu'une division binaire par 2, 4, 8. Or, la division décimale et le modulo décimal sont très simples avec les puissances de 10. Diviser par 10 demande juste d'éliminer le dernier chiffre, diviser par 100 demande d'éliminer les deux derniers chiffres, diviser par 1000 demande d'éliminer les trois derniers chiffres, etc. De manière générale, diviser par $10^{n}$ demande d'éliminer les $n$ derniers chiffres. Pour le modulo, c'est la même chose. Le reste d'une division par 10 demande de conserver le dernier chiffre, à savoir le chiffre qui serait effacé par la division par 10. De même, le modulo par 100 demande de conserver juste les deux derniers chiffres, le modulo par 1000 demande de conserver les trois derniers chiffres, le modulo par 10000 les quatre derniers chiffres, etc.

En binaire, c'est la même chose, sauf que les chiffres sont ici les bits. En clair, il faut éliminer les n derniers bits pour obtenir le quotient, les conserver pour trouver le modulo. Le résultat d'une division binaire par $2^{n}$ est composé des bits de poids forts, ceux au-delà du rang $n$. Le résultat du modulo par $2^{n}$, quant à lui, est composé des $n$ bits de poids faible. Le tout est illustré dans le schéma ci-dessous.

Modulo et quotient d'une division par une puissance de deux en binaire.

On retrouve le fait qu'une division par $2^{n}$ se calcule en faisant un décalage vers la droite de n rangs. Et à l'opposé, on comprend ce qui se passe quand on masque les bits de poids fort, en les remplaçant par des zéros : on calcule le modulo par $2^{n}$. Calculer le modulo par $2^{n}$ demande juste de garder les $n$ bits de poids faible. Pour comprendre pourquoi cela fonctionne, partons de l'écriture en binaire d'un nombre :

$2^{x}+2^{x-1}+2^{x-2}+...+2^{2}+2^{1}+2^{0}$

Par définition, le modulo d'un nombre prend le reste de la division par un entier, c’est-à-dire ce qu'il reste une fois qu'on a éliminé tous les multiples du quotient. Sachant que dans notre cas, le quotient est égal à $2^{n}$, cela veut dire qu'on doit supprimer tous les multiples de $2^{n}$ dans l'écriture binaire de notre nombre, en les mettant à zéro. Et cela revient en fait à ne conserver que les n bits les plus à droite dans l'écriture binaire de notre nombre.

Manipuler les bits de poids faible : des arrondis liés à des multiples de $2^{n}$

Maintenant, nous allons voir ce qui se passe quand on met les n bits de poids faible d'un nombre à 0 ou à 1. Ces bits correspondent au modulo par $2^{n}$, ce qui fait que nous les appellerons tout bonnement : le modulo, sous-entendu le modulo à $2^{n}$. Quand il sera fait mention de "mettre le modulo à 0", cela vaudra dire que tous les n bits de poids faible seront mis à 0. Et pour l'expression "mettre le modulo à sa valeur maximale", cela vaudra dire que tous les n bits de poids faible seront mis à 1.

Les deux opérations, à savoir mettre le modulo à zéro ou à 1, sont liés à des arrondis particuliers. Les arrondis en question arrondissent au multiple de $2^{n}$ immédiatement supérieur ou inférieur. Pour comprendre à quoi correspondent ces arrondis, prenons l'exemple du nombre 46, qu'on souhaite arrondir au multiple de 8 immédiatement supérieur/inférieur. Le fait est que 46 n'est pas un multiple de 8, mais est situé entre deux multiples de 8 : 48 (8*6) et 40 (8*5). Arrondir 46 au multiple de 8 immédiatement supérieur donne 46, alors qu'arrondir au multiple de $2^{n}$ immédiatement inférieur donne 40. La même logique peut s'appliquer pour les multiples de 4, 16, 32 et autres. Par exemple, reprenons le nombre 46 et arrondissons-le au multiple de 16 immédiatement supérieur/inférieur. Arrondir au multiple de 16 immédiatement inférieur donne 32 (16*2), alors qu'arrondir au multiple de 16 immédiatement supérieur 48 (16*3).

Dans ce qui va suivre, nous allons noter $N$ le nombre à arrondir. Le multiple de $2^{n}$ immédiatement inférieur sera noté $M_{inf}$, alors que le multiple immédiatement supérieur sera noté $M_{sup}$. On a alors :

$M_{inf}\leq N<M_{sup}$

Par définition, $M_{inf}$ et $M_{sup}$ sont des multiples de $2^{n}$, et qui plus est deux multiples consécutifs. On a donc :

$k\times 2^{n}\leq N<(k+1)\times 2^{n}$

Cette inégalité sera très importante pour comprendre comment calculer les arrondis en question.

Mettre les bits de poids faible à zéro

Pour commencer, regardons ce qui se passe quand on met les bits de poids faible à zéro et essayons de donner un sens au résultat. L'idéal est de comparer avec ce qui se passe avec l'opération équivalente en décimal. Celle-ci revient, dans un nombre décimal, à remplacer les N derniers chiffres par des zéros. Par exemple, mettre le dernier chiffre à 0 revient à arrondir à la dizaine la plus proche, mettre les deux derniers chiffres à 0 revient à arrondir à la centaine la plus proche, mettre les trois derniers chiffres à 0 revient à arrondir au millier le plus proche, etc. En clair : remplacer les N derniers chiffres par des 0 revient à arrondir au multiple de $10^{N}$ immédiatement inférieur. En binaire, c'est la même chose, mais avec les bits et des puissances de 2.

Pour comprendre le sens du résultat, il faut revenir sur la division euclidienne de N par $2^{n}$. Par définition de la division euclidienne, on a :

$N=q\times 2^{n}+r$, avec r le reste, qui est une constante inférieure à $2^{n}$.

Rappelons que les n bits de poids faible d'un nombre sont le modulo par $2^{n}$. Si l'on met le modulo par $2^{n}$ à zéro, cela revient à tout simplement soustraire le reste, le modulo proprement dit. On trouve :

$N-r=q\times 2^{n}$

Par définition, le terme de droite est le multiple de $2^{n}$ le plus proche de N, mais qui lui est immédiatement inférieur. Vous comprenez donc pourquoi je parle de ces arrondis particuliers juste après la section sur la division et le modulo par $2^{n}$ ! Tout cela pour dire que :

$M_{inf}=q\times 2^{n}$

$M_{sup}=(q+1)\times 2^{n}$

Mettre les bits de poids faible à 1

Maintenant, regardons ce qui se passe quand on met tous les bits du modulo non pas à zéro, mais à 1. En clair, le modulo est remplacé par la plus grande valeur qu'il peut prendre. Pour comprendre le sens du résultat de cette opération, repartons encore une fois de N écrit comme suit :

$N=q\times 2^{n}+r$

L'opération met le reste à sa valeur maximale, qui est composée de n bits tous à 1, qui est par définition égale à $2^{n}-1$. Le remplacement donne donc un nombre $R$ tel que :

$R=q\times 2^{n}+(2^{n}-1)$

Pour comprendre le résultat, rappelons que l'on a : $M_{inf}=q\times 2^{n}$. En faisant le remplacement, on a :

$R=M_{inf}+(2^{n}-1)$

En identifiant avec : $M_{sup}=(q+1)\times 2^{n}$, on trouve que le résultat est de :

$R=M_{sup}-1$

En clair, mettre tous les n bits de poids fort d'un nombre à 1 donne le nombre qui est juste avant le multiple de $2^{n}$ immédiatement supérieur. Dit autrement, calculer le multiple de $2^{n}$ immédiatement supérieur demande de mettre les n bits de poids faible à 1 et d'incrémenter.

Manipuler les bits de poids faible, grâce à un incrément

Dans la section précédente, nous avons vu ce qu'il se passe quand on masque un nombre avec un nombre de la forme $2^{n}-1$. Mais ce n'est pas la seule possibilité et d'autres masques peuvent être utilisés. Le cas le plus intéressant est d'utiliser un masque qui se calcule en incrémentant/décrémentant le nombre à masquer. Pour le dire plus clairement, nous allons étudier des calculs comme $x.(x-1)$, $x.(x+1)$, $x|(x-1)$, etc. Pour comprendre comment ces formules fonctionnent, il faut voir en quoi un nombre et son suivant différent en binaire. Et pour cela, on doit parler de comment incrémenter un nombre en binaire avec seulement des opérations bit à bit.

Pour comprendre comment cela fonctionne, commençons d'abord par faire un rappel sur l'addition en binaire. La table d'addition est très simple en binaire. Jugez plutôt :

• 0 + 0 = 0, retenue = 0 ;
• 0 + 1 = 1, retenue = 0 ;
• 1 + 0 = 1, retenue = 0 ;
• 1 + 1 = 0, retenue = 1.

Évidemment, la retenue se propage au bit suivant, exactement comme en décimal.

Incrémenter un nombre revient à lui ajouter le nombre 000 ... 001, à savoir un nombre dont seul le bit de poids faible est à 1. En clair, incrémenter un nombre consiste juste à incrémenter le bit de poids faible et à propager les retenues. Regardons ce qui se passe quand on incrémente le bit de poids faible. S'il vaut 0, il passe alors à 1 et il n'y a pas de retenue à propager. Mais s'il vaut 1, il passe à 0 et une retenue est propagée sur la colonne suivante. Et si une retenue est propagée, la même chose se reproduit à la colonne suivante, et ainsi de suite... Au final, on voit que la propagation de la retenue s'arrête au premier bit à 0 rencontré, mais se propage tant que les bits de poids faible sont à 1.

Pour clarifier les choses, prenons un nombre de la forme suivante : XXXX ... XXXX 0111 ... 1111. Dans ce cas, l'incrémentation fait passer ce nombre de XXXX ... XXXX 0111 ... 1111 à XXXX ... XXXX 1000 ... 0000. Le premier zéro rencontré passe à 1, et tous les bits précédents passent à 0.

Notons que cette logique marche aussi s'il n'y a pas de 1 de poids faible : le bit de poids faible passe alors juste de 0 à 1.

Le seul cas un peu trompeur est celui où il n'y a pas de bit à zéro, dont l'incrémentation donne un débordement d'"entier. Mais dans ce cas, la gestion traditionnelle des débordement fait que le résultat est tout bonnement zéro.

Nombre à incrémenter	Résultat de l'incrémentation
XXXX ... XXXX ... XXX0	XXXX ... XXXX ... XXX1
XXXX ... X011 ... 1111	XXXX ... X100 ... 0000
1111 ... 1111 ... 1111	0000 ... 0000 ... 0000

Concrètement, les bits qui changent après incrémentation sont le 0 de poids faible et les bits précédents (les trailing ones).

En sachant ceci, vous pouvez facilement déterminer ce que donne le résultat de calculs comme $x.(x+1)$, ${\overline {x}}|(x+1)$ ou encore $x|(x+1)$. Ces opérations vont donc modifier le 0 de poids faible et/ou les trailing ones.

Mettre à 0 les 1 de poids faible

Fort de ce qui vient d'être dit, regardons ce que fait l'opération suivante :

$x.(x+1)$

Reprenons le tableau précédent et regardons quel est le résultat de l’opération :

$x$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
$x+1$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
$x.(x+1)$	XXXX ... XXXX ... XXX0	XXXX ... X000 ... 000	0000 ... 0000 ... 0000

Si on analyse le résultat du tableau, on voit que la seule différence entre $x$ et $x+1$ est dans les bits de poids faible. Tous les bits de poids faible à 1, ceux situés avant le premier bit à 0, sont mis à 0.

Mettre à 1 le 0 de poids faible

Maintenant, regardons ce qui se passe si on remplace le ET par un OU.

$x|(x+1)$

Reprenons le tableau de l'incrémentation et regardons quel est le résultat de l’opération :

$x$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
$x+1$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
$x.(x+1)$	XXXX ... XXXX ... XXX1	XXXX ... X111 ... 1111	1111 ... 1111 ... 1111

On voit que cette opération permet de mettre à 1 le zéro de poids faible, à savoir le premier bit à 0 en partant des bits de poids faible.

Mettre à 0 les bits situés à gauche du 0 de poids faible

Maintenant, étudions le résultat de cette opération :

$x.\left({\overline {x+1}}\right)$

Ce calcul ressemble aux précédents, sauf que cette fois-ci, on a pris de NOT du résultat de l'incrémentation.

Reprenons le tableau des cas possibles. Précisons que pour un bit quelconque, noté X, son NOT sera noté Y.

$x$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
$x+1$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
${\overline {x+1}}$	YYYY ... YYYY ... YYY0	YYYY ... Y011 ... 1111	0000 ... 0000 ... 0001
$x.\left({\overline {x+1}}\right)$	0000 ... 0000 ... 0000	0000 ... 0011 ... 1111	0000 ... 0000 ... 0001

Le tableau montre que ce calcul isole les 1 de poids faible. En clair, tous les bits situés à gauche du 0 de poids faible sont mis à 0.

Isoler le 0 de poids faible

Maintenant, étudions le résultat de cette opération, qui n'est autre que l'opération précédente dans laquelle on a remplacé le ET par un OU :

$x|\left({\overline {x+1}}\right)$

Reprenons le tableau des cas possibles. Précisons que pour un bit quelconque, noté X, son NOT sera noté Y.

$x$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
${\overline {x+1}}$	YYYY ... YYYY ... YYY0	YYYY ... Y011 ... 1111	0000 ... 0000 ... 0001
$x.\left({\overline {x+1}}\right)$	1111 ... 1111 ... 1110	1111 ... 1011 ... 1111	1111 ... 1111 ... 1111

On voit que tous les bits sont mis à 1, sauf un : le zéro le plus à droite, le zéro de poids faible. On dit que ce calcul isole le 0 de poids faible.

Isoler le 0 de poids faible et l'inverser

Maintenant, regardons ce que fait l'opération suivante :

${\overline {x}}.(x+1)$

Reprenons le tableau précédent et regardons quel est le résultat de l’opération :

$x$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
$x+1$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
${\overline {x}}$	YYYY ... YYYY ... YYY1	YYYY ... Y100 ... 0000	0000 ... 0000 ... 0000
${\overline {x}}.(x+1)$	0000 ... 0000 ... 0001	0000 ... 0100 ... 000	0000 ... 0000 ... 0000

On voit que l'opération a pour un résultat un nombre dont le seul bit à 1 est situé à la position du zéro de poids faible de l'opérande.

Isoler les 1 de poids faible et inverser

Maintenant, regardons ce que fait l'opération suivante :

${\overline {x}}|(x+1)$

Reprenons le tableau précédent et regardons quel est le résultat de l’opération :

$x$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
$x+1$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
${\overline {x}}$	YYYY ... YYYY ... YYY1	YYYY ... Y100 ... 0000	0000 ... 0000 ... 0000
${\overline {x}}.(x+1)$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 000	0000 ... 0000 ... 0000

On voit que cette opération isole les 1 de poids faible ceux situés avant le zéro de poids faible, mais inverse le résultat.

Manipuler les bits de poids faible/fort, grâce à un décrément

Maintenant, étudions ce qui se passe quand on décrémente un nombre. Il se passe alors la même chose qu'avec l'incrémentation, si ce n'est qu'on doit remplacer la table d'addition par la table de soustraction. Il y a toujours une retenue à propager d'une colonne vers la suivante, en partant du bit de poids faible. Par contre, la retenue est soustraite.

La table de soustraction est la suivante :

• 0 - 0 = 0, retenue = 0 ;
• 0 - 1 = 1, retenue = 1 ;
• 1 - 0 = 1, retenue = 0 ;
• 1 - 1 = 0, retenue = 0.

Décrémenter un nombre revient à lui soustraire le nombre 000 ... 001, à savoir un nombre dont seul le bit de poids faible est à 1. En clair, on soustrait 1 au bit de poids faible et on propage les retenues s'il y en a. La propagation de la retenue ne s'arrête cependant pas au même moment que la retenue d'une incrémentation. La raison est que la table de soustraction et d'addition sont différentes et que les cas où une retenue se propage ne sont pas les mêmes. Avec la décrémentation, la propagation de la retenue s'arrête au premier bit à 1 rencontré. Les bits avant ce premier 1 sont inversés et passent de 0 à 1. Si on reprend le tableau des trois cas possibles, voici ce que cela donne.

Nombre à décrémenter	Résultat de la décrémentation
XXXX ... XXXX ... XXX1	XXXX ... XXXX ... XXX0
XXXX ... X100 ... 0000	XXXX ... X011 ... 1111
0000 ... 0000 ... 0000	1111 ... 1111 ... 1111

Les bits qui changent après décrémentation sont le 1 de poids faible et les 0 précédents.

En sachant ceci, vous pouvez facilement déterminer ce que donne le résultat de calculs comme $x.(x-1)$ ou encore $x|(x-1)$

Mettre à 0 le 1 de poids faible

Commençons par voir ce que donne ce calcul :

$x.(x-1)$

Le tableau des cas possibles donne ceci :

$x$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000... 0000... 0000
$x-1$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111... 1111... 1111
$x.(x-1)$	XXXX ... XXXX ... XXX0	XXXX ... X000 ... 0000	0000... 0000 ... 0000

On remarque que ce calcul ne change qu'un seul bit du nombre initial, pas un de plus, pas un de moins. Et ce bit, qui passe de 1 à 0, est le 1 le plus à droite dans l'écriture binaire, à savoir le 1 de poids faible.

$x$	$x.(x-1)$
1111 1111	1111 1110
1111 1110	1111 1100
1111 1000	1111 0000
0010 1000	0010 0000
0010 0000	0000 0000

Notons que ce calcul permet de vérifier si un nombre est une puissance de deux. Si ce calcul donne pour résultat zéro, alors le nombre $x$ est une puissance de deux. En effet, par définition, une puissance de deux n'a qu'un seul bit à 1. Si ce bit est mis à 0, alors on obtient bien un zéro.

Mettre à 1 le ou les 0 de poids faible

On peut maintenant se demander ce qui se passe quand on effectue non pas un ET, mais un OU, soit l'opération suivante :

$x|(x-1)$

Le tableau des cas possibles donne ceci :

$x$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000... 0000... 0000
$x-1$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111... 1111... 1111
$x.(x-1)$	XXXX ... XXXX ... XXX1	XXXX ... X111 ... 1111	1111... 1111... 1111

Dans ce cas, on remarque que les 0 de poids faibles sont mis à 1. Précisément, si on prend un nombre de la forme XXXXX...XXXX 100000...000, celui-ci devient de la forme XXXXX...XXXX 11111...1111. En clair, tous les bits qui se situe à droite du 1 de poids faible sont mis à 1. Par exemple, le nombre 0110 1010 0011 1000 deviendra 0110 1010 0011 1111.

Isoler le 1 de poids faible

A votre avis, que donne le résultat de cette opération :

$x.(-x)$

Cela semble n'avoir aucun rapport avec les opérations précédentes, mais rappelez-vous des règles du complément à deux. Celles-ci disent que $-x={\overline {x}}+1={\overline {x-1}}$. En clair, ce calcul est équivalent au suivant :

$x.\left({\overline {x-1}}\right)$

On prend le tableau des différentes possibilités :

$x$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
$x-1$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111 ... 1111 ... 1111
${\overline {x-1}}$	YYYY ... YYYY ... YYY1	YYYY ... Y100 ... 0000	0000 ... 0000 ... 0000
$x.\left({\overline {x-1}}\right)$	0000 ... 0000... 0001	0000 ... 0100 ... 0000	0000 ... 0000 ... 0000

On voit que cette opération isole le 1 de poids faible, c'est à dire que le 1 de poids faible est conservé, tandis que tous les autres bits sont mis à zéro.

Isoler les 0 de poids faible

Reprenons l'opération précédente et remplacons le ET par un OU :

$x|\left({\overline {x-1}}\right)$

On prend le tableau des différentes possibilités :

$x$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000 ... 0000 ... 0000
${\overline {x-1}}$	YYYY ... YYYY ... YYY1	YYYY ... Y100 ... 0000	0000 ... 0000 ... 0000
$x|\left({\overline {x-1}}\right)$	1111 ... 1111 ... 1111	1111 ... 1100 ... 0000	0000 ... 0000 ... 0000

On voit que cette opération isole les 0 de poids faible, c'est à dire les bits situés avant le 1 de poids faible. Tous les autres bits sont mis à 1.

Isoler les 0 de poids faible et inverser

Étudions maintenant ce calcul :

${\overline {x}}.(x-1)$ ;

Le tableau des cas possibles donne ceci :

$x$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000... 0000... 0000
${\overline {x}}$	YYYY ... YYYY ... YYY0	YYYY ... Y011 ... 1111	1111 ... 1111 ... 1111
$x-1$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111... 1111... 1111
$x.(x-1)$	0000... 0000... 0000	0000 ... 0011 ... 1111	1111... 1111... 1111

On voit que cette formule isole les 0 de poids faible, ceux situés avant le premier bit à 0, et inverse le tout. Par exemple, le nombre 0110 1100 1111 0000 deviendra : 0000 0000 0000 1111. Ou encore, le nombre 0101 1000 deviendra 0000 0111.

D'autres formules équivalentes peuvent être utilisées. Les voici :

• ${\overline {x+(-x)}}$ ;
• $(x.-x)-1$.

Isoler le 1 de poids faible et inverser

Étudions maintenant ce calcul :

${\overline {x}}|(x-1)$ ;

Le tableau des cas possibles donne ceci :

$x$	XXXX ... XXXX ... XXX1	XXXX ... X100 ... 0000	0000... 0000... 0000
${\overline {x}}$	YYYY ... YYYY ... YYY0	YYYY ... Y011 ... 1111	1111 ... 1111 ... 1111
$x-1$	XXXX ... XXXX ... XXX0	XXXX ... X011 ... 1111	1111... 1111... 1111
$x.(x-1)$	1111... 1111... 1110	1111 ... 1011 ... 1111	1111... 1111... 1111

On voit que cette formule isole le 1 de poids faible et inverse le tout. En clair, le résultat est un nombre dont tous les bits sont à 1, sauf à la position du 1 de poids faible dans l'opérande.

Manipuler le ou les bits de poids fort

Les opérations précédentes, basées sur un incrément ou un décrément, permettent d'isoler ou de manipuler les 0/1 de poids faible. Mais ils ne peuvent pas toucher aux 0/1 de poids fort. La raison est que la retenue se propage soit jusqu’au zéro de poids faible (incrémentation), soit jusqu'au 1 de poids faible (décrémentation). Manipuler le 1 ou le 0 de poids fort est plus compliqué. Dans ce qui va suivre, nous allons donner un code qui permet d'agir sur les bits qui précédent le 1 de poids fort.

Mettre à 1 les bits situés avant le 1 de poids fort

Pour commencer, nous allons voir comment mettre à 1 tous les bits situés avant le 1 de poids fort. Pour donner un exemple, cela permet de transformer 0010 1101 en 0011 1111. Ou encore, cela transforme 0001 0010 en 0001 1111. L'utilité de cette manipulation ne vous parait pas évidente, mais sachez que nous l'utiliserons dans la suite du chapitre.

Pour cela, partons de l’exemple d'un nombre, que l'on va nommer N. Dans ce qui va suivre, ce N vaudra 0010 1101, pour l'exemple. Comme vous le voyez, ce nombre est de la forme 001X XXXX, avec X qui vaut zéro ou 1 selon le bit. Le nombre de la forme $2^{n}-1$ immédiatement supérieur lui, vaut 0011 1111. On voit que pour obtenir ce nombre, il faut recopier le 1 le plus à gauche, dans tous les bits à sa droite. Pour cela, quelques décalages font l'affaire.

Pour vous donner une idée, regardons ce que vaut N OU (N >> 1) :

001X XXXX OR 0001 XXXX = 0011 XXXX

On voit que le 1 le plus à gauche a été recopié dans le bit à sa droite.

Ensuite, regardons ce que vaut N OU (N >> 1) OU (N >> 2) :

001X XXXX OR 0001 XXXX OR 0000 1XXX = 0011 1XXX

Vous commencez à comprendre ? Les bits qui sont à droite du 1 le plus à gauche se remplissent progressivement avec des 1, au fur et à mesure des décalages. Si on pousse le bouchon encore plus loin, on se retrouvera avec un nombre dont tous les bits à droite du 1 le plus à gauche seront tous des 1. Le résultat est un nombre de la forme $2^{n}-1$. Pour être plus précis, il s'agit du nombre de la forme $2^{n}-1$. Il n'y a plus qu'à l'incrémenter pour obtenir la puissance de deux immédiatement supérieure.

On doit donc effectuer suffisamment de décalages pour mettre à 1 tous les bits à droite. On peut croire que pour un nombre de n bits, il faut effectuer n décalages. Mais en réalité, on peut réduire ce nombre assez facilement. Prenons l'exemple du nombre de la forme 1XXX XXXX. On peut effectuer un premier décalage d'un rang vers la droite, ce qui donne : 11XX XXXX. Ensuite, on peut prendre les deux bits à 1 et les recopier dans les deux bits qui suivent. C'est plus rapide que de remplir les bits par un par un. Il faut alors faire un décalage de deux rangs, ce qui donne : 1111 XXXX. Enfin, on peut recopier les 4 bits à 1 dans les 4 bits suivants, ce qui demande un décalage par 4. Si le nombre était plus long, on pourrait réutiliser la même logique : à chaque étape, le nombre de rangs pour le décalage double. Et cela marche pour tous les nombres, peu importe leur écriture binaire. Le code correspondant, bien que spécifique aux nombres de 32 bits, est le suivant :

unsigned SetBitsAfterHighestOne(unsigned n)
{
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
}

Une interprétation mathématique de ce calcul est qu'il donne le nombre de la forme $2^{n}-1$ immédiatement supérieur. Par exemple, 5 donnera 7 (8-1), 25 donnera 31 (32-1), 250 donnera 255 (256-1), etc.

Le calcul de la puissance de deux immédiatement supérieure

Maintenant que l'on sait calculer le nombre de la forme $2^{n}-1$ immédiatement supérieur, on peut facilement deviner comment calculer la puissance de deux immédiatement supérieure à un nombre. Avec un tel calcul, 5 aurait pour résultat 8, 25 donnerait 32, 250 donnerait 256, etc. On pourrait croire qu'il suffirait de prendre le code précédent et d'y ajouter une incrémentation. Dans les faits, ce code ainsi modifié marcherait, mais échouerait dans le cas où le nombre considéré serait lui-même une puissance de deux. Pour éviter cela, il suffit d'ajouter une décrémentation en première instruction.

unsigned NextPowerOf2 (unsigned n)
{
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n++;
}

FFS, FFZ, CTO et CLO

Dans cette section, nous allons aborder plusieurs opérations fortement liées entre elles. Dans toutes ces opérations, les bits sont numérotés, leur numéro étant appelé leur position ou leur indice. La première opération, Find First Set, donne la position du 1 de poids faible. Cette opération est liée à l'opération Count Trailing Zeros, qui donne le nombre de zéros situés à droite de ce 1 de poids faible. L'opération Find First Set est opposée au calcul du Find highest set, qui donne la position du 1 de poids fort. Le nombre de zéros situés à gauche de ce bit à 1 est appelé le Count Leading Zeros.

Ces quatre opérations ont leurs équivalents en remplaçant les 0 par des 1 et réciproquement. Par exemple, l'opération Find First Zero donne la position du 0 de poids faible (le plus à droite) et l'opération Find Highest Zero donne la position du 0 de poids fort (le plus à gauche). L'opération Count Trailing Ones donnent le nombre de 1 à gauche du 0 de poids fort, tandis que l'opération Count Leading Ones donne le nombre de 1 situé à droite du 0 de poids faible. Ceux-ci se calculent à partir des quatre opérations précédentes, en inversant l'opérande, aussi nous n'en parlerons pas plus que cela.

Opérations Find First Set ; Find First Zero ; Find Highest Set (le logarithme binaire) ; Find Highest Zero ; Count Leading Zeros ; Count Trailing Zeros ; Count Leading Ones et Count Trailing Ones.

Ces opérations varient selon la méthode utilisée pour numéroter les bits. On peut commencer à compter les bits à partir de 0, le 0 étant le numéro du bit de poids faible. Mais on peut aussi compter à partir de 1, le bit de poids faible étant celui de numéro 1. Ces deux conventions ne sont pas équivalentes.

• Si on choisit la première convention, certaines opérations sont équivalentes. Par exemple, les opérations Count Trailing Zeros et Find First Set donnent toutes les deux le même résultat.
• Avec l'autre convention, les deux diffèrent de 1 systématiquement.

Dans ce qui va suivre, nous allons utiliser la première convention, ce qui fait que nous n'aurons qu'à aborder quatre calculs :

• le Find First Set, abréviée FFS ;
• le Find highest set, abrévié FHS ;
• le Find First Zero, abréviée FFZ ;
• le Find highest Zero, abrévié FHZ.

Avec cette convention, pour un nombre codé sur $n$ bits, on a :

$fhs+clz(n)=n-1$

$fhz+clo(n)=n-1$

$ffs=ctz(n)$

$ffz=cto(n)$

Find highest set : le logarithme binaire

Maintenant, nous allons voir comment déterminer la position du 1 le plus significatif dans l'écriture binaire du nombre. En clair, la position du 1 le plus à gauche. Mine de rien, ce calcul a une interprétation arithmétique : il s'agit du logarithme en base 2 d'un entier non-signé. Dans tout ce qui va suivre, nous allons numéroter les bits à partir de zéro : le bit le plus à droite d'un nombre (son bit de poids faible) sera le 0-ème bit, le suivant le 1er bit, et ainsi de suite.

Nous allons commencer par voir un cas simple : le cas où notre nombre vaut $2^{n}$. Dans ce cas, un seul bit est à 1 dans notre nombre : le n-ième bit. On peut en faire une démonstration par récurrence. Déjà, on remarque que la propriété est vraie pour $2^{0}$ : le 0-ème bit du nombre est mis à 1. Supposons maintenant que cette propriété soit vraie pour $n$ et regardons ce qui se passe pour $n+1$. Dans ce cas, $2^{n+1}=2\times 2^{n}=2^{n}<<1$. Donc, le bit suivant sera à un si on augmente l'exposant d'une unité : la propriété est respectée !

Maintenant, qu'en est-il pour n'importe quel nombre $x$, et pas seulement les puissances de deux ? Prenons n'importe quel nombre, écrit en binaire. Si celui-ci n'est pas une puissance de deux, alors il est compris entre deux puissances de deux : $2^{n}\leq x<2^{n+1}$. En prenant le logarithme de l'inégalité précédente, on a : $\log _{2}{2^{n}}\leq \log _{2}{x}<\log _{2}{2^{n+1}}$. Par définition du logarithme en base 2, on a : $n\leq \log _{2}{x}<n+1$. Dit autrement, le logarithme en base 2 d'un nombre est égal à $n$, qui est la position de son 1 de poids fort, celui le plus à droite. Plus précisément, il s'agit de la partie entière du logarithme.

Méthode itérative

Mais comment calculer cette position ? Pour cela, on peut utiliser le code suivant Celui-ci est composé d'une boucle qui décale le nombre d'un rang à chaque itération, et compte le nombre de décalage avant d'obtenir 0.

int log_2 (int a)
{
    unsigned int r = 0;
    while (a >>= 1)
    {
        r++;
    }
    return r ;
}

Méthode par dichotomie

Une autre méthode se base sur un algorithme par dichotomie, à savoir qu'il vérifie si le logarithme est compris dans un intervalle qui se réduit progressivement. Pour illustrer le principe de cet algorithme, nous allons prendre un entier de 64 bits. L'algorithme utilise un variable accumulateur pour mémoriser le logarithme, qui est calculé au fil de l'eau. L'algorithme vérifie d'abord si le bit de poids fort est compris dans les 32 bits de poids fort. Si c'est le cas, on sait que le logarithme est d'au moins 32 (> ou = à 32). La variable accumulatrice est alors incrémentée de 32 et le nombre est décalé de 32 rangs vers la droite. On poursuit alors l'algorithme, mais en vérifiant si le bit de poids fort est dans les 16 bits de poids fort. Et ainsi de suite avec les 8, 4, et 2 bits de poids fort. Pour vérifier si le bit de poids fort est dans les 32, 16, 8, 4, ou 2 bits de poids fort, une simple comparaison suffit. Il suffit de comparer si le nombre est supérieur respectivement à (1111 1111 1111 1111 1111 1111 1111 1111), (1111 1111 1111 1111), (1111 1111), (1111), (11). Le code est donc le suivant :

int log_2 (int x)
{
    unsigned log = 0 ;

    if (x > 0xFFFFFFFF)
    {
        log += 32 ;
        x = x >> 32 ;
    }
    if (x > 0xFFFF)
    {
        log += 16 ;
        x = x >> 16 ;
    }
    if (x > 0xFF)
    {
        log += 8 ;
        x = x >> 8 ;
    }
    if (x > 0xF)
    {
        log += 4 ;
        x = x >> 4 ;
    }
    if (x > 3)
    {
        log += 1 ;
        x = x >> 2 ;
    }
    log = x >> 1 ;

    return log ;
}

On peut généraliser cet exemple pour n'importe quel nombre de $n$ bits. L'algorithme commence par vérifier si le bit de poids fort est dans les $n \over 2$ bits de poids fort ou dans les $n$ bits de poids faible. Si le bit de poids fort est dans les $n$ bits de poids forts, alors on sait que le logarithme est d'au moins $n \over 2$ et peut lui être supérieur ou égal. On mémorise donc $n \over 2$ bits comme valeur temporaire du logarithme. On décale alors le nombre de $n \over 2$ bits vers la droite pour le ramener dans l'autre intervalle. Et on continue, mais en vérifiant les $n \over 4$ bits de poids fort, et ainsi de suite.

Méthode basée sur le poids de Hamming

Une autre solution se base sur le fait que le bit de poids faible est numéroté 0 ! Pour cela, on peut utiliser le code précédent, qui permet de trouver le nombre de la forme $2^{n}-1$ immédiatement supérieur. Ce nombre, par définition, a tous les bits de rang $\leq n$ à 1 : il suffit de calculer son poids de Hamming pour obtenir le rang $n$ !

int log_2 (int a)
{
    int n = SetBitsAfterHighestOne(a) ;
    return HammingWeight(n) ;
}

Count Leading Zeros

L'instruction Count leading zeros (clz) a pour objectif de compter les zéros situés avant le premier 1 de poids le plus fort. Ce nombre de leading zéros peut varier entre 0 et N (où N est le nombre total de bits représentant le nombre entier). S'il vaut zéro, le bit de plus à gauche est un 1. S'il vaut N, c'est que tous les bits du nombre sont à zéro. En matériel, cette opération est souvent utilisée dans certaines unités de calcul à virgule flottante, dans les opérations de normalisation et d'arrondis du résultat. Néanmoins, il faut préciser que seules les unités de calcul à faible performance ont besoin de déterminer le nombre de zéros les plus à gauche.

On peut calculer ce nombre de zéros à gauche (clz) simplement à partir de l'indice du 1 de poids fort, en utilisant l'équation :

$fhs(n)+clz(n)=N-1$

Il existe deux autres méthodes qui commencent toutes deux par mettre à 1 tous les bits situés à droite du 1 de poids fort. Une fois cela fait, il y a deux possibilités.

La première est d'effectuer un calcul de population count et de soustraire le résultat de $N$.

unsigned countLeadingZeros (unsigned n)
{
    a = SetBitsAfterHighestOne(n)

    return WORDBITS - population_count(a) ;
}

L'autre solution est d'inverser les bits et de calculer la population count. L'inversion des bits garantis que seuls les 0 de poids forts seront à 1, d'où le fait que la population count donne le bon résultat.

unsigned countLeadingZeros (unsigned n)
{
    a = SetBitsAfterHighestOne(n)

    return population_count( ~ a ) ;
}

Find First Set

Passons maintenant à l'opération Find First Set, qui donne la position du 1 de poids faible. On a vu plus haut que l'on peut isoler ce bit, avec le calcul $x.(-x)$. Une fois ce bit isolé, on peut trouver sa position avec l'opération Find Highest Set. On a donc :

unsigned ffs (unsigned n)
{
    return fhs( x & -x ) ;
}

Manipulations intra-mots

Dans cette section, nous allons voir des manipulations qui modifient ou travaillent à l'intérieur d'un mot/d'une variable/d'un registre. Nous allons voir comment échanger deux portions à l'intérieur d'un mot, comment inverser les bits d'un mot, détecter les octets nuls, et bien d'autres.

Inverser l'ordre des bits

Inverser l'ordre des bits d'un nombre est une opération qui est assez peu courante. Cependant, elle peut être très utile dans certains algorithmes, comme ceux qui impliquent des transformées de Fourier. Pour inverser les bits d'un nombre, il suffit d'inverser les bits en position paire et impaire, puis inverser les groupes de deux bits adjacents, puis des groupes de 4 bits, et ainsi de suite jusqu’à obtenir le bon résultat. Pour cela, on peut réutiliser les masques du calcul de la population count pour sélectionner les bits/groupes de bits, et de faire quelques décalages. Le code obtenu devrait être celui-ci pour des entiers de 32 bits :

unsigned BitReverse (unsigned x)
{
    x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1 ;
    x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2 ;
    x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4 ;
    x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8 ;
    x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16 ;

    return x ;
}

Les deux dernières lignes peuvent être remplacées par une seule ligne de code, qui fait l'échange entre quatre groupes de bits.

unsigned BitReverse (unsigned x)
{
    x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1 ;
    x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2 ;
    x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4 ;
    x = x << 24 | (x & FF00) << 8 | ( (x >> 8) & 0xFF00 ) | x >> 24 ;

    return x ;
}

Identification des octets nuls

Dans cette section, nous allons voir comment détecter les octets nuls dans un mot/registre (pour rappel, un mot est un groupe de plusieurs octets et/ou bytes qui a la taille d'un registre). Cet algorithme est très utilisé dans des langages comme le C, notamment dans leur bibliothèque standard, pour utiliser les chaînes de caractère. Les chaînes de caractères du C sont stockées sous la forme d'un tableau d'octets, chaque octet codant un caractère et la fin de la chaîne est indiquée par un octet nul. Au lieu de traiter la chaîne octet par octet, les bibliothèques standard préfèrent traiter la chaîne mot par mot, ce qui est plus rapide. Pour identifier correctement la fin de la chaîne, les algorithmes utilisés doivent donc déterminer si un octet est nul dans un mot. Mais cet algorithme peut avoir d'autres utilisations, que nous ne détaillerons pas ici. Par exemple, ce code peut servir à savoir si un mot contient un octet égal à x (et non à 0). Pour cela, il suffit de faire un XOR entre chaque octet et la valeur x. Si les deux octets sont égaux et seulement si c'est le cas, l'octet sera mis à 0. On peut ensuite utiliser le code qui détermine si un octet est nul.

Version avec branchements

Dans ce qui va suivre, chaque octet sera noté de 0 à n-1 pour un mot de n octets, avec 0 l'octet de poids faible et n-1 l'octet de poids fort. L'algorithme que nous allons voir renvoie un nombre qui indique la position du premier octet nul. La valeur renvoyée est égale à n si aucun octet n'est nul dans le mot. Pour les exemples qui vont suivre, nous allons prendre un mot de 64 bits, qui a donc 8 octets numérotés de 0 à 7. Cet algorithme va commencer par calculer un booléen/bit pour chaque octet, qui indique s'il est nul ou non : il vaut 0 s'il est nul et 1 sinon. Il va ensuite combiner ces booléens/bits pour déterminer la valeur de retour.

Le code utilisé dans ce chapitre suppose que l'ordre des octets est little endian où l'octet de poids faible du mot se situe en premier dans la séquence d'octet le représentant en mémoire. Pour l'ordre big endian, il suffit de changer l'ordre des noms de variables dans le code.

La version qui utilise des branchements va masquer chaque octet et tester si celui-ci est nul :

unsigned FindFirstZeroByte (unsigned word)
{
    unsigned b0 = (word & 0xFF) == 0 ;
    unsigned b1 = (word & 0xFF00) == 0 ;
    unsigned b2 = (word & 0xFF0000) == 0 ;
    unsigned b3 = (word & 0xFF000000) == 0 ;
    unsigned b4 = (word & 0xFF00000000) == 0 ;
    unsigned b5 = (word & 0xFF0000000000) == 0 ;
    unsigned b6 = (word & 0xFF000000000000) == 0 ;
    unsigned b7 = (word & 0xFF00000000000000) == 0 ;

    if (b0)
    {
        return 0 ;
    }
    else if (b1)
    {
        return 1 ;
    }
    else if (b2)
    {
        return 2 ;
    }
    else if (b3)
    {
        return 3 ;
    }
    else if (b4)
    {
        return 4 ;
    }
    else if (b5)
    {
        return 5 ;
    }
    else if (b6)
    {
        return 6 ;
    }
    else if (b7)
    {
        return 7 ;
    }
    else
    {
        return 8 ;
    }
}

Calcul en parallèle

Pour faire le calcul plus rapidement, il faut effectuer toutes les comparaisons en même temps, en utilisant des opérations bit à bit et des calculs arithmétiques. Le calcul que nous allons voir utilise ce principe. Il va placer les bits b0, b1, ..., b7, dans le bit de poids fort de chaque octet, comme le font les prédicats de comparaison. Ainsi, ce calcul va remplacer tous les octets nuls par 0xxx xxxx et tous les bytes non nuls par 1xxx xxx. Une solution qui marche pour les octets inférieurs à 1000 000 est d'additionner 0111 111 : en faisant cela, tous les octets nuls deviendront 0111 1111 alors que les octets non-nuls dépasseront 0111 1111. Ces derniers deviendront donc des octets de la forme 1xxx xxxx. Mais comme dit plus haut, cela ne fonctionne que pour les octets inférieurs à 1000 0000. Le problème avec ces octets est que le résultat déborde de l'octet, modifiant les résultats des autres octets. Pour faire l'addition correctement, il faut donc mettre à 0 le bit de poids fort de chaque octet pour éviter le débordement. Pour mettre le bit de poids fort à 0, il faut faire un masque avec 0x7F. Enfin, il faut additionner 0x7F (0111 1111). Le calcul effectué sur tous les octets en même temps est donc :

$x=(x.0x7F7F7F7F)+0x7F7F7F7F$

Pour prendre en compte les octets supérieurs à 1000 0000, il faut simplement faire un OU entre le résultat précédent et l'octet en question. Comme cela, si l'octet dépasse 1000 0000, le bit de poids fort du résultat sera mis à 1. Ce qui corrige le résultat précédent.

$x=((x.0x7F7F7F7F)+0x7F7F7F7F)|x$

Le code devient donc :

unsigned FindFirstZeroByte (unsigned x)
{
    unsigned word = x = ( (x & 0x7F7F7F7F) + 0x7F7F7F7F ) | x ;

    unsigned b0 = word >> 7 ;
    unsigned b1 = word >> 15 ;
    unsigned b2 = word >> 23 ;
    unsigned b3 = word >> 31 ;
    unsigned b4 = word >> 39 ;
    unsigned b5 = word >> 47 ;
    unsigned b6 = word >> 55 ;
    unsigned b7 = word >> 63 ;

    /* return b0 + (b0 & b1) + (b0 & b1 & b2) + (b0 & b1 & b2 & b3) ; */
    return b0 ? 0 : b1 ? 1 : b2 ? 2 : b3 ? 3 : b4 ? 4 : b5 ? 5 : b6 ? 6 : b7 ? 7 : 8;
}

Les prédicats de comparaison

Tous les langages de programmation gèrent les comparaisons et conditions, à l'exception de quelques langages très rares. Le résultat d'une comparaison est ce qu'on appelle un booléen, une variable qui ne peut prendre que les valeurs vrai et faux (True et False). Un bit suffit pour stocker cette valeur : en général 0 représente faux et 1 représente vrai.

Au niveau du processeur, ce résultat peut être mémorisé de plusieurs manières. Les processeurs x86 mémorisent le résultat de la comparaison dans un registre d"état, dont les bits ont une interprétation prédéfinie. Ces bits sont accédés par des instructions de branchement, ce qui permet de programmer des structures de contrôles, comme des IF, WHILE, et autres. Mais il arrive que le programmeurs souhaite utiliser des booléens et faire des opérations dessus sans forcément les utiliser dans une structure de contrôle. Il est alors possible de stocker un booléen dans une variable, certains langages ayant même un type booléen dédié.

Dans le langage Java, le type boolean permet d'utiliser les valeurs booléennes false et true.

Dans le langage C, il n'existe pas de type booléen, le résultat des comparaisons pouvant cependant mémorisé dans une variable entière. Le standard C ANSI stipule que cet entier code la valeur False par un 0 et la valeur True par la valeur 1. Des calculs du style x = (a < 15) * (b > 0) * d sont alors possibles. Cependant, le processeur peut ne pas gérer de telles opérations nativement. Autant les processeurs sans registre d'état (les MIPS, ARM et quelques CPU RISC) le peuvent grâce à la présence de certaines instructions, ce n'est pas le cas sur les processeurs x86 ou quelques autres jeux d'instructions avec un registre d'état. Les résultats de comparaison doivent alors être calculés sans recourir à des instructions de comparaison et être calculées à grand coup d'opérations bit à bit. Voyons comment faire.

Les formules que nous allons voir placent le prédicat (le résultat de la comparaison) dans un entier, et précisément dans son bit de signe. Un simple décalage peut être utilisé pour respecter la convention 0 = False et 1 = True. Dans le cas où on doit traiter plusieurs prédicats avec des opérations logiques on peut parfaitement imaginer combiner les bits de signe avec des opérations logiques et ne faire le décalage qu'au moment où l'on doit effectivement respecter la convention. La raison qui fait que le résultat se situe dans le bit de signe tient à la manière dont on peut effectuer une comparaison. Dans la plupart des unités de calcul, les comparaisons sont implémentées avec des soustractions : on soustrait les opérandes à comparer et on effectue quelques tests sur le résultat pour déterminer les prédicats. Par exemple, un débordement de la soustraction indique que la première opérande est plus petite que celle soustraite. La logique des formules qui vont suivre est plus ou moins la même : on soustrait les deux opérandes, et on fait quelques bidouilles sur les signes ou bits de débordement.

Dans ce qui va suivre, abs(à désigne la valeur absolue, nabs son opposé, et nlz désigne l'opération Count Leading Zero et les opérandes à comparer seront notées A et B.

Le prédicat d'égalité/inégalité

Le prédicat d'inégalité, qui indique si les deux nombres comparés sont inégaux, se calcule avec les formules suivantes. La première formule est assez simple à comprendre. Il faut juste remarquer que B - A et A - B sont opposés et ont donc des signes différents : leur OU donnera un bit de signe à 1 dans le résultat. Par contre, si les deux opérandes sont égaux, leur soustraction donnera 0 : le bit de signe vaudra 0 pour les deux soustractions et leur OU aussi. Ainsi, le résultat aura un bit de signe à 0 quand A = B, et à 1 sinon. La seconde formule est une reformulation de la seconde formule.

• $(B-A)|(A-B)$

• $nabs(A-B)$

Pour le prédicat d'égalité, il suffit de prendre l'opposé des formules précédentes. Cela donne les formules suivantes :

• ${\overline {(B-A)|(A-B)}}$

• $abs(A-B)-1$

Le prédicat d'infériorité/supériorité

Le prédicat d'infériorité et de supériorité sont deux faces d'une même pièce : il suffit de faire le calcul de l'un en inversant les opérandes pour calculer l'autre. Aussi, nous allons donc voir le prédicat d'infériorité A < B. Celui-ci existe en une version stricte : A < B, et une version non-stricte : $A\leq B$. Nous allons les voir dans cet ordre.

Le prédicat d'infériorité/supériorité stricte

Celui-ci se calcule, comme le prédicat d'égalité, en calculant A - B et en testant les signes du résultat. Mais les opérations à réaliser sur les signes sont assez complexes à comprendre dans le détail. Pour mieux les comprendre, nous allons voir quel est le signe de A - B selon les signes de A et B, et quel est le résultat de la comparaison. Quatre cas peuvent se présenter : on soustrait un nombre positif à un autre positif, on soustrait un négatif à un positif, on soustrait un positif à un négatif et on soustrait un négatif à un négatif. Quand les opérandes sont de signes différents, on sait d'avance comment calculer le prédicat : un négatif est toujours inférieur à un positif.

Maintenant, regardons le cas où les opérandes sont de même signe. On se retrouve alors face à 4 cas différents, selon le signe de A - B. Le premier cas est celui où A et B sont positifs et A - B aussi. Dans ce cas, on sait que A > B : le prédicat est donc faux. Le second cas est celui où A et B sont positifs mais pas A - B. Dans ce cas, on sait que A < B : le prédicat est vrai. Le troisième cas est celui où les deux opérandes sont négatifs : la soustraction donne donc $-A-(-B)=B-A$. Si leur soustraction donne un résultat négatif, cela signifie que B - A est positif et donc que A < B : le prédicat est vrai. Si le résultat est positif, on est dans la situation inverse : le prédicat est donc faux.

En traduisant les signes en bits de signe, on a alors :

Signe de A	Signe de B	Signe de A - B	Prédicat A < B
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

En utilisant la méthode des minterms, on trouve l'équation suivante :

$(a.{\overline {b}})|\left[(a-b).{\overline {a\oplus b}}\right]$

Dans ce cas précis, l'équation précédente peut se simplifier en :

$(a.{\overline {b}})|\left[(a-b).(a|{\overline {b}})\right]$

Il faut cependant faire une précision importante : les opérations précédentes doivent modifier directement l'écriture binaire des opérandes. Autant cela ne pose pas de problèmes pour les opérations logiques et bit à bit, autant la soustraction ne donnera pas le bon résultat sans conversion. En C, cela demande d'utiliser des opérandes qui sont de type unsigned, et non des int. La conversion se fait en passant par des conversions de pointeurs assez spéciales.

Le prédicat d'infériorité/supériorité non-stricte

Les formules précédentes donnent un prédicat pour l'infériorité stricte A < B. Mais il est aussi possible de dériver un critère pour l'infériorité non-stricte A <= B. Pour cela, il faut simplement fusionner le critère d'égalité et celui d'infériorité : un simple OU entre les deux suffit ! L'équation obtenue peut naturellement se simplifier, avec beaucoup de labeur. La formule final obtenue est la suivante :

$({\overline {a}}|b).\left[(a\oplus b)|({\overline {b-a}})\right]$

Enfin, ce prédicat peut se calculer avec une seule instruction sur certaines processeurs. La plupart des processeurs ont dans leur registre d'état un bit qui indique si une retenue a été générée par une addition/soustraction. Tout addition/soustraction modifie ce bit selon son résultat. Certains processeurs permettent, à la suite d'un calcul arithmétique, de déplacer cette retenue dans un registre en une seule instruction. Dans le cas d'une soustraction, ce bit est mis à 1 si $A\leq B$. En clair, l'instruction précédente permet de calculer ce prédicat en une fois, sans passer par des opérations compliquées.

Le prédicat de comparaison

Le prédicat de comparaison permet de connaitre le signe du nombre. Traditionnellement, il s'agit d'une fonction qui vaut :

$signe(x,y)=\left\{{\begin{array}{r c l}1,x>y\\0,x=y\\-1,x<y\\\end{array}}\right.$

En utilisant les prédicats de comparaison précédent, on peut calculer cette fonction signe avec la formule suivante :

$(x>y)-(x<y)$

Pour comprendre cette formule, le mieux est de regarder d'étudier tous les cas possibles pour les comparaisons $x>y$ et $x<y$ et d'en déduire le résultat du calcul complet.

$x>y$	$x<y$		$(x>y)-(x<y)$
0	0		0
0	1		-1
1	0		1
1	1		Impossible

Une autre formule possible est la suivante :

$(x\geq y)-(x\leq y)$

Là encore, étudions tous les cas possibles pour voir ce que fait ce calcul.

$x\geq y$	$x\leq y$		$(x\geq y)-(x\leq y)$
0	0		Impossible
0	1		-1
1	0		1
1	1		0

Le prédicat de signe

Le prédicat de signe est une fonction qui vaut :

$signe(n)=\left\{{\begin{array}{r c l}1,n>0\\0,n=0\\-1,n<0\\\end{array}}\right.$

On peut remarquer que celui-ci se calcule en comparant le nombre avec 0 : il suffit d'utiliser la fonction précédente avec y = 0. On peut donc le calculer avec la fonction suivante :

$(x>0)-(x<0)$

$(x\geq 0)-(x\leq 0)$

Le prédicat d'inégalité des signes

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

Ou bien avec 3 comparaisons :

int SignUnequals (int a , int b)
{
    return ( a < 0 ) != ( b < 0 ); // Ou encore  ( 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 ;
}

Le branch-free code

De nombreuses opérations se calculent en faisant intervenir des branchements. Par exemple, si je vous demande de calculer la valeur absolue d'un entier, vous allez certainement m'écrire un code qui utilise des branchements. De nombreux calculs simples du même genre existent. Le calcul du minimum de deux nombres ou de leur maximum est l'un d'eux. Mais certains de ces calculs peuvent se faire sans utiliser de branchements ! Pour cela, il faut utiliser des techniques de manipulation de bit ou des opérations logiques. On obtient alors du branch-free code, du code sans branchements. Un tel code est très utile pour éliminer les branchements et gagner en performances. Il élimine les problèmes liés au branchements : mauvaises prédictions de branchement, meilleure utilisation du parallélisme d'instruction, etc. Le compilateur profite aussi de ces techniques, celui-ci se débrouillant mieux avec des blocs de code de grande taille. Certaines optimisations fonctionnent en effet nettement mieux quand il n'y a pas de branchements pour les gêner.

Le code branch-free est plus facile à écrire en assembleur que dans les langages de haut-niveau. La raison tient en l'utilisation des instructions à prédicat, qui rend très facile l'écriture des opérations suivantes. Le calcul du minimum ou maximum de deux nombres, qui sera vue plus loin, peut en effet s'écrire facilement avec des instructions CMOV. Les instructions à prédicats étant implémentées sur tous les jeux d'instruction grands public, les compilateurs peuvent, en théorie, les utiliser pour simplifier les opérations que nous allons voir. Mais le cout des opérations à prédicats est cependant assez élevé sur certaines architectures, ce qui rend les alternatives que nous allons présenter utiles, si ce n'est profitables. Ces techniques ont de plus le loisir d'être implémentables dans les langages de haut niveau. Voyons donc ces techniques dans le détail.

La différence avec zéro

Pour le premier calcul branche-free, nous allons voir le calcul de la différence avec zéro, aussi appelée DOZ (difference of zero) par les anglo-saxons. Ce calcul très simple sera utilisé pour implémenter d'autres expressions branch-free, comme le calcul du minimum/maximum de deux nombres, ou la valeur absolue d'un nombre. Nous la voyons donc en premier, même si elle est de peu d'utilité pratique. Cette différence avec zéro se définit comme une soustraction qui donnerait 0 si son résultat est négatif.

$doz(x,y)=\left\{{\begin{array}{r c l}x-y,x>y\\0,x\leq y\\\end{array}}\right.$

Ce calcul s'implémente avec l'expression suivante, qui fonctionne avec des opérandes signées et non-signées :

$(x-y).-(x\geq y)$

int doz (int x, int y)
{
    return ( x - y ) && - ( x >= y ) ;
}

La valeur absolue et son inverse

Passons maintenant à la valeur absolue et à son inverse. Si je vous demande de calculer la valeur absolue d'un entier, vous allez certainement m'écrire le code suivant :

int abs (int a)
{
    if (a > 0)
        return a ;
    else
        return - a ;
}

Mais il existe des méthodes sans branchements qui donnent le même résultat.

Le calcul de la valeur absolue

Pour calculer la valeur absolue, il existe trois méthodes alternatives. Toutes ces méthodes nécessite d'isoler le bit de signe. Pour cela, il suffit d'utiliser un décalage logique pour déplacer ce bit et le mettre dans le bit de poids faible. Dans ce qui suit, ce bit de signe sera noté $y$. La valeur absolue d'un nombre x peut se calculer comme ceci :

$(x\oplus y)-y$ ;

$(x+y)\oplus y$ ;

$x-\left[(2\times x).y\right]$.

Les codes correspondant à chaque ligne est le suivant pour des entiers de 32 bits :

int abs (int x)
{
    int y = x >> 31 ;
    return (x ^ y) - y ;
}

int abs (int x)
{
    int y = x >> 31 ;
    return x - ( (x << 1) & y ) ;
}

int abs (int x)
{
    int y = x >> 31 ;
    return (x + y) ^ y ;
}

Le calcul de la valeur absolue inverse

Pour obtenir l'inverse de la valeur absolue, il suffit de prendre l'opposée de celle-ci. En appliquant un simple - devant les expressions du dessus, on peut alors avoir diverses formules pour le calcul de l'inverse de la valeur absolue :

$y-(x\oplus y)$ ;

$(y-x)\oplus y$ ;

$\left[(2\times x).y\right]-x$.

Le minimum et maximum d'un nombre

Si je vous donne deux nombres et que je vous demande d'écrire un code qui renvoie le plus petit des deux, il y a de fortes chances que vous m'écriviez ceci :

int min (int a , int b)
{
    if (a > b)
        return b ;
    else
        return a ;
}

Une autre manière est d'utiliser la différence avec zéro. En effet, on sait que :

$min(x,y)=x-doz(x,y)$

$max(x,y)=y+doz(x,y)$

Le calcul du minimum de deux nombres

Si on remplace le doz par l'expression vue plus haut, on trouve :

$min(a,b)=a-(a-b).-(a\geq b)$

Divers simplifications algébriques et booléennes donnent ensuite :

$min(a,b)=b\oplus \left((a\oplus b).-(a<b)\right)$

Voici le code qui correspond :

int min (int a , int b)
{
    return b ^ ( (a ^ b) & -(a < b) ) ;
}

L'idée derrière ce calcul est assez simple, bien que l'expression soit relativement compliquée. Pour la comprendre, il faut regarder ce qui se passe quand b < a et quand b >= a. Si b < a, alors la comparaison a < b renvoie un 0. Le terme complet (a ^ b) & -(a < b) donne alors 0 et l'expression se simplifie alors en b ^ 0, ce qui donne b. En clair, si b < a, alors le code renvoie b, ce qui est bien ce qu'on lui demande. Dans le cas où b >= a, alors la comparaison renvoie 1. Elle est alors inversée = le terme -(a < b) donne alors -1, ce qui est un nombre dont tous les bits sont à 1 en complément à 2. Le terme (a ^ b) & -(a < b) se simplifie donc en (a ^ b). L'expression totale est alors : b ^ (a ^ b). On sait que cela donne a. En clair, si a < b, le code renvoie a, ce qui lui est demandée.

Le calcul du maximum de deux nombres

On peut appliquer la même logique que précédemment, à savoir remplacer la doz par sa valeur calculée dans la première section. On trouve alors, après simplification, que le calcul du maximum est identique, si ce n'est qu'il faut inverser la comparaison. On doit alors calculer $b\oplus \left((a\oplus b).-(a>b)\right)$

int max (int a , int b)
{
    return b ^ ( (a ^ b) & -(a > b) ) ;
}

Appliquer un masque différemment suivant le résultat d'une condition

Appliquer un masque sur un nombre permet de mettre à 1 les bits choisit, ou alors de les mettre à zéro. On peut vouloir faire l'un ou l'autre selon si une condition bien précise est remplie : on met à 1 les bits si la condition est remplie, à 0 sinon. Le code qui correspondrait serait celui-ci :

bool condition_result;         // Résultat de la condition
unsigned int mask ; // Le masque
unsigned int word ; // Nombre à maquer

if (condition_result)
{
    word |= mask ; // mettre à 1 les bits voulus
}
else
{
    word &= ~mask ; // mettre à 0 les bits voulus
}

Il existe deux solutions sans branchements. La première est celle-ci :

bool condition_result ;         // Résultat de la condition
unsigned int mask ; // Le masque
unsigned int word; // Nombre à maquer

word ^= ( - condition_result ^ word) & mask ;

Une solution équivalente serait la suivante :

bool f;         // Résultat de la condition
unsigned int m; // Le masque
unsigned int w; // Nombre à maquer

word = (word & ~mask) | ( - condition_result & mask );

Les opérations arithmétiques sur des entiers

Les opérations bit à bit permettent d'effectuer certains calculs arithmétiques assez simplement et souvent avec des performances très intéressantes. Dans ces conditions, effectuer des calculs arithmétiques avec des opérations bit à bit est un bon investissement. Dans ce qui va suivre, nous allons évidemment travailler avec des nombres en complément à deux.

Petite précision, avant de commencer : nous allons beaucoup faire intervenir des nombres de la forme $2^{n}$ et $2^{n}-1$ dans ce chapitre. Il faut dire qu'en binaire, les puissances de deux ont un rôle tout particulier à jouer, en lien avec le fait que le binaire est la base 2. En binaire, les puissances de deux ont un rôle équivalent à celui des puissances de 10 en décimal. Dans la numération décimale de tous les jours, les nombres comme 10, 100, 1000 sont particuliers. Certaines opérations sont drastiquement plus simples avec des nombres qu'avec les autres : pensez notamment aux divisions et multiplications par 10 ! En binaire, c'est la même chose avec les puissances de deux.

La moyenne de deux nombres

Calculer la moyenne de deux nombres peut sembler simple comme bonjour. Il suffit d'appliquer la formule $(x+y)/2$. Mais cette expression peut donner lieu à un débordement d'entier : le calcul de x + y peut dépasser la taille d'un registre, ce qui donnera un résultat totalement faux. Pour éviter cela, on peut ruser en utilisant des astuces mathématiques. Une première astuce consiste à reformuler l'équation $(x+y)/2$ de manière à éviter d'additionner x et y. Si $x\leq y$, on sait que la moyenne se calcule comme suit : $x+(y-x)/2$. Mais cette expression peut encore être simplifiée en utilisant des opérations bit à bit, plus rapides.

Le calcul avec des nombres non-signés

Pour rappel, la somme de deux bits a et b donne un bit de résultat et une retenue. Le bit de résultat vaut $a\oplus b$, tandis que la retenue vaut $a.b$. C'est exactement la même chose pour la somme de deux nombres A et B, si on prend en compte le fait que les retenues doivent être additionnés aux bits de résultats de la colonne suivante. On peut donc calculer la somme de deux nombres en calculant les bits de résultat (sans propager les retenues) et les retenues séparément : il suffit d'additionner ces deux termes pour obtenir le résultat. N'oublions pas que les retenues doivent être additionnées à la colonne suivante, ce qui fait que le terme pour les retenues doit être décalé d'un cran vers la gauche. Vu que les retenues se calculent en faisant $(A.B)<<1$ et les bits de résultat avec $A\oplus B$ , on a :

$A+B=(A.B)<<1+A\oplus B$

Maintenant, divisons le tout par deux pour obtenir la moyenne, ce qui revient à tout décaler d'un cran vers la droite. On obtient alors la formule pour calculer la moyenne :

$(A+B)/2=(A.B)+(A\oplus B)>>1$

Celle-ci peut être reformulée comme suit, en utilisant les identités sur l'addition et la soustraction du premier chapitre :

$(A+B)/2=(A|B)-(A\oplus B)>>1$

Voici le code source qui correspond à la première formule :

unsigned average (unsigned a , unsigned b)
{
    return ( a & b ) + ( a ^ b ) >> 1 ;
}

Le calcul avec des nombres signés

Le calcul de la moyenne pour les nombres signés peut se faire avec les formules précédentes, à condition de remplacer le décalage par un décalage arithmétique. Mais dans ce cas, il faut faire attention aux arrondis pour les nombres négatifs. Autant cela ne pose aucun problème pour les nombres positifs, autant l'arrondi des nombres négatifs est quelque peu erroné. Par exemple, la moyenne de -5 et -2 peut être arrondie de deux manières : soit vers 0, ce qui donne -2, soit vers $-\infty$ ce qui donne -3. Les calculs précédents vont causer un arrondi vers $-\infty$. Pour les nombres positifs, ces deux arrondis sont identiques, mais donnent des résultats différents pour les négatifs. Précisons que le problème d'arrondi ne se manifeste que pour les résultats négatifs et impairs.

Pour obtenir un arrondi vers 0, les formules de la section précédente doivent être modifiées. L'idée est de prendre les formules précédentes, mais de corriger le résultat s'il est négatif et impair (condition obligatoire pour que l'arrondi soit problématique). La correction consiste à incrémenter le résultat. Pour cela, on peut prendre le bit de signe du résultat x + y ou celui de la moyenne, ces deux bits étant identiques. Pour un nombre de n bits, celui-ci se calcule avec la formule $x>>(n-1)$. Une fois ce bit de signe obtenu, il faut l'additionner seulement si x + y est impair. Déterminer si la somme de deux nombres est impair est simple : le bit de poids faible doit être égal à 1. Il peut se calculer avec un XOR entre les deux opérandes à moyenner. Une fois qu'on a le bit de poids faible et le bit de signe localisés sur la même colonne, il suffit de faire un ET entre les deux : le résultat de l’opération donne un bit qui vaut 1 si la moyenne est impaire et négative, et 0 sinon. Il reste à additionner ce bit à la moyenne pour la corriger.

$a=(A|B)-(A\oplus B)>>1$

$b=(t>>(n-1).(x\oplus y)$

$(A+B)/2=a+b$

La multiplication par une constante

Les opérations de multiplication entière sont gourmandes en temps d’exécution et toute optimisation est bonne à prendre. Les compilateurs modernes sont capables d'optimiser un grand nombre de multiplications pour les remplacer par des opérations plus rapides. Cela arrive souvent lorsqu'on utilise des tableaux : les calculs d'adresses localisés dans des boucles peuvent parfois être optimisés et certaines multiplications sont alors remplacées par des additions. À ce petit jeu, la multiplication par une constante est une opportunité d'optimisation importante. On a vu précédemment qu'il est possible de remplacer la multiplication par une puissance de deux par un simple décalage. Ce qui va suivre se base sur ce principe, même si nous allons aborder la multiplication par autre chose qu'une puissance de deux. Aussi bizarre que cela puisse paraitre, il y a deux méthodes pour cela. Suivant la situation, l'une d'entre elle sera plus rapide que l'autre : tout dépend du nombre de bits à 1 dans la constante.

Décaler et additionner

Comme vous le savez, tout nombre entier est une somme de puissances de deux. C'est d'ailleurs le principe qui est derrière le binaire. Dans ce cas, multiplier par une puissance, c'est multiplier par une somme de puissances de deux. Avec quelques manipulations algébriques simples, cette multiplication peut se transformer en une somme de multiplications par une puissance de deux. Supposons que je veuille effectuer une multiplication entre un nombre A, et une constante B. Il est évident que B est une somme de puissances de deux. Dans ce cas, je peux remplacer B par la somme de puissances de deux qui correspond. Dans ce qui va suivre, nous allons prendre B = 13. Pour rappel, $13=8+4+1=2^{3}+2^{2}+2^{0}$ :

$A\times (2^{3}+2^{2}+2^{0})$

En utilisant la distributivité de la multiplication, on trouve :

$A\times 2^{2}+A\times 2^{0}+A\times 2^{3}$

Dans cette expression, on a donc une somme, qui additionne quelques termes. Ces termes sont tous des multiplications par une puissance de deux. On peut les remplacer par un décalage vers la gauche.

$(A<<3)+(A<<2)+A$

Ainsi, la multiplication par 13 peut se remplacer en deux décalages et deux additions.

Le principe reste le même pour toute multiplication par une constante : en décomposant la constante en puissances de deux, et avec quelques calculs, on peut transformer une multiplication par une constante en série de décalages et d'additions. Le nombre de décalages effectué est égal au nombre de bits à 1 dans la constante. Le nombre d'additions est presque identique. Si la constante contient donc trop de bits à 1, il se peut que le nombre de décalages et d'additions soit trop important : une multiplication peut être plus rapide. Cette technique ne marche donc que pour les nombres ayant un nombre de bits à 1 faible : 2-3 bits, parfois plus sur les architectures ayant une multiplication particulièrement lente, mais pas plus.

Décaler et soustraire

Dans le cas où un nombre contient beaucoup de bits à 1, il existe une seconde méthode. Elle se base sur un principe légèrement différent, mais assez similaire à celui utilisé dans la méthode précédente. Comme vous le savez, un nombre entier peut s'écrire sous la forme d'une somme de puissances de deux. Par exemple, $5=2^{2}+2^{0}$. Ceci dit, 5 peut aussi s'écrire sous une autre forme. Si on remarque bien, $5=8-3$. Dans cette expression, 8 est une puissance de 2, et 3 est un nombre comme un autre. Si on réfléchit bien, tout nombre entier peut s'écrire sous la forme $2^{n}-x$.

Prenons un exemple avec une multiplication par 5.

$5=8-3$

Dans cette expression, on peut remplacer chaque nombre par son expression en binaire. En clair, on le remplace par la somme de puissances de deux qui correspond.

$5=2^{3}-(2^{1}+2^{0})$

$5=2^{3}-2^{1}-2^{0}$

Maintenant, supposons que l'on veuille multiplier un nombre A par 5. On peut alors remplacer 5 par l'expression avec décalages et soustractions :

$A\times 5=A\times (2^{3}-2^{1}-2^{0})$

En se rappelant que la multiplication est distributive, on obtient :

$A\times 5=A\times 2^{3}-A\times 2^{1}-A\times 2^{0})$

Dans cette expression, on peut alors remplacer les multiplications par des puissances de deux par des décalages à gauche :

$A\times 5=A<<3-A<<1-A$

Comme on le voit, cette expression ne contient que des décalages et des soustractions. Et le principe est le même pour tout entier. Il suffit d'écrire la constante comme une puissance de deux à laquelle on aurait soustrait ce qu'il faut. Pour cela, il suffit de prendre la puissance de deux immédiatement supérieure à notre constante : cela simplifie les calculs et diminue le nombre de soustractions. On a donc l'équation : constante + nombre à soustraire = puissance de deux choisie. Si on calcule sur n bits, la puissance de deux aura n+1 bits et vaudra donc zéro. En clair : constante + nombre à soustraire = 0. Ce qui signifie que constante = - nombre à soustraire : le nombre à soustraire est donc le complément à deux de la constante, codé sur n bits. Cela nous dit donc que plus un nombre à de bits à 1, plus son complément à deux aura de bits à 0 : le nombre de soustractions à effectuer sera donc plus faible. Cette technique marche donc nettement mieux pour les nombres remplis de 1.

La division par une constante

Après la multiplication par une constante, il faut savoir que la division par une constante peut aussi être améliorée. On sait déjà ce qu'il en est pour la division par une puissance de deux : il suffit de la remplacer par un décalage vers la droite, en prenant garde à bien choisir entre décalage arithmétique et logique. Pour ce qui est de la division par une constante arbitraire, il est possible d'utiliser une technique d'optimisation particulièrement efficace : la multiplication réciproque. Cette technique nous permet de remplacer la division par une constante en une multiplication. Les divisions étant des opérations nettement plus lentes que les multiplications, on peut facilement gagner quelques dizaines de cycles d'horloge.

Mais tout d'abord, nous devons préciser une chose. Lorsqu'on multiplie deux nombres de $n$ bits, leur produit a une taille qui est de $2^{n}$ bits. Dans le détail, on a besoin de deux fois plus de bits pour le résultat. D'ordinaire, on s'en moque, et on se contente de garder les $n$ bits de poids faible. Mais dans ce qui va suivre, nous allons avoir besoin des $n$ bits de poids fort. Heureusement, certains processeurs disposent d'instructions de multiplications qui calculent ces bits de poids fort, le résultat étant enregistré dans deux registres : un pour les bits de poids faible, un autre pour les registres de poids forts. D'autres processeurs disposent d'une instruction qui effectue la multiplication et ne conserve que les bits de poids forts dans un registre. Enfin, certains processeurs disposent d'instructions de multiplication configurables, qui permettent de choisir quels bits conserver : poids fort ou poids faible.

La multiplication réciproque est basée sur un principe simple : diviser par $N$, c'est multiplier par $1 \over N$. Si N est une constante, alors on peut pré-calculer $1 \over N$ et éliminer ainsi la division. Et là, un premier problème semble se faire jour : cela marche peut-être pour les nombres flottants, mais ne peut pas fonctionner avec des nombres entiers. Mais on peut sauver le principe en remplaçant $1 \over N$ par une constante judicieusement choisie, dont la multiplication donnera le résultat voulu. Si on multiplie par cette constante et que l'on garde les bits de poids forts, on obtiendra le même résultat qu'avec une multiplication par $1 \over N$ (sur les bits de poids faible). Cette constante vaut, par définition : $2^{n} \over N$. En effet, regardons ce que donne l’opération suivante, avec A le nombre qu'on cherche à diviser par N :

$A\times {\frac {2^{n}}{N}}$

On réarrange les termes :

$2^{n}\times {\frac {A}{N}}$

Rappelons que multiplier par $2^{n}$ est équivalent à faire un décalage à gauche de n bits. Faire le remplacement donne :

${\frac {A}{N}}<<n$

En clair, on obtient le résultat de la division de A par N, mais décalé de n rangs : on obtient bien le résultat de la division dans les bits de poids fort.

Cette méthode demande que le calcul de $2^{n} \over N$ tombe juste, qu'il n'y ait pas de part fractionnaire. Mais ce n'est pas le cas pour certaines constantes, notamment N = 10, 7, 11, et grosso-modo, tout ce qui n'est pas une puissance de deux. Dans ce cas, le mieux est de rechercher des constantes proches de la constante réciproque qui donnent de meilleurs résultats. Cependant, l'imprécision de la constante réciproque est alors à l'origine d'erreurs de calcul et le résultat doit être corrigé avant d'être utilisable. Cette correction est une simple addition, qui ajoute un paramètre déterminé, fixe, qui dépend de la constante.

Le modulo par une puissance de deux

Dans les chapitres précédents, nous avons vu que calculer le modulo par $2^{n}$ est très simple : il suffit de masquer les bits de poids fort et de ne garder que les n bits de poids faible. Mais pour les nombres signés, cette méthode basée ne marche tout simplement pas pour le calcul du modulo. On peut cependant faire le modulo de la valeur absolue, avant de rétablir le signe du résultat.

Dans ce qui va suivre, nous allons noter le bit de signe $y$. Celui-ci sera mis dans un nombre, précisément dans son bit de poids faible.

Première méthode

Une première formule pour le calcul du modulo est la suivante :

$mod(n,2^{n})=\left\{{\begin{array}{r c l}x.(2^{n}-1)&x>=0\\-\left(-x.(2^{n}-1)\right)&x<0\\\end{array}}\right.$

Le calcul du modulo d'un nombre signé peut donc se réaliser avec l'équation suivante :

$\left(abs(x).(2^{n}-1)\right)\oplus y-y$

La seule exception est quand on souhaite calculer le modulo 2. Dans ce cas, le bit de poids faible donne directement le modulo, peu importe le signe du nombre testé. Le calcul est alors le suivant :

$\left(x.1\right)\oplus y-y$

Seconde méthode

Une autre solution est d'utiliser la formule suivante :

$mod(n,2^{n})=\left\{{\begin{array}{r c l}x.(2^{n}-1)&x>=0\\\left(x+y).(2^{n}-1)\right)-y&x<0\\\end{array}}\right.$

Le calcul du modulo d'un nombre signé peut donc se réaliser avec l'équation suivante :

$\left(x+y).(2^{n}-1)\right)-y$

Les opérations arithmétiques sur des flottants

Après avoir vu comment certains calculs entiers peuvent se réaliser via des opérations logiques, il est temps de voir des astuces de calcul sur des nombres flottants. Dans ce qui va suivre, nous allons travailler avec des nombres flottants au format IEEE754, le format le plus courant (pour ne pas dire le seul utilisé à l'heure actuelle).

La représentation binaire d'un flottant et les astuces associées

Pour rappel, le codage d'un nombre flottant demande d'écrire celui-ci sous la forme suivante :

$\pm (1+m)\times 2^{e}$, avec $m\in [0,1[$ la mantisse et e l'exposant.

Il ne s'agit ni plus ni moins que l'écriture scientifique que vous avez certainement vu dans votre scolarité, mais adaptée en base 2. En gros, on écrit le nombre sous la forme d'un produit entre une puissance de deux et un autre nombre. L'autre nombre doit être compris entre 1 et 2, pour éviter que l'on ait plusieurs représentations identiques, afin que l'exposant et le nombre multiplié soient uniques. Il est inutile d'encoder la partie entière du nombre, qui vaut toujours 1, mais il est nécessaire d'encoder sa partie fractionnaire. Cela fait donc trois informations à encoder : le signe (flottant positif ou négatif), l'exposant, et la partie fractionnaire du nombre multipliée qui est appelée mantisse.

Le tout est encodé en binaire, en concaténant trois informations : un bit de signe, un champ pour l'exposant et un champ pour la mantisse.

IEEE754 Format Général

Dans ce qui suit, la représentation binaire du flottant sera notée I, celle de l'exposant sera notée E, celle de la mantisse sera notée M. Si on néglige le bit de signe, un nombre flottant se calcule donc comme suit, à partir des deux représentations binaires de l'exposant et de la mantisse :

$I=E<<n+M$

$I=E\times L+M$, avec $L=2^{n}$

La mantisse est codée normalement, sous la forme d'un nombre en virgule fixe/d'un entier. L'exposant est quant à lui un nombre pouvant être nul, positif ou négatif. Mais il n'est pas codé en complément à deux, mais en représentation par excès. La représentation par excès consiste à ajouter un biais aux nombres à encoder afin de les encoder par un entier positif. Pour encoder tous les nombres compris entre -X et Y en représentation par excès, il suffit de prendre la valeur du nombre à encoder, et de lui ajouter un biais égal à X. Ainsi, la valeur -X sera encodée par zéro, et toutes les autres valeurs le seront par un entier positif. Par exemple, prenons des nombres compris entre -127 et 128. On va devoir ajouter un biais égal à 127, ce qui donne :

Valeur avant encodage	Valeur après encodage
-127	0
-126	1
-125	2
…	…
0	127
…	…
127	254
128	255

Pour résumer, partons d'un flottant écrit comme suit : $e=\pm (1+m)\times 2^{e}$. L'exposant est en représentation par excès, ce qui veut dire que l'on a :

$E=e+B$, avec e l'exposant et B le biais de la représentation par excès.

La représentation binaire de la mantisse M s'obtient en prenant la mantisse m (qui est un nombre à virgule compris entre 0 et 1) et en décalant le tout de n rangs vers la gauche. En clair :

$M=m\times L$

On peut alors combiner le tout avec l'équation $I=E\times L+M$, ce qui donne :

$I=(e+B)\times L+m\times L$

$I=(e+B+m)\times L$

Et à partir de cette représentation binaire, certaines opérations deviennent assez simples. Pour cela, il faut cependant traiter le flottant comme s'il s'agissait d'un entier, afin d'utiliser des opérations logiques dessus. Mais en C et dans les autres langages de ce type, les opérations bit à bit ne fonctionnent pas sur les flottants. Il est cependant possible de contourner le problème en faisant quelques manipulations. Dans le langage C, ces manipulations se résument à des conversions et déréférencements entre pointeurs. Le but est alors de copier la représentation binaire d'un flottant dans un nombre entier, sur lequel on pourra effectuer des opérations logiques et/ou mathématiques dessus. Le code pour cela est celui-ci :

    long i  = * ( long * ) &y ; // Bidouille qui permet de copier l'écriture binaire d'un flottant y dans un entier i.

Le code à comprendre est assez simple : on prend un pointeur vers le flottant voulu, puis on convertit ce pointeur sur un flottant en pointeur sur un entier (de type long), et enfin on déréférence ce pointeur.

Le calcul de la valeur absolue d'un flottant

Nous allons commencer par une opération extrêmement simple : la valeur absolue. On sait que les flottants sont codés avec une représentation spéciale. Le signe d'un flottant est indiqué par un bit de signe, localisé dans le bit de poids fort. Obtenir sa valeur absolue demande simplement de mettre ce bit de signe à 0. Un simple masque suffit !

(((int *) &x) + 1) &= 0x7fffffff ;

Les comparaisons entre flottants

Chose peu connue, il est possible de comparer deux nombres flottants en utilisant les comparaisons pour nombres entiers. Du fait de leur encodage, les comparaisons entre flottants et entiers sont différentes sur le papier. Mais dans les faits, quelques propriétés de l'encodage des flottants fait que l'on peut comparer deux flottants comme s'ils s'agissait d'entiers sans problèmes. Ce que cela veut dire, c'est que si l'on prend l'écriture binaire de deux flottants, et que l'on compare ces écritures comme s'il s'agissait d'entiers, alors le résultat de la comparaison sera le bon. Cela vient du fait que deux flottants consécutifs auront un encodage consécutifs, chose qui est garantie par la norme IEEE754.

Tout du moins, cela fonctionne dans la plupart des cas, bien que cela demande quand même quelques précisions. Premièrement, l'encodage du bit de signe pose quelques problèmes : les nombres négatifs suivent les positifs du point de vue de l'écriture binaire. La solution est alors d'utiliser une comparaison signée. Pour régler ce problème, il suffit d'inverser le bit de signe avec le masque adéquat.

Et cela peut se comprendre quand on regarde l'équation qui donne la représentation binaire d'un flottant positif :

$I=E\times L+M$, avec $L=2^{n}$

Si on compare deux flottants, le plus grand des deux est celui qui a l'exposant le plus grand, ou la mantisse la plus grande si les deux exposants sont égaux. L'exposant étant dans les bits de poids fort, on comprend que l'exposant passera en priorité dans la comparaison, et que les mantisses seront comparées si les deux exposants sont égaux.

Le calcul du logarithme d'un flottant

Nous verrons dans quelques chapitres comment trouver le logarithme d'un entier, pour des raisons liée à la nature de ce calcul, mais la méthode que nous aborderons ne fonctionne évidemment pas sur les nombres flottants. Pour ceux-ci, il existe cependant une méthode assez simple, qui demande de passer par l'écriture binaire du flottant en question. La technique que l'on va voir donne un résultat entier, pas un flottant.

Prenons un nombre x qui vaut :

$x=2^{e}\times (1+m)$, avec m la mantisse et e l'exposant.

Prenons le logarithme en base 2 :

$\log _{2}{x}=\log _{2}{(2^{e}\times (1+m))}$

Vu que le logarithme d'un produit est égal à la somme des logarithmes, on a :

$\log _{2}{x}=\log _{2}{(2^{e})}+\log _{2}{(1+m)}$

Ce qui se simplifie en :

$\log _{2}{x}=e+\log _{2}{(1+m)}$

Le calcul du logarithme d'une somme est complexe et ne peut pas se faire simplement. Heureusement, vu que la mantisse est comprise entre 0 et 1, on a l'approximation suivante qui tient bien la route :

$\log _{2}(1+m)\approx m+\sigma$, avec $\sigma$ un facteur correctif variable, souvent pris égal à 0,0430357.

On a alors :

$\log _{2}{x}\approx e+m+\sigma$

L'équation précédente nous donne une idée de comment calculer le logarithme binaire d'un flottant. Rappelons que les trois termes de l'équation sont des nombres fractionnaires, ce qui fait que les calculs peuvent se faire aussi bien en virgule flottante qu'en virgule fixe, mais pas avec des nombres entiers. Pour calculer le logarithme entier, il faut faire des approximations.

Le logarithme entier d'un nombre flottant

Si l'exposant est codé par un entier dans le nombre flottant, le terme m est un nombre fractionnaire compris entre 0 et 1, de même que $\sigma$. Si on veut un résultat qui soit un nombre entier, on doit se contenter du terme e, ce qui donne :

$\lfloor \log _{2}{x}\rfloor \approx e$

En clair, le logarithme binaire d'un nombre n'est autre que l'exposant de la représentation flottante ! Et pour extraire cet exposant, il suffit de faire quelques décalages sur l'écriture binaire du flottant. Il faut cependant se souvenir que l'exposant est encodé en représentation par excès, ce qui fait qu'il doit lui soustraire le biais adéquat pour obtenir sa valeur normale. La formule mathématique suivante permet de calculer l'exposant à partir de la représentation binaire d'un flottant, notée I, et du biais B de la représentation par excès :

$\lfloor \log _{2}{x}\rfloor \approx E-B$

$\lfloor \log _{2}{x}\rfloor \approx (I>>n)-B$

Le tout peut s'écrire comme ceci :

$\lfloor \log _{2}{x}\rfloor \approx {\frac {I}{L}}-B$, avec $L=2^{n}$.

Précisons qu'ici, la division par L est une division entière.

Le code devrait être le suivant pour un flottant 32 bits (simple précision). La première ligne permet de traiter directement l'écriture binaire du flottant, afin de faire les décalages et autres. Il faut cependant signaler que ce code ne fonctionne pas avec les flottants dénormaux.

float rsqrt(float n)
{
    long i  = * ( long * ) &n ;
    unsigned e = (c >> 23) - 127 ;
    return e ;
}

Le calcul du logarithme binaire à partir de l'interprétation de la représentation binaire d'un flottant

Log by aliasing to int

Dans cette section, nous allons voir que le logarithme d'un flottant peut se calculer à partir de sa représentation binaire. Pour simplifier le tout, négligeons totalement le bit de signe pour le moment, en supposant que le nombre traité est positif. Rappelons que l'écriture binaire d'un flottant est mathématiquement définie par la formule suivante, pour un nombre flottant positif :

$I=(e+B+m)\times L$

On peut donc déterminer la somme e + m à partir de la représentation binaire d'un flottant, ce qui est presque égal au logarithme.

${\frac {I}{L}}=e+B+m$

${\frac {I}{L}}-B=e+m$

Mais il reste à faire apparaitre le terme $\sigma$. Pour cela, ajoutons les termes sigma comme ceci :

${\frac {I}{L}}-B+\sigma =e+m+\sigma$

On applique alors la formule $\log _{2}{(x)}\approx e+m+\sigma$ :

${\frac {I}{L}}-B+\sigma \approx \log _{2}{(x)}$

En réarrangeant les termes, on trouve alors :

$\log _{2}{x}\approx {\frac {I}{L}}-(B-\sigma )$

Le calcul de la racine carrée inverse d'un flottant

Dans cette section nous allons nous intéresser au calcul de la racine carrée inverse, à savoir : $1 \over {\sqrt {x}}$. L'algorithme utilisé se base sur l'identité mathématique suivante :

$\log {\left({\frac {1}{\sqrt {x}}}\right)}=-{\frac {1}{2}}\log {x}$

Pour simplifier les calculs pour un ordinateur, il est naturel de prendre le logarithme en base 2 de l'opérande.

$\log _{2}{\left({\frac {1}{\sqrt {x}}}\right)}=-{\frac {1}{2}}\log _{2}{x}$

La solution consiste donc à calculer le logarithme de l'opérande, multiplier par - 0.5, et prendre le logarithme inverse (l'exponentielle). On sait déjà comment calculer ce logarithme en base 2 pour un entier, la division ne pose pas de problèmes (c'est un simple décalage) et le calcul de l'exponentielle est trivial : $2^{n}=1<<n$. Mais cette méthode ne fonctionne que pour des entiers : il faut donc convertir le nombre flottant voulu en entier et appliquer dessus les calculs. Avec les flottants, on vient cependant de voir comment calculer le log binaire d'un flottant, ce qui permet de faire la première étape. On vient aussi de voir comment traduire un résultat en virgule fixe en flottant, ce qui correspond à la troisième étape.

Passage par la représentation entière

On vient de voir il y a quelques sections que :

$\log _{2}(x)={\frac {I}{L}}-(B-\sigma )$

On peut combiner les deux équations précédentes pour remplacer le terme de gauche et le terme de droite. Il faut alors faire la différence entre la représentation binaire du résultat, notée $I_{y}$ et celle de l'opérande, notée $I_{x}$. Remplaçons le terme de droite en priorité :

$\log _{2}{\left({\frac {1}{\sqrt {x}}}\right)}=-{\frac {1}{2}}\left[{\frac {I_{x}}{L}}-(B-\sigma )\right]$

Le tout se simplifie en :

$\log _{2}{\left({\frac {1}{\sqrt {x}}}\right)}={\frac {1}{2}}(B-\sigma )-{\frac {1}{2}}{\frac {I_{x}}{L}}$

Maintenant, on peut appliquer la formule $\log _{2}(x)={\frac {I}{L}}-(B-\sigma )$ sur le terme de gauche. On a donc :

${\frac {I_{y}}{L}}-(B-\sigma )={\frac {1}{2}}(B-\sigma )-{\frac {1}{2}}{\frac {I_{x}}{L}}$

On réarrange les termes :

${\frac {I_{y}}{L}}={\frac {3}{2}}(B-\sigma )-{\frac {1}{2}}{\frac {I_{x}}{L}}$

On multiplie par L :

$I_{y}={\frac {3}{2}}(B-\sigma )L-{\frac {1}{2}}I_{x}$

Pour un flottant 32 bits, le terme de gauche vaut : ${\frac {3}{2}}(B-\sigma )\times L={\text{0x5f3759df}}$. On a donc :

$I_{r}={\text{0x5f3759df}}-{\frac {1}{2}}I_{x}$

Évidemment, il ne s'agit là que d'une approximation. Le code correspondant est le suivant :

float rsqrt(float number)
{
    long i  = * ( long * ) &y ; // Bidouille qui permet de traiter l'écriture binaire d'un flottant.
    i  = 0x5f3759df - ( i >> 1 ) ; // Utilisation du calcul précédent, en remplaçant la division par deux par un décalage.
    float y  = * ( float * ) &i; // Conversion du résultat en flottant, facultatif.

    return y;
}

Le calcul de la racine carrée inverse rapide d'un flottant

Imprécision de la racine carré inverse.

Les raisonnements précédents sont à 'origine d'une bidouille vraiment intéressante, incorporée dans certains moteurs de jeux vidéo. Celle-ci se base sur le principe vu dans la section précédente. On ne sait pas qui l'a inventé, mais il est devenu célèbre lors de la publication du code source de Quake 3 arena, un vieux fast FPS comme on en fait plus, très sympa à jouer en LAN. Un vrai jeu, quoi ! Bref, dans les jeux vidéo, on a souvent besoin de calculer la racine carrée inverse. Ce calcul est évidemment effectué sur des nombres flottants. Mais à l'époque de la création de ce jeu vidéo, les opérations flottante étaient très lentes. Et elles le sont toujours un petit peu, d'ailleurs. Pour diminuer la lenteur du calcul de la racine carrée inverse, on a inventé la Fast Inverse SQRT, afin de calculer celle-ci en utilisant uniquement des opérations entières ! Cet algorithme prend un flottant 32 bits, et donne une approximation de la racine carrée inverse. La qualité de cette approximation est illustrée à droite. Cet algorithme est très simple, jugez plutôt :

float rsqrt(float number)
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;
    x2 = number * 0.5F;
    y  = number;

    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
    y  = * ( float * ) &i;

    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    //y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

La version en C moderne, à laquelle on aurait omis quelques optimisations, donnerait ceci :

float rsqrt(float number)
{
    float y  = number;

    long i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
    y  = * ( float * ) &i;

    y  = y * ( 1.5F - ( y * y * number / 2 ) );   // 1st iteration
    //y  = y * ( 1.5F - ( y * y * number / 2 ) );   // 2nd iteration, this can be removed

    return y;
}

Les deux dernières lignes de code, dont celle mise en commentaire, correspondent chacune à une itération de la méthode de Newton, une méthode utilisée pour déterminer des approximations de fonctions à partir d'une approximation initiale. Les lignes de code précédentes calculent une approximation assez précise de la racine carrée inverse, qui est ensuite utilisée telle quelle par la méthode de Newton. Le premier "bloc" de code contient de simples déclarations de variables utilisées dans le calcul, la plupart servant uniquement à rendre les calculs plus lisibles. Les lignes suivantes contiennent des conversions et déréférencements entre pointeurs qui permettent d’accéder directement à l'écriture binaire du flottant, afin de traiter celle-ci avec des opérations logiques comme s'il s'agissait d'un entier. Le calcul de l'approximation réutilise ce qu'on a vu dans la section précédente, par la ligne de code suivante :

i  = 0x5f3759df - ( i >> 1 ) ;

Les débordements d'entiers

Les instructions arithmétiques et quelques autres manipulent des entiers de taille fixe, qui ne peuvent prendre leurs valeurs que dans un intervalle. Si le résultat d'un calcul sort de cet intervalle, il ne peut pas être représenté par l'ordinateur : il se produit ce qu'on appelle un débordement d'entier. Dans la plupart des applications, ces débordements ne posent pas le moindre problème. Mais pour d'autres situations, ces débordements doivent être détectés avant ou juste après leur occurrence. Certains processeurs disposent d'instructions pour détecter de tels débordements. D'autres, comme les processeurs x86, utilisent le registre d'état pour mémoriser l’occurrence d'un débordement. Si une opération entraine un débordement, un bit dédié du registre d'état est mis à 1. Mais ce bit n'est pas accessible depuis les langages de programmation de haut niveau, et des solutions logicielles de détection des débordements doivent être utilisées si besoin. Dans ce qui va suivre, nous allons voir comment détecter ces débordements avec des opérations bit à bit et des comparaisons.

Avant toute chose, il faut considérer la taille des opérandes en nombre de bits. Quand les opérandes ne sont pas du même type, le compilateur convertira généralement tous les opérandes vers le type ayant le plus grand nombre de bits. Si certains langages n'ont pas ce comportement, il faudra explicitement ajouter cette conversion. Les sections suivantes partent du principe que cette conversion a déjà eu lieu et que les opérandes ont tous le même nombre de bits. Le nombre de bits à considérer étant le plus grand parmi les opérandes, ou celui du type utilisé dans une conversion explicite.

Les débordements peuvent avoir lieu autant avec des nombres signés que non-signés. Nous allons commencer par voir les opérations sur des nombres non-signés, qui sont nettement plus simples.

Les débordements lors des opérations non-signées

Les débordements sur les opérations non-signées sont plus simples à comprendre que les débordements lors d'opérations non-signées. Nous allons supposer que les débordements d'entier sont tous gérés de la même manière : si le résultat d'une opération déborde, le processeur conserve les bits de poids faible du résultat et ne calcule pas les bits de poids fort.

L'addition et la soustraction

Pour l'addition de deux nombres notés X et Y, un débordement fait que la somme X + Y est systématiquement inférieure à la fois à X et à Y. On a donc :

$(X+Y<X)|(X+Y<Y)$

Le truc, c'est qu'une seule condition suffit, l'une entrainant naturellement l'autre, ce qui donne : $X+Y<X$. En simplifiant, via les règles d'utilisation des opérations logiques lors des comparaisons, on trouve :

${\overline {X}}<Y$

Les conditions précédentes peuvent s'adapter pour la soustraction, en tenant compte de l'équation $-y={\overline {y-1}}$. Cette fois-ci, on sait qu'il y a débordement si : $X-Y>X$. Ce qui donne :

$X<Y$

La multiplication

Le cas de la multiplication et de la division sont assez différents de l'addition/soustraction. Le cas de la division est cependant le plus simple : le diviseur et le reste étant inférieurs par définition au diviseur, il ne peut pas y avoir de débordements d'entiers lors d'une division entière. Mais c'est très loin d'être le cas pour la multiplication. En effet, la multiplication de deux opérandes de $n$ bits donne un résultat de $n\times 2$. Le résultat d'une multiplication ne tient donc pas dans un registre. En général, le processeur gère cela soit en ne conservant que les bits de poids faible. Dans ces conditions, il existe plusieurs moyens pour détecter un débordement.

La première méthode commence par faire la multiplication $x\times y$, avant de vérifier que l'on obtient bien $x$ en divisant le résultat par $y$. Si on obtient le bon résultat, alors il n'y a pas eu débordement. Mais en cas de débordement, les bits perdus faussent le résultat de la division et on ne retrouve pas l'opérande initiale. Cette méthode donne le bon résultat à une exception près : le cas où l'une des opérandes est nulle, qui entraine une division par zéro.

Il est possible d'améliorer la méthode précédente de manière à ne pas avoir à faire la multiplication $x\times y$. Il suffit d'appliquer la formule suivante, dans laquelle $I_{max}$ est le plus grand entier codable en complément à deux. On voit que cette formule vérifie deux conditions. La première condition est le diviseur n'est pas nul. La deuxième condition est celle qui vérifie s'il y a possibilité de débordement compte tenu des opérandes. Dans la formule, la division $I_{max}/y$ donne, par définition, le plus grand entier tel qu'il n'y a pas de débordement si on le multiplie par Y. Il suffit alors de comparer ce nombre au multiplicande : il y a débordement si le multiplicande est supérieur, pas de débordement sinon.

$(y\neq 0).(x>I_{max}/y)$

Une autre solution se base sur le fait que le produit de deux opérandes de a et b bits donne un résultat de a + b bits. Si les registres du processeur sont de n bits, alors on a un débordement si a + b > n. L'idée est alors de déterminer quel est le nombre de bits de chaque opérande avec l'opération Count Leading Zero. Celle-ci renvoie naturellement n - a et n - b quand on l'applique sur les opérandes. En additionnant ces deux valeurs, on a : $2n-(a+b)$. On a alors : $a+b=2n-\left(clz(a)+clz(b)\right)$. En couplant avec la condition a + b < n, on obtient l'inégalité suivante s'il n'y a pas de débordement :

$n\leq clz(a)+clz(b)$

Les débordements lors des opérations signées

Passons maintenant aux opérations sur les nombres signés. Là encore, nous verrons les additions/soustractions, avant de passer aux multiplications et aux divisions. Vous noterez la présence des divisions dans cette section, les divisions signées pouvant déborder.

L'addition et la soustraction

D'après les règles du complément à deux, on sait que le bit de poids fort (le plus à gauche) permet de déterminer si le nombre est positif ou négatif : il indique le signe du nombre. Tout se passe comme si les entiers en complément à deux étaient codés sur un bit de moins, et avaient leur longueur amputé du bit de poids fort. Si le résultat d'un calcul a besoin d'un bit de plus que cette longueur, amputée du bit de poids fort, le bit de poids fort sera écrasé; donnant un débordements d'entiers. Il existe une règle simple qui permet de détecter ces débordements d'entiers. L'addition (ou la multiplication) de deux nombres positifs ne peut pas être un nombre négatif : on additionne deux nombres dont le bit de signe est à 0 et que le bit de signe du résultat est à 1, on est certain d'être en face d'un débordements d'entiers. Même chose pour deux nombres négatif : le résultat de l'addition ne peut pas être positif. On peut résumer cela en une phrase : si deux nombres de même signe sont ajoutés, un débordement a lieu quand le bit du signe du résultat a le signe opposé. On peut préciser que cette règle s'applique aussi pour les nombres codés en complément à 1, pour les mêmes raisons que pour le codage en complément à deux. Cette règle est aussi valable pour d'autres opérations, comme les multiplications.

La division

La première possibilité de débordement correspond à une division par zéro, quand $(Y=0)$. Le second cas correspond au cas où l'on divise le plus petit entier par -1. Pour comprendre pourquoi, rappelons la règle suivante : $-y={\overline {y}}+1$. Notons maintenant le plus petit et le plus grand entier codable en complément à deux : $I_{min}$ et $I_{max}$. On a alors :

$I_{min}=-I_{max}-1$

On en déduit l'inégalité suivante :

$I_{min}<-I_{max}$

Divisons ensuite par -1, ce qui revient à prendre l'opposé du nombre ainsi divisé. L'inégalité s'inverse, ce qui donne :

${\frac {I_{min}}{-1}}>{\frac {I_{max}}{-1}}$

Cette inégalité est conservée si l'on prend les valeurs absolues :

$|{\frac {I_{min}}{-1}}|>|I_{max}|$

Pour résumer, un débordement a lieu lors d'une divisions non-signée X / Y quand :

$(Y=0)|\left[(x=0b100000...00000).(Y=-1)\right]$

Cette expression peut se reformuler de plusieurs manières, qui sont listées ci-dessous.

$abs(Y\oplus 0b100000...00000)|\left[(abs(x).abs(y=0b100000...00000)\right]$

$nabs(Y)|nabs((x\oplus 0b100000...00000)|(Y+1))\geq 0$

Les débordements de puissance de deux

Comme vous le savez peut-être, certaines architectures demandent aux accès mémoire de respecter des contraintes d'alignement. Pour rappel, la mémoire est alors découpée en blocs dont la taille est égale à la largeur du bus de données. Quand on accède à une donnée, il est préférable que celle-ci soit intégralement contenue dans un bloc : l'accès mémoire est alors dit aligné. Mais si la donnée est à cheval sur deux blocs, l'accès mémoire est dit non-aligné et cela peut poser problème. Si certaines architectures gèrent parfaitement les accès non-alignés, d'autres ne permettent pas de tels accès. Pour diverses raisons, il est possible pour un programmeur de détecter si un accès mémoire sera ou non aligné.

Un problème similaire apparait lorsque l'on doit charger une donnée depuis la mémoire RAM, sur les systèmes à mémoire virtuelle. Cette fois-ci, la mémoire virtuelle divise la RAM en pages, les données pouvant être à cheval sur deux pages. Détecter de tels chevauchements est alors une nécessité pour le système d’exploitation. Il se trouve qu'aussi bien la taille des pages que la largeur des blocs de RAM alignés sont des puissances de deux.

Gérer les accès non-alignés demande donc de détecter quand une donnée est à cheval entre deux blocs. Détecter les accès non-alignés est primordial et, fort heureusement, se fait avec quelques calculs particulièrement simples. Pour cela, il existe plusieurs solutions différentes.

La méthode avec des divisions

L'adresse $A$ peut se calculer à partir d'autres paramètres, comme la taille des blocs. Déjà, il faut savoir que chaque bloc a une taille qui s'exprime en bytes. Avec un système d'alignement ou de page, chaque bloc est numéroté en partant de zéro, ce numéro étant l'équivalent de l'adresse pour les bytes. L'adresse d'un bloc est par convention l'adresse du premier byte du bloc, celui dont l'adresse est la plus basse. Elle se calcule donc en multipliant le numéro du bloc par sa taille. Une donnée à l'intérieur d'un bloc est généralement localisée à une certaine distance de l'adresse de base, elle est placée quelques bytes plus loin que la base du bloc. Dit autrement, l'adresse $A$ d'une donnée s'écrit comme suit :

$A=N\times T+P$, avec $T$ la taille d'un bloc, $N$ le numéro du bloc et $P$ la position de la donnée par rapport à l'adresse de base du bloc.

Pages et blocs ont une taille qui est presque toujours une puissance de deux, ce qui est une norme tacite. Ce qui fait que l'on a :

$A=N\times 2^{n}+P$

L'adresse de $A+L$ s'écrit de la même manière, sauf que le numéro du bloc et la position dans le bloc sont potentiellement différents.

Notons que l'on peut trouver N et P à partir de A assez simplement. Il suffit en effet de diviser A par $2^{n}$ : N sera alors le quotient et P sera le reste de la division. Et c'est très utile pour détecter un accès non-aligné. Il suffit de diviser $A$ et $A+L$ par $2^{n}$, et de comparer les numéro de bloc obtenus. Si les deux numéros de bloc sont identiques, cela signifie que la donnée est toute entière dans le même bloc. Par contre, si les deux sont différents, cela signifie que le début de la donnée à l'adresse $A$ est dans un bloc, mais que la fin de la donnée $A+L$ est dans un autre bloc : il y a donc débordement.

Notons que faire la division en question demande juste de faire un décalage vers la droite, du moins sous condition que la taille du bloc soit une puissance de deux. C'est d'ailleurs une des raisons pour lesquelles les blocs/pages ont une taille égale à une puissance de deux. Faire ainsi simplifie de nombreux calculs d'adresse et permet des simplifications assez utiles.

La méthode avec le modulo

Il existe une seconde méthode qui une logique très simple. La donnée à charger commence à une adresse que nous noterons $A$ et a une longueur $L$. Un débordement de page/bloc a lieu quand il existe un multiple de $2^{n}$ entre $A$ et $A+L$. Cela traduit le fait que la donnée commence dans un premier bloc, atteint la limite du bloc (donc, une adresse multiple de $2^{n}$) et se poursuit au-delà. Reste à voir comment les opérations bit à bit nous aident pour détecter une telle situation.

Rappelons que l'on a :

$A=N\times 2^{n}+P_{0}$

Un débordement a lieu si, en ajoutant $L$, on passe au multiple de $2^{n}$ suivant. En clair, un débordement a lieu si :

$A+L=(N+1)\times 2^{n}+P_{1}$, avec $P_{1}\geq 0$

Soustrayons la première équation de la seconde :

$(A+L)-A=\left[(N+1)\times 2^{n}+r_{2}\right]-\left[N\times 2^{n}+P_{0}\right]$

Réorganisons les termes :

$L=\left[(N+1)\times 2^{n}-N\times 2^{n}\right]+\left[P_{1}-P_{0}\right]$

Simplifions :

$L=2^{n}+P_{1}-P_{0}$

Ajoutons $r_{0}$ des deux cotés :

$L+P_{0}=2^{n}+P_{1}$, avec, rappelons-le, $r_{2}\geq 0$

Pour le reformuler, le débordement implique que $P_{1}\geq 0$, ce qui implique que l'équation précédente est équivalente à l'inégalité suivante :

$L+P_{0}>2^{n}$

L'équation précédente dit que si la longueur dépasse ce qu'il manque à l'adresse pour atteindre le prochain multiple de $2^{n}$, alors c'est un débordement.

Sachant que le reste vaut par définition $P_{0}=A\mod 2^{n}$, on a :

$(A\mod 2^{n})+L\geq 2^{n}$

La méthode avec débordement d'entier

Une seconde méthode effectue un calcul similaire, si ce n'est que la comparaison est remplacée par un débordement d'entier. Le principe est très simple et se contente de remplacer l'adresse par le multiple de $2^{n}$ le plus grand possible qui soit adressable. Prenons par exemple une mémoire de 2^32 adresses, adressée par des adresses de 32 bits, découpée en page de 4096 octets. On suppose aussi que la machine travaille sur les mots/registres de 32 bits, comme les adresses. Sur 32 bits, l'adresse la plus grande qui soit multiple de 4096 est de 4294963200. Si à cette adresse on ajoute $L+A\mod 2^{n}$, un débordement se produit si $L+A\%2^{n}>4096$. En clair, le débordement d'entier traduit un débordement de page. On détecte donc un débordement de page si :

$4294963200+L+(A\%4096)>2^{32}$

Il se trouve que le calcul de $4294963200+(A\%4096)$ peut se réaliser sans faire l'addition. En effet, 4294963200 a déjà ses 12 bits de poids faible à 0. Tout ce qu'il faut faire est de remplacer les bits de poids forts de l'adresse par des 1, sans toucher aux bits sélectionnés par le modulo. L'application d'un masque est alors obligatoire, ce qui donne le code suivant :

$(A|4294963200)+L>2^{32}$

Ou encore :

$(A|-4096)+L>2^{32}$

On peut bien sûr généraliser les résultats précédents à toute autre valeur. Pour des adresses de $n$ bits et des pages/blocs de $m$ octets, on a :

$(A|-m)+L>2^{n}$

Les subtilités du XOR

Dans cette partie, nous allons voir ce qu'il est possible de faire avec l'instruction XOR. Faire un XOR entre deux nombres permet de faire pas mal de choses : émuler certaines instructions, échanger deux variables, fabriquer des listes chainées et j'en passe. Les techniques que nous allons voir se basent sur les propriétés de l'opération XOR. Pour rappel, nous avons vu au premier chapitre que : $a\oplus 0=a$ et $a\oplus a=0$. Ces deux propriétés sont assez importantes, surtout la dernière.

La mise à zéro rapide d'une variable ou d'un registre

Initialiser une variable à 0 est une opération extrêmement courante. En conséquence, il vaut mieux la rendre la plus rapide possible. Et il existe plusieurs méthodes pour mettre un registre à 0 en assembleur, certaines n'étant compatibles qu'avec certains processeurs. Certains processeurs ont une instruction dédiée pour mettre à 0 un registre : c'est alors la solution idéale dans la (quasi-)totalité des cas. Sur les processeurs qui n'ont pas cette instruction, on peut utiliser une instruction MOV (ou équivalent) pour mettre un 0 dans le registre. Mais il existe une dernière solution : faire un XOR entre le registre et lui-même.

Pour comprendre pourquoi cette solution fonctionne, il faut rappeler que l'on obtient 0 lorsque l'on XOR un bit avec lui-même : $a\oplus a=0$. 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.

L'utilisation d'une opération XOR peut utiliser moins de cycles d'horloge et/ou économiser de la mémoire (encodage plus court). Si c'est le cas, elle est utilisée par les compilateurs pour mettre à zéro un registre. C'est notamment ce qui est fait sur les architectures x86, sur lesquelles cette solution est légèrement meilleure que celle utilisant un MOV. Sur ces architectures, il faut utiliser MOV en adressage immédiat, c'est à dire que la constante à mettre dans le registre est stockée dans l'instruction elle-même. Et cette constante prend facilement 8 à 16 bits, ce qui fait qu' l'instruction MOV est assez longue avec ce mode d'adressage. En comparaison, le XOR entre deux registre est très court car il suffit de préciser l'opcode et deux noms de registre eux-mêmes très courts (quelques bits). 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.

L'émulation de l'instruction MOV

L'instruction XOR permet d'émuler des opérations plus complexes, dont des transferts entre registres/variables. Elle permet notamment 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

Les listes chainées XOR

La propriété $a\oplus a=0$ est aussi utilisée pour créer des listes doublement chainées plus économes en mémoire que la normale, appelées listes liées par ou exclusif, ou encore listes à chaînage 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.

Liste doublement chainée normale.

Les listes liées par ou exclusif (XOR linked lists) remplacent les deux pointeurs par un seul entier, qui contient le XOR entre ces deux pointeurs. Ainsi, on gagne un petit peu de mémoire : au lieu de stocker deux adresses, on n'en stocke plus qu'une. La consommation mémoire est identique à celle d'une liste simplement chainée.

Liste chainée XOR.

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 : $Ptr=P\oplus S$.

Parcourir une liste liée par ou exclusif

Traverser une liste à chaînage XOR ne se fait que dans un sens : soit on part du début pour arriver à la fin, soit on va dans l'autre sens.

Le parcours commençant par le début de la liste vers la fin de celle-ci s'effectue en gardant deux pointeurs. 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, on a :

$P\oplus Ptr=P\oplus (P\oplus S)=S$.

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 effectuer un ou exclusif entre le pointeur de l’élément précédemment visité et le pointeur stocké dans le nœud.

Il existe des listes à chaînage XOR qui permettent le parcours dans les deux sens. De telles listes doivent maintenir un pointeur vers le premier élément et un pointeur vers le dernier. Quand la liste est vide, les deux pointeurs valent NULL / NIL (adresse 0). Quand la liste ne contient qu'un élément, les deux pointeurs pointent le même élément.

Algorithme de parcours des éléments d'une liste du début vers la fin :

prev = 0
pelem = list.first
// ... traiter l'élément pointé par pelem ...

// Élément suivant
p = pelem
pelem = prev ^ list.ptr
prev = p
// si pelem == 0 alors le parcours est terminé

Algorithme de parcours des éléments d'une liste de la fin vers le début :

next = 0
pelem = list.last
// ... traiter l'élément pointé par pelem ...

// Élément précédent
p = pelem
pelem = next ^ list.ptr
next = p
// si pelem == 0 alors le parcours est terminé

Les 2 différences entre les 2 parcours sont le nom de la variable (prev / next) stockant l'ancienne valeur du pointeur pelem, et l'initialisation de ce pointeur (list.first / list.last).

Les avantages et inconvénients des listes chaînées liées par ou exclusif

Les listes à chaînage XOR ne sont pas une structure de données sans inconvénients.

Le premier inconvénient est le fait que l'on doive parcourir la liste à chaînage XOR du début à la fin. Impossible de revenir en arrière pendant le parcours de la liste chaînée, à moins d'utiliser une variable supplémentaire. Certes, revenir en arrière de cette manière est assez rare, mais cela peut avoir son utilité.

Ensuite, les insertions et retraits demandent de parcourir toute la liste, sauf dans quelques cas assez rares, contrairement à ce qu'on a avec les listes doublement chainées. Par exemple, il est impossible de retirer un élément de la liste si on ne connaît que son adresse. Il est aussi impossible d'insérer un élément avant/après un élément repère si on ne connaît que l'adresse du dit repère. Les 2 inconvénients sur le parcours en sens inverse et la modification à partir d'un pointeur sont résolus en utilisant deux pointeurs : un sur l'élément et un autre sur le suivant ou le précédent de l'élément pointé.

Enfin, de telles listes marchent assez mal avec les algorithmes de ramasse-miettes (garbage collection). Avec l'usage d'un ramasse-miette, la libération de la mémoire inutilisée est automatique. Les algorithmes de libération de la mémoire inutilisée se basent cependant sur l'usage de pointeurs. Pour être précis, ils analysent les données accessibles via les pointeurs d'un programmes pour déterminer la mémoire utile de la mémoire libre. Si les pointeurs sont cachées, comme dans les listes à chaînage XOR, les algorithmes ne peuvent pas les reconnaître et donnent un résultat sous-optimal. La libération de la mémoire se fait moins bien, ce qui peut poser quelques problèmes. Ironiquement, cela peut augmenter la consommation mémoire alors que le but du chaînage XOR est justement de la réduire. Cependant les langages à ramasse-miette n'autorisent pas les pointeurs, car le langage les gère. Il n'est donc pas possible d'implémenter de telles listes dans ces langages. Par contre, le problème peut se poser si un ramasse-miette est utilisé dans un langage qui n'en utilise pas nativement. En effet, il existe des librairies qui permettent d'ajouter un ramasse-miette dans des programmes codés en C ou en C++, un bon exemple étant le Boehm garbage collector. L'usage d'une liste à chaînage XOR avec de telles librairies peut éventuellement poser quelques problèmes.

Ces inconvénients sont à comparer avec les avantages promis pour cette structure de données. L'avantage principal d'une liste à chaînage XOR est évidemment la consommation de mémoire équivalente à celle d'une liste chaînée simple. Le gain et surtout sensible sur les longues listes chaînées, sur les machines où les pointeurs sont longs, et où chaque élément a une petite taille. Plus les éléments de la liste sont gros, moins l'économie est importante, rapportée au poids total de la liste chaînée. De plus, il existe d'autres solutions pour économiser de la mémoire avec les listes chaînées, comme les listes chaînées déroulées (unrolled linked lists). Tout cela expliquer que le chaînage XOR est actuellement peu, voire pas du tout, utilisé sur les machines modernes. Il peut éventuellement être utile sur quelques machines embarquées très peu puissantes, et encore !

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

La première méthode alternative qui utilise des additions et soustractions. Il faut effectuer ces opérations dans l'ordre suivant :

• $A=A-B$ ;
• $B=A+B$;
• $A=B-A$.

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

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 :

• $A=A\oplus B$ ;
• $B=A\oplus B$;
• $A=A\oplus B$.

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

Le fonctionnement de cette méthode se base sur le fait que $(x\oplus y)\oplus y=x$. Faites les calculs vous-même : $(x\oplus y)\oplus y=x\oplus (y\oplus y)=x\oplus 0=x$. 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\oplus B$	B
Seconde étape	$A\oplus B$	$(A\oplus B)\oplus B$
Troisième étape	$((A\oplus B)\oplus B)\oplus (A\oplus B)$	$(A\oplus B)\oplus B$

Vu que XOR est associatif, commutatif, distributif, on peut alors supprimer les parenthèses. Les identités $a\oplus a=0$ et $a\oplus 0=a$ 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	$A\oplus B$	B
Seconde étape	$A\oplus B$	$(A\oplus B)\oplus B$
Troisième étape	$((A\oplus B)\oplus B)\oplus (A\oplus B)$	$(A\oplus B)\oplus B$

Ce qui se simplifie en :

Étape	Variable A	Variable B
Avant l'opération	A	B
Première étape	$A\oplus B$	B
Seconde étape	$A\oplus B$	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 ;
}

GFDL

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans texte de dernière page de couverture.