Nombres entiers relatifs
Précédemment, nous avons vu que nous pouvions coder l'ensemble des entiers naturels sans limitation, à condition d'ajouter suffisamment de bits.
À présent, trouvons une méthode qui va nous permettre de coder les entiers relatifs (positifs et négatifs).
Proposition naïve
L'idée immédiate, mais naïve1 consiste à consacrer le bit de poids fort (celui le plus à gauche) comme bit de signe :
- 0 pour les nombres positifs,
- 1 pour les négatifs.
Avec 9 bits, par exemple, on représente les entiers compris entre -255 et +255. Mais le nombre 0 est représenté deux fois, 0 0000 0000 (+0) et 1 0000 0000 (-0) et surtout la somme de deux nombres opposés n'est pas nulle, ce qui est gênant.
Ainsi, si on effectue \(214 + (-214)\), on obtient :
| bit de report | bit de signe | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 214 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | |
| -214 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | |
| Somme | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
Nous sommes devant 2 problèmes :
- on a un bit de report sur un 10ème bit...
- le résultat de cette somme est non nul, ce qui est inacceptable sur un plan mathématique !
Ainsi, il faut donc trouver une autre méthode...
Méthode du complément à 2
Pour résoudre le problème, on définit le complément à 2 d'un entier positif qui représente son opposé, de manière que la somme de deux entiers opposés soit bien égale à 0.
Pour obtenir le complément à 2, il suffit de retenir la recette qui est très simple et qui se déroule en deux étapes vraiment élémentaires :
Complément à 2
La première étape consiste à complémenter chaque bit du nombre entier positif, auquel on a ajouté le bit de signe à 0 comme dans la méthode naïve : cela signifie qu'un bit à 0 passe à 1 et un bit à 1 passe à 0. On obtient ainsi le complément à 1 :
| bit de signe | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | |
|---|---|---|---|---|---|---|---|---|---|
| +214 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| complément à 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
Puis, la seconde étape consiste à ajouter le nombre 1 au complément à 1 :
| bit de signe | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | |
|---|---|---|---|---|---|---|---|---|---|
| +214 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| complément à 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| +1 | 1 | ||||||||
| -214 complément à 2 |
1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
Si on somme à présent les deux entiers opposés, soit \(214 + (-214)\), on obtient :
| bit de report | bit de signe | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | |
|---|---|---|---|---|---|---|---|---|---|---|
| +214 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | |
| -214 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | |
| Somme | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Certes, il y a un dernier report qui passe dans un dixième bit, mais sur 9 bits, la somme de deux entiers opposés est bel et bien nulle.
-
En informatique, une solution naïve désigne une approche simple et directe pour résoudre un problème, généralement sans optimisation ni prise en compte des contraintes de performance. ↩