Complément à deux

En informatique, le complément à deux, (in ext. complément à deux puissance n, n étant la taille du codage) est une méthode de représentation des entiers relatifs en binaire permettant d'effectuer les opérations arithmétiques usuelles en utilisant les mêmes circuits que pour les entiers naturels.

bit de signe 0 1 1 1 1 1 1 1 = 127 0 … = … 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 … = … 1 0 0 0 0 0 0 1 = −127 1 0 0 0 0 0 0 0 = −128 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 −2^n − 1 à 2^n − 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é. 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) permet de connaitre le signe du nombre représenté (positif ou nul, 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
0000 0010	+2 en décimal
1000 0010	−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 : 0000 0000 et 1000 0000, qui sont respectivement égales à +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	+ 0000 0011	+  3
+ 132	+ 1000 0100	+ -4
= 135	= 1000 0111	= -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 $-x$ sont obtenus en calculant l'opposé du nombre positif $x$, en utilisant le fait que $x+{\overline {x}}=111...1=-1$, soit $-x={\overline {x}}+1$, ce qui se traduit par les 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) (voir addition en binaire).

Cette opération, nommée complément à 2, est fondamentalement liée à la notation en complément à deux ; elle correspond au calcul de 2ⁿ − |x|, où n est la longueur de la représentation et |x| la valeur absolue du nombre à coder. Elle garantie que $x+(-x)=0$, qui vient de $x+(-x)=2^{n}$ comme $2^{n}\equiv 0$ sur n bits. Exemple, −1 s'écrit comme 256−1 = 255 = 1111 1111₂, pour les nombres sur 8 bits et on a bien 1+1111 1111₂=1 0000 0000₂=256=0 (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 » et également à l'origine du nom de la représentation en complément à 2 qui associe à un nombre son opposé pour passer des positifs aux négatifs et inversement, avec l'opposé obtenu comme le complément à $2^{n}$ ($\equiv 0$ sur n bits).

Les deux inconvénients précédents disparaissent alors. En effet, le calcul de l'opposé de 0000 0000 utilise le complément à 1 : 1111 1111 qui après ajout de 1 redevient 0000 0000. 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: 2ⁿ − (2ⁿ − x) = x.

Pour retrouver le codage binaire de (−4) :

• on prend le nombre positif 4 : 0000 0100 ;
• on inverse les bits : 1111 1011 ;
• on ajoute 1 : 1111 1100.

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	+ 0000 0011	+  3
+ 252	+ 1111 1100	+ −4
= 255	= 1111 1111	= −1	La même opération fonctionne pour les nombres négatifs et positifs

Le complément à deux de 1111 1111 est 0000 0001 soit 1 en décimal, donc 1111 1111 = (−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 : 0001 0100.
• On garde la partie à droite telle quelle : (0001 0100).
• On inverse la partie de gauche après le premier un : 1110 1100.
• Et voici −20 : 1110 1100.

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 2ⁿ.

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.

Remarque : ce nombre « spécial » correspond en fait à la plus petite valeur représentable pour un type signé, par exemple -128 sur 8 bits.

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 et le chiffre le plus à gauche donne le signe du nombre (le signe + pour 0, 1, 2, 3, 4 ; le signe - pour 5, 6, 7, 8, 9). Dans le cas où ce chiffre vaut 0 ou 9, il représente alors simplement l'infinité des chiffres à gauche. Lorsque ce chiffre est 1, 2, 3, ou 4, l'extension de la représentation pour passer à un format plus grand consiste à ajouter des 0. Lorsque ce chiffre est 5, 6, 7, 8, l'extension de la représentation pour passer à un format plus grand consiste à ajouter des 9. il n'y a pas d'extension par recopie du chiffre de signe comme en complément à 2, sauf pour 0 ou 9. Mais dans tous les cas, après extension à l'infini, on retrouve une infinité de 0 ou de 9 à gauche.

Le complément à deux est alors la même technique, plus simple, puisque réduite à 0 et 1, employée avec la base 2 au lieu de la base 10.

Voir aussi

Articles connexes

• Système binaire
• Complément à un
• Nombre p-adique