Complément à deux
Un article de Wikipédia, l'encyclopédie libre.
Le complément à deux est une représentation binaire des entiers relatifs qui permet d'effectuer les opérations arithmétiques usuelles naturellement.
| bit de signe | |||||||||
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | = | 127 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | = | 2 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | = | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | = | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | = | −1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | = | −2 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | = | −127 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | = | −128 |
Entier de 8 bits en complément à deux
[modifier] Explication
La notation est utilisée sur des écritures de nombres de longueur donnée (nombres écrits couramment sur 8, 16, 32 ou 64 bits). Dans une telle écriture on utilise le bit de poids fort (bit le plus à gauche) du nombre pour contenir la représentation de son signe (positif ou négatif, le zéro étant considéré comme positif).
La première idée est de marquer le signe du nombre de façon simple : le signe puis la représentation de sa valeur absolue. Ainsi :
v 00000010 = +2 en décimal
v 10000010 = (-2) en décimal
Malheureusement cette représentation possède deux inconvénients. Le premier (mineur) est que le nombre zéro (0) possède deux représentations: 00000000 et 10000000 sont respectivement égaux à 0 et -0. L'autre inconvénient (majeur) est que cette représentation n'est pas compatible avec l'addition; l'addition usuelle d'un nombre négatif et d'un nombre positif ne fonctionne pas. Ainsi:
00000011 + 10000100 = 10000111
Soit 3 + (-4) = (-7) au lieu de (-1)
C'est pour remédier à ces problèmes que l'on utilise la notation en complément à deux. Les nombres positifs sont représentés comme attendu; par contre les nombres négatifs sont obtenus de la manière suivante :
- On inverse les bits de l'écriture binaire de sa valeur absolue (opération binaire NOT), on fait ce qu'on appelle le complément à un,
- On ajoute 1 au résultat (les dépassements sont ignorés).
Cette opération correspond au calcul de 2n-|X|, où n est la longueur de la représentation. Ainsi -1 s'écrit comme 256-1=255=111111112, pour les nombres sur 8 bits.
Les deux inconvénients précédents disparaissent alors. En effet, l'opération précédente effectuée sur 00000000 permet d'obtenir 00000000 (-0=+0=0) et l'addition usuelle des nombres binaires fonctionne.
La même opération effectuée sur un nombre négatif donne le nombre positif de départ: 2n-(2n-x)=x.
Pour coder (-4) :
- On prend le nombre positif 4 : 00000100
- On inverse les bits : 11111011
- On ajoute 1 : 11111100
Le bit de signe est automatiquement mis à 1 par l'opération d'inversion. On peut vérifier que cette fois l'opération 3 + (-4) se fait sans erreur :
00000011 + 11111100 = 11111111
Le complément à deux de 11111111 est 00000001 soit 1 en décimal, donc 11111111 = (-1) en décimal.
Le résultat de l'addition usuelle de nombres représentés en complément à deux est le codage en complément à deux du résultat de l'addition des nombres. Ainsi les calculs peuvent-ils s'enchaîner naturellement.
[modifier] Explications plus détaillées
D'un point de vue plus technique, cette écriture est simplement la troncature de l'écriture infinie à gauche. Pour la base 10, on sait qu'il est sans effet de compléter un nombre par des zéros à sa gauche, i.e. 123 peut s'écrire 0000123 et même avec une infinité de 0, comme ...0123. Mais il est bien moins connu que si l'on permet de compléter à gauche avec une infinité de 9 on obtient une réprésentation des nombres négatifs! Par exemple :
...99 (infinité de 9 à gauche) + ...01 (infinité de 0 à gauche) ------- ...00 (infinité de 0 à gauche)
On peut alors interpréter ...99 comme étant -1, puisque -1+1=0.
Cette notation est le complément à 10. Pour obtenir la représentation d'un nombre négatif il faut complémenter à 9 chaque chiffre puis ajouter 1 au résultat. Ainsi pour obtenir la représentation de -123 on fait : ...0123 transformé en ...9876 puis en ...9877.
Un exemple plus complet. Essayons de calculer dans une telle représentation 12+(-7) 12 s'écrit ...012, -7 s'écrit (...07 complémenté en ...92 puis additionné de 1 donne ...93) ...93. Additionnons:
...012 + ....93 -------- ....05
Et chacun sait que 12+(-7)=12-7=5
Une telle écriture mais de taille fixe fonctionne car le chiffre le plus à gauche (le signe 0 pour le + et 9 pour le -) représente alors simplement l'infinité des chiffres à gauche (l'opération consistant à allonger à volonté l'écriture du nombre à gauche s'appelle l'extension du signe et est bien connue des informaticiens).
Le complément à deux est alors la même technique employée avec la base 2.
