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.

Opérations non-signées

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.

Addition et soustraction

Quand la somme X + Y déborde, le processeur va conserver les bits de poids faible du résultat et ne calculera pas les bits de poids fort (ou alors, il les oubliera). Les conséquences sont différentes selon que les opérandes soient considérées comme signées ou non-signées. Dans le cas des nombres non-signés, un débordement fait que la somme X + Y n'est pas aussi grande que ce qu'elle devrait. On peut même dire que la somme X + Y est systématiquement inférieure à X et à Y. En effet, si la somme X + Y <= X, alors cela signifie que la valeur Y est plus grande que la valeur d'un registre, d'où paradoxe. 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$

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 d'une opérande de m bits par une autre opérande de n bits donne un résultat codé sur m + n bits. Vu que tous les processeurs utilisent des opérandes de même taille, on sait que la multiplication donnera un résultat de $n\times 2$ bits pour des registres de n bits. Le résultat va donc prendre deux registres.

Certains processeurs se contentent de garder les $n$ bits de poids faible, ce qui fait que les débordements sont monnaie courante. 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. Ceux-ci permettent de détecter facilement un débordement. Pour le cas d'une multiplication non-signée, le débordement se détecte facilement : il suffit de regarder les bits de poids fort du résultat. Si le registre pour les bits de poids fort est nul, cela signifie qu'il n'y a pas eu débordement. Il y a eu débordement s'il n'est pas nul.

Si le processeur se contente de garder les bits de poids faible du résultat, on peut quand même détecter les débordements. Pour cela, il suffit de faire la multiplication $x\times y$ et de faire l'opération inverse : 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 vont fausser le résultat de la division. En conséquence, la division ne redonnera 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 pose des problèmes lors de la division. Il est possible de détecter le débordement sans faire la multiplication $x\times y$, en utilisant la formule suivante. Dans cette formule, $I_{max}$ est le plus grand entier codable en complément à deux.

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

Une autre solution se base sur un raisonnement plus simple. On a dit plus haut que le produit de deux nombres 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 du nombre. Pour cela, on peut utiliser le nombre de zéros non-significatifs à gauche, obtenu 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)$

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.

Addition et 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.

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$