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