Les opérations bit à bit/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$