Nombres entiers relatifs

Les entiers naturels

Pour représenter et stocker en mémoire des entiers naturels (c'est-à-dire des nombres entiers positifs ou nuls), il suffit d'utiliser leur représentation binaire (en base 2). Vous pouvez trouver des informations supplémentaires sur cette page. Un entier naturel (on dit aussi un entier non signé) va être codé avec un certain nombre de bits : 8, 16, 32, ... Le nombre de bits va définir la valeur maximale de l'entier que l'on peut stocker. Par exemple, sur un octet (8 bits), on peut stocker 2⁸ = 256 valeurs différentes. Sur 16 bits, on peut stocker 2¹⁶ = 65536 valeurs différentes. On peut donc compter de 0 à 65535 (2¹⁶ - 1). En règle générale, avec n bits, on peut stocker 2ⁿ valeurs, et donc compter de 0 à 2ⁿ - 1. Exemples :

• 52, codé sur 8 bits : 0011 0100
• 255, codé sur 8 bits : 1111 1111
• 52000, codé sur 16 bits : 1100 1011 0010 0000
• 65535, codé sur 16 bits : 1111 1111 1111 1111
• 0, codé sur 8 bits : 0000 0000

On remarque que pour un nombre donné de bits, la valeur maximale s'obtient en mettant tous les bits à la valeur 1. La valeur 0 s'obtient quand tous les bits sont à 0.

Les entiers relatifs

Les entiers relatifs sont des nombres entiers qui peuvent être positifs, négatifs ou nuls. On les appelle aussi des entiers signés. Le signe d'un nombre peut être + ou -. Il n'y a donc que deux possibilités. Une idée serait donc de réserver l'un des bits de ce nombre pour indiquer son signe. On parlera de bit de signe.

1ère méthode :

On peut prendre par exemple le bit se situant le plus à gauche (le bit le plus significatif) et utiliser la convention suivante. Si le bit vaut 0, le nombre est positif, si le bit vaut 1, le nombre est négatif.

Prenons un exemple sur 8 bits : Soit le nombre binaire suivant : 1011 0110. Le bit le plus à gauche est 1, le nombre est donc négatif. Pour avoir sa valeur, on prend les 7 bits restants : 011 0110. Ce nombre binaire correspond au nombre décimal 54. Le nombre binaire signé sur 8 bits 1011 0110 correspond donc à la valeur décimale -54.

Avec ce système, le nombre positif le plus grand est : 0111 1111, c'est-à-dire +127. Le nombre négatif le plus petit est : 1111 1111, c'est-à-dire -127. On peut compter moins loin qu'avec les entiers non signés, et c'est normal car nous avons perdu un bit pour représenter le signe.

Cette représentation pose deux problèmes importants :

• Sur 8 bits et avec ce système, la représentation du nombre entier +1 est : 0000 0001 et la représentation du nombre entier -1 est : 1000 0001. Or (+1) + (-1) = 0, mais si on additionne les deux nombres binaires 0000 0001 et 1000 0001, on obtient 1000 0010, qui correspond à (-2). Avec notre système, (+1) + (-1) = (-2), ce qui est loin d'être satisfaisant !
• Un autre soucis est que nous avons deux possibilités pour représenter le zéro : 0000 0000 (+0) et 1000 0000 (-0). Le fait d'avoir deux représentations pour un même nombre n'est pas satisfaisante.

Pour résoudre ce problème, on va essayer une autre méthode.

2ème méthode :

On va illustrer cette méthode par un exemple sur un nombre codé sur 8 bits.

Soit le nombre décimal 104. Sa représentation binaire sur 8 bits est 0110 1000. On va maintenant calculer le complément à deux de ce nombre binaire. Pour cela on commence d'abord par inverser la valeurs de tous les bits : les 0 deviennent des 1, et les 1 deviennent des 0. On obtient donc le nombre binaire suivant : 1001 0111. On ajoute ensuite 1 à ce résultat. On obtient alors : 1001 1000. On a donc : 1001 1000 est le complément à deux de : 0110 1000. Ce nombre est aussi la représentation binaire sur 8 bits de -154.

On remarque que comme dans la première méthode, le bit le plus à gauche sera toujours à 1 pour un nombre négatif : il sert donc de bit de signe. Par contre les deux problèmes que nous avions soulevé sont résolus :

• Avec ce système, la représentation de (+1) sur 8 bits est : 0000 0001. La représentation de (-1) sur 8 bits est le complément à deux de ce nombre. On commence par inverser tous les bits, et on obtient : 1111 1110. Puis on ajoute 1, pour obtenir 1111 1111. La représentation binaire de (-1) est donc 1111 1111. Si on ajoute ces deux nombres binaires, on obtient un nombre à 9 bits, à cause de la dernière retenue : 1 0000 0000. Comme l'ordinateur ne conserve que 8 bits pour représenter le nombre, le neuvième bit tout à fait à gauche est perdu, et le résultat de l'opération est 0000 0000, qui est le résultat correct pour (+1) + (-1).
• Avec ce système, (+0) a pour représentation 0000 0000. Pour calculer la représentation de (-0), on va prendre le complément à 2 : on inverse tous les bits, et on obtient : 1111 1111. On ajoute 1, et on obtient : 1 0000 0000, c'est-à-dire 0000 0000 car le neuvième bit est perdu. Il n'y a donc qu'une seule représentation binaire pour le zéro.

Avec cette méthode, l'entier positif le plus grand codé sur 8 bits est : 0111 1111, c'est-à-dire +127, et l'entier négatif le plus petit est : 1000 0000, c'est-à-dire -128.

Dépassement de capacité

Le fait que les entiers relatifs soient codés sur un nombre donnés de bits peut poser des problèmes. Par exemple, 42 + 90 = 132, nombre que=i est supérieur à 127, et donc qui ne peut pas être codé sur 8 bits. Regardons ce qu'il se passe lorsque nous faisons l'opération en binaire. La représentation binaire de 42 est : 0010 1010, et celle de 90 est : 0101 1010. La somme de ces deux nombres binaires est : 1000 0100. Le fait que le bit le plus à gauche soit égal à un nous dit que ce nombre est négatif. Pour obtenir sa valeur, il nous allons appliquer la méthode de conversion à l'envers : on enlève 1, pour obtenir 1000 0011. Puis on inverse les bits, et on obtient : 0111 1100, ce qui est la représentation binaire de 124. Le résultat de notre calcul est donc : 42 + 90 = -124 ! Dès que le résultat d'un calcul sortira de l'intervalle permis, ce phénomène se produira, entrainant des erreurs de calcul. Loin d'être anecdotique, ce problème peut avoir des conséquences très fâcheuses : voir à cet effet le bug le plus coûteux de l'histoire.

Codage des entiers en Python

Contrairement à d'autres langages, comme le C par exemple, qui code les entiers sur un nombre de bits fixé, Python, à partir de sa version 3, peut gérer des entiers aussi grand que possible. Leur représentation binaire va avoir un nombre de bits variable, et n'est théoriquement limitée que par la taille mémoire. On pourra s'en rendre compte en essayant l'exemple suivant dans la console Python :

>>> 2 ** 4096
1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595674492194617023806505913245610825731835380087608622102834270197698202313169017678006675195485079921636419370285375124784014907159135459982790513399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412945674919823050571642377154816321380631045902916136926708342856440730447899971901781465763473223850267253059899795996090799469201774624817718449867455659250178329070473119433165550807568221846571746373296884912819520317457002440926616910874148385078411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190336

Vous pourrez essayer d'autres calculs, et vous apercevoir que vous pouvez travailler avec des entiers vraiment très grands, sans aucune perte de précision. La bonne nouvelle, c'est que le problème de dépassement de capacité avec les entiers ne se produira pas en Python !