Nombre entiers relatifs : Méthode du complément à 2
Précédemment, nous avons vu que nous pouvions coder l'ensemble des entiers naturels sans limitation, à condition d'ajouter des bits.
À présent, trouvons une méthode qui va nous permettre de coder les entier relatifs, positifs et négatifs
Proposition naïve
L'idée immédiate mais naïve consiste à consacrer le bit d'extrême 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 : 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 à ce 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 :
La première étape consiste à complémenter chaque bit du nombre entier positif avec son bit de signe à 0, 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 |
Simulation : Vérification de la somme nulle...
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 obtenu par la méthode du complément à 2 | 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.