Complément à deux - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

- Introduction - Explication - Explications plus détaillées

Introduction

Le complément à deux est une représentation binaire des entiers relatifs qui permet d'effectuer les opérations arithmétiques usuelles naturellement.

bit de signe
0	1	1	1	1	1	1	1	=	127
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	0	0	0	0	0	0	1	=	−127
1	0	0	0	0	0	0	0	=	−128

Entiers de 8 bits en complément à deux

Explication

La notation est utilisée sur des écritures de nombres de longueur donnée (nombres écrits couramment sur 8, 16, 32 ou 64 bits). Dans une telle écriture on utilise le bit de poids fort (bit le plus à gauche) du nombre pour contenir la représentation de son signe (positif ou négatif, le zéro étant considéré comme positif).

La première idée est de marquer le signe du nombre de façon simple : le signe puis la représentation de sa valeur absolue. Ainsi :

      v      00000010 = +2 en décimal

      v      10000010 = −2 en décimal

Malheureusement 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 n'est pas compatible avec l'addition ; l'addition usuelle d'un nombre négatif et d'un nombre positif ne fonctionne pas. 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 NOT), 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 2ⁿ−|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₂, pour les nombres sur 8 bits.

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: 2ⁿ − (2ⁿ−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-ils 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.