# Complément à deux

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 −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) 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, 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 | + 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) (voir addition en binaire).
Cette opération correspond au calcul de 2$^n$ − |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 = 11111111$_2$, 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: 2$^n$ − (2$^n$ − 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 2$^n$.

### 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 :
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 :
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.