Complément à deux
En informatique, le complément à deux est une méthode de représentation des entiers relatifs en binaire permettant d'effectuer simplement des opérations arithmétiques.
Représentation en complément à deux sur 8 bits. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Le complément à deux ne s'applique qu'à des nombres ayant tous la même longueur : avec un codage sur n bits, cette méthode permet de représenter toutes les valeurs entières de −2n − 1 à 2n − 1 − 1.
Histoire
La méthode des compléments est utilisée depuis longtemps pour effectuer des soustractions dans les machines à additionner décimales et les calculateurs mécaniques. John von Neumann a suggéré l'utilisation de la représentation binaire par complément à deux dans son premier projet de rapport sur la proposition EDVAC de 1945 d'un ordinateur numérique électronique à programme enregistré[1]. L'EDSAC de 1949, qui s'est inspiré du premier projet, utilise la représentation par complément à deux des nombres binaires.
De nombreux premiers ordinateurs, dont le CDC 6600, le LINC, le PDP-1 et l'UNIVAC 1107, utilisent la notation en complément à un ; les descendants de l'UNIVAC 1107, les séries UNIVAC 1100/2200, ont continué à le faire. Les machines scientifiques des séries IBM 700/7000 utilisent la notation signe/magnitude, sauf pour les registres d'index qui sont en complément à deux. Les premiers ordinateurs commerciaux à complément à deux comprennent le PDP-5 de Digital Equipment Corporation et le PDP-6 de 1963. Le System/360, introduit en 1964 par IBM, alors l'acteur dominant de l'industrie informatique, a fait du complément à deux la représentation binaire la plus utilisée dans l'industrie informatique. Le premier mini-ordinateur, le PDP-8 introduit en 1965, utilise l'arithmétique du complément à deux, tout comme le Data General Nova de 1969, le PDP-11 de 1970 et presque tous les mini-ordinateurs et micro-ordinateurs ultérieurs.
Description
Le complément à deux opère toujours sur des nombres binaires ayant le même nombre de bits. Dans une telle écriture, le bit de poids fort (bit le plus à gauche) donne le signe du nombre représenté (positif ou strictement négatif). C'est le bit de signe.
Problème de la représentation naïve
Une représentation naïve pourrait utiliser ce bit de poids fort comme marqueur du signe, les autres bits donnant une valeur absolue :
Dans les exemples ci-après, le bit de signe est représenté en bleu ciel.
| Notation naïve | Décimal |
|---|---|
| 00000010 | +2 en décimal |
| 10000010 | −2 en décimal |
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 impose de modifier l'algorithme d'addition ; si un des nombres est négatif, l'addition binaire usuelle donne un résultat incorrect. Ainsi :
| Décimal non signés | Addition en notation naïve | Décimal | |
|---|---|---|---|
| +00 3 | + 00000011 | + 3 | |
| + 132 | + 10000100 | + -4 | |
| = 135 | = 10000111 | = -1 → -7 |
= −7 au lieu de (−1) |
Représentation des nombres en complément à 2
Pour remédier au problème posé par une représentation naïve, la notation en complément à deux est utilisée:
- Les nombres positifs sont représentés de manière usuelle.
- Les nombres négatifs sont obtenus en calculant l'opposé du nombre positif par deux opérations successives:
- On inverse les bits de l'écriture binaire (opération binaire NON), 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 et |x| la valeur absolue du nombre à coder. Ainsi, −1 s'écrit comme 256−1 = 255 = 111111112, pour les nombres sur 8 bits. Ceci est à l'origine du nom de cette opération : « complément à 2 puissance n », quasi-systématiquement tronqué en « complément à 2 ».
Les deux inconvénients précédents disparaissent alors. En effet, le calcul de l'opposé de 00000000 utilise le complément à 1: 11111111 qui après ajout de 1 redevient 00000000. De même, 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 retrouver le codage binaire de (−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 :
| Décimal non signés | Notation complément à 2 | Décimal signé | |
|---|---|---|---|
| +00 3 | + 00000011 | + 3 | |
| + 252 | + 11111100 | + −4 | |
| = 255 | = 11111111 | = −1 | La même opération fonctionne pour les nombres négatifs et positifs |
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 s'enchaîner naturellement.
Si l'on doit transformer un nombre en son complément à deux « de tête », un bon moyen est de garder tous les chiffres depuis la droite jusqu'au premier 1 (compris) puis d'inverser tous les suivants.
- Prenons par exemple le nombre 20 : 00010100.
- On garde la partie à droite telle quelle : (00010100).
- On inverse la partie de gauche après le premier un : 11101100.
- Et voici −20 : 11101100.
Les opérations d'addition, soustraction et multiplication en complément à deux sur n bits sont identiques à celles en interprétant la suite de bits comme étant un entier non signé, les valeurs étant considérées modulo 2n.
Cas particulier
Il existe une valeur représentable pour laquelle l'opposé n'est pas représentable. En effet, le complément à 2 de 1000 0000 se calcule en deux étapes :
- complément à 1 : 0111 1111
- puis incrément : 1000 0000
Ainsi, le complément à 2 de ce nombre est ce nombre lui-même, comme pour 0, alors que ce nombre n'est pas l'opposé de lui-même.
Analogie avec la base 10
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 0123, 00123, 000123, etc, avec une infinité de 0 à sa gauche.
De même, si on considère une infinité de 9 à gauche on obtient une représentation des nombres négatifs. Par exemple :
…9999 (infinité de 9 à gauche)
+ …0001 (infinité de 0 à gauche)
-------
…0000 (infinité de 0 à gauche)
On peut alors interpréter …9999 comme étant −1, puisque −1 (i.e. …9999) + 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
Or 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.