« Les opérations bit à bit/Les débordements d'entiers » : différence entre les versions
Contenu supprimé Contenu ajouté
mAucun résumé des modifications |
|||
Ligne 2 :
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==
===Addition et soustraction===▼
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.
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 :
: <math>( X + Y < X ) | ( X + Y < Y )</math>
Le truc, c'est qu'une seule condition suffit, l'une entrainant naturellement l'autre, ce qui donne : <math>X + Y < X</math>. En simplifiant, via les règles d'utilisation des opérations logiques lors des comparaisons, on trouve :
: <math>\overline{X} < Y</math>
Ligne 17 ⟶ 23 :
: <math>X < Y</math>
===
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 <math>n</math> bits donne un résultat de <math>n \times 2</math>. 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, mais il existe des processeurs qui permettent de récupérer les n bits de poids fort du résultat. Sur ces derniers, le débordement se détecte facilement : il suffit de regarder les bits de poids fort du résultat : pas de débordement s'ils sont nuls, débordement sinon.
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 <math>x \times y</math> et de faire l'opération inverse : vérifier que l'on obtient bien <math>x</math> en divisant le résultat par <math>y</math>. 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 <math>x \times y </math>, en utilisant la formule suivante. Dans cette formule, <math>I_{max}</math> est le plus grand entier codable en complément à deux.
Ligne 33 ⟶ 35 :
: <math>n \leq clz(a) + clz(b)</math>
==
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.
===
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 première possibilité de débordement correspond à une division par zéro, quand <math>( Y = 0 )</math>. Le second cas correspond au cas où l'on divise le plus petit entier par -1. Pour comprendre pourquoi, rappelons la règle suivante : <math>- y = \overline{y} + 1</math>. Notons maintenant le plus petit et le plus grand entier codable en complément à deux : <math>I_{min}</math> et <math>I_{max}</math>. On a alors :
| |||