Complément à deux

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Complément à 2)
Sauter à la navigation Sauter à la recherche
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 opération sur les nombres binaires qui permet d'effectuer simplement des opérations arithmériques sur les entiers relatifs.

Le complément à deux ne s'applique qu'à des nombres ayant tous la même longueur : codés sur N bits, les nombres binaires peuvent représenter les valeurs entières de −2N − 1 à 2N − 1 − 1.

Description[modifier | modifier le code]

Le complément à deux opère toujours sur des nombres binaires ayant le même nombre de bits (par commodité, celui-ci est généralement un multiple de 4). Dans une telle écriture, le bit de poids fort (bit le plus à gauche) donne le signe du nombre représenté (positif ou négatif). C'est l'Indicateur de signe (N).

Une représentation naïve pourrait utiliser ce bit de poids fort comme marqueur du signe, les autres bits donnant une valeur absolue :

v
00000010 = +2 en décimal
v
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 :

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, en revanche 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 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ù 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, 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 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.

Explications détaillées[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

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.

Voir aussi[modifier | modifier le code]