Complément à deux

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
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 décimales 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).

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]