Complément à deux

Un article de Wikipédia, l'encyclopédie libre.
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.

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.

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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 − (2nx) = 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[modifier | modifier le code]

Pour une valeur, l'opposé n'est pas représentable.

Le complément à 2 de 1000 0000 se calcule en deux étapes :

  • complément à 1 : 0111 1111
  • puis incrément : 1000 0000

Ainsi, la complément à 2 de ce nombre est ce nombre à l'identique comme pour 0, alors que ce nombre n'est pas l'opposé de lui-même.

Analogie avec la base 10[modifier | modifier le code]

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.

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]