Chapitre 2: Représentation des entiers relatifs

Jusqu'à maintenant, nous avons appris à représenter des entiers naturels en représentation binaire ou hexadécimale.

Ainsi en utilisant des mots binaires de n bits, on peut coder $2^{n}$ nombres entiers.

Par exemple sur un octet, soit 8 bits, on peut coder $2^{n}$ valeurs soit dans le cas des entiers naturels des nombres de 0 à 255.

Cependant dans de nombreux programmes, il est nécessaire d'utiliser d'autres types de nombres comme les entiers relatifs ou les réels.

Méthode naïve: utilisation d'un bit de signe

La façon la plus simple de procéder serait de réserver le bit de poids fort pour le signe(0 pour positif et 1 pour négatif), et de garder le rester pour la représentation de la valeur absolue du nombre.

Avec un codage utilisant des mots de n bits, on pourrait représenter des nombres entre $-2^{n-1}+1$ et $2^{n-1}-1$.

Par exemple, avec un codage sur 3 bits, des nombres entre -3 et 3:

Malheureusement cette représentation possède deux inconvénients. Le premier (mineur) est que le nombre zéro (0) possède deux représentations. L'autre inconvénient (majeur) est que cette représentation impose de modifier l'algorithme d'addition ; si un des nombres est négatif, l'addition binaire usuelle donne un résultat incorrect. Voir l'article de Wikipedia pour plus de détails

Notation en complément à deux

Cette méthode permet de remédier aux problèmes évoqués ci-dessus.

On utilise toujours un bit de signe tout à gauche:

• les entiers positifs sont codés normalement,
• par contre on ajoute $2^n$ aux entiers négatifs.

Méthode d'encodage

L'entier négatif $x$ est codé comme s'il s'agissait de l'entier $x + 2^{n}$ ou n est la taille du mot.

Il est possible d'appliquer un algorithme simple pour réaliser cette addition en binaire (cette méthode sera désignée comme 2e méthode par la suite).

• On inverse les bits de l'écriture binaire de sa valeur absolue.
• On ajoute 1 au résultat (les dépassements sont ignorés).

Avec ce codage utilisant des mots de n bits, on pourrait représenter des nombres entre $-2^{n-1}$ et $2^{n-1}-1$.

Article Wikipedia sur le complément à deux

On peut alors vérifier avec cette notation que l'algorithme d'addition utilisé pour les entiers naturels donne des résultats corrects avec cette représentation(voir les exercices[./exo]).

Méthode de décodage

Pour connaitre le nombre que représente un entier négatif, on effectue la démarche inverse:

• On lui retranche 1 puis,
• on inverse tous ces bits,
• On convertit en base 10, et on ajoute le signe -.

Ce qui revient à lui soustraire $2^n$.