Complément à un

Le complément à un d'un nombre binaire est la valeur obtenue en inversant (retournant) tous les bits de la représentation binaire du nombre. Le nom « complément à un » fait référence au fait qu'une telle valeur inversée, si elle était ajoutée à l'originale, produirait toujours un nombre « tout en un » (le terme « complément » fait référence à de telles paires de nombres inverses mutuellement additifs , ici par rapport à un nombre de base non nul). Cette opération mathématique intéresse principalement l' informatique , où elle a des effets variables selon la façon dont un ordinateur spécifique représente les nombres.

Un système de complément à un ou arithmétique de complément à un est un système dans lequel les nombres négatifs sont représentés par l'inverse des représentations binaires de leurs nombres positifs correspondants. Dans un tel système, un nombre est nié (converti de positif en négatif ou vice versa) en calculant son complément à un. Un système de numération en complément à un à N bits ne peut représenter que des entiers compris entre −(2 ^N−1 −1) et 2 ^N−1 −1 tandis que le complément à deux peut exprimer −2 ^N−1 à 2 ^N−1 −1. C'est l'une des trois représentations courantes des entiers négatifs dans les ordinateurs binaires , avec le complément à deux et la grandeur du signe .

Le système de numération binaire en complément à un est caractérisé par le fait que le complément binaire de toute valeur entière est l'inverse arithmétique de la valeur. Autrement dit, l'inversion de tous les bits d'un nombre (le complément logique) produit le même résultat que la soustraction de la valeur de 0.

De nombreux ordinateurs anciens, dont les UNIVAC 1101 , CDC 160 , CDC 6600 , LINC , PDP-1 et UNIVAC 1107 , utilisaient l'arithmétique en complément à un. Les successeurs du CDC 6600 ont continué à utiliser l'arithmétique en complément à un jusqu'à la fin des années 1980, et les descendants de l'UNIVAC 1107 (la série UNIVAC 1100/2200 ) le font toujours, mais la majorité des ordinateurs modernes utilisent le complément à deux .

Les nombres positifs sont le même système binaire simple utilisé par le complément à deux et la grandeur du signe. Les valeurs négatives sont le complément binaire de la valeur positive correspondante. La plus grande valeur positive est caractérisée par le bit de signe (de poids fort) désactivé (0) et tous les autres bits activés (1). La plus petite valeur négative est caractérisée par le bit de signe 1 et tous les autres bits 0. Le tableau ci-dessous montre toutes les valeurs possibles dans un système à quatre bits, de −7 à +7.

 + − 0 0000 1111 — Notez que +0 et −0 renvoient VRAI lorsqu'ils sont testés pour zéro 1 0001 1110 — et FAUX lorsqu'il est testé pour une valeur différente de zéro. 2 0010 1101 3 0011 1100 4 0100 1011 5 0101 1010 6 0110 1001 7 0111 1000 

L'addition de deux valeurs est simple. Il suffit d'aligner les valeurs sur le bit le moins significatif et d'ajouter, en propageant toute retenue au bit situé à gauche. Si la retenue s'étend au-delà de la fin du mot, on dit qu'elle a "bouclé", une condition appelée " retenue de fin de mot ". Lorsque cela se produit, le bit doit être rajouté au bit le plus à droite. Ce phénomène ne se produit pas dans l'arithmétique du complément à deux.

 0001 0110 22 + 0000 0011 3 ============= ==== 0001 1001 25 

La soustraction est similaire, sauf que les emprunts, plutôt que les retenues, se propagent vers la gauche. Si l'emprunt s'étend au-delà de la fin du mot, on dit qu'il a « enveloppé », une condition appelée « emprunt de fin de mot ». Lorsque cela se produit, le bit doit être soustrait du bit le plus à droite. Ce phénomène ne se produit pas dans l'arithmétique du complément à deux.

 0000 0110 6 − 0001 0011 19 ============= ==== 1 1111 0011 −12 —Un emprunt de fin de parcours est produit et le bit de signe du résultat intermédiaire est 1. − 0000 0001 1 —Soustraire l’emprunt de fin de parcours du résultat. ============= ==== 1111 0010 −13 —Le résultat correct (6 − 19 = −13) 

Il est facile de démontrer que le complément binaire d'une valeur positive est la grandeur négative de la valeur positive. Le calcul de 19 + 3 produit le même résultat que 19 − (−3).

Ajoutez 3 à 19.

 0001 0011 19 + 0000 0011 3 ============= ==== 0001 0110 22 

Soustrayez −3 de 19.

 0001 0011 19 − 1111 1100 −3 ============= ==== 1 0001 0111 23 —Un emprunt de bout en bout est réalisé. − 0000 0001 1 —Soustraire l’emprunt de fin de parcours du résultat. ============= ==== 0001 0110 22 —Le résultat correct (19 − (−3) = 22). 

Le zéro négatif est la condition dans laquelle tous les bits d'un mot signé sont 1. Cela suit les règles du complément à un selon lesquelles une valeur est négative lorsque le bit le plus à gauche est 1, et qu'un nombre négatif est le complément binaire de la grandeur du nombre. La valeur se comporte également comme zéro lors du calcul. L'ajout ou la soustraction d'un zéro négatif à/d'une autre valeur produit la valeur d'origine.

Ajout d'un zéro négatif :

 0001 0110 22 + 1111 1111 −0 ============= ==== 1 0001 0101 21 Un portage en bout de course est produit. + 0000 0001 1 ============= ==== 0001 0110 22 Le résultat correct (22 + (−0) = 22) 

Soustraire moins zéro :

 0001 0110 22 − 1111 1111 −0 ============= ==== 1 0001 0111 23 Un emprunt de bout en bout est réalisé. − 0000 0001 1 ============= ==== 0001 0110 22 Le résultat correct (22 − (−0) = 22) 

Le zéro négatif est facilement obtenu dans un additionneur en complément à un. Il suffit d'additionner le positif et le négatif de même grandeur.

 0001 0110 22 + 1110 1001 −22 ============= ==== 1111 1111 −0 Négatif zéro. 

Bien que les mathématiques produisent toujours des résultats corrects, un effet secondaire du zéro négatif est que le logiciel doit tester le zéro négatif.

La génération d'un zéro négatif ne pose aucun problème si l'addition est réalisée avec un soustracteur complémentaire. Le premier opérande est transmis au soustracteur sans modification, le deuxième opérande est complété et la soustraction génère le résultat correct, évitant ainsi un zéro négatif. L'exemple précédent additionnait 22 et −22 et produisait −0.

 0001 0110 22 0001 0110 22 1110 1001 −22 1110 1001 −22 + 1110 1001 −22 − 0001 0110 22 + 0001 0110 22 − 1110 1001 −22 =========== ==== mais =========== ==== de même, =========== === mais =========== === 1111 1111 −0 0000 0000 0 1111 1111 −0 0000 0000 0 

Les « cas limites » surviennent lorsqu'un ou les deux opérandes sont nuls et/ou négatifs.

 0001 0010 18 0001 0010 18 − 0000 0000 0 − 1111 1111 −0 =========== ==== =========== ==== 0001 0010 18 1 0001 0011 19 − 0000 0001 1 ============= ==== 0001 0010 18 

La soustraction de +0 est triviale (comme indiqué ci-dessus). Si le deuxième opérande est négatif, il est inversé et la valeur d'origine du premier opérande est le résultat. La soustraction de −0 est également triviale. Le résultat ne peut être que l'un des deux cas suivants. Dans le cas 1, l'opérande 1 est −0, le résultat est donc produit simplement en soustrayant 1 de 1 à chaque position de bit. Dans le cas 2, la soustraction génère une valeur supérieure de 1 à celle de l'opérande 1 et un borrow de fin de chaîne . La fin de l'emprunt génère la même valeur que l'opérande 1.

L'exemple suivant montre ce qui se passe lorsque les deux opérandes sont plus ou moins zéro :

 0000 0000 0 0000 0000 0 1111 1111 −0 1111 1111 −0 + 0000 0000 0 + 1111 1111 −0 + 0000 0000 0 + 1111 1111 −0 =========== ==== =========== ==== =========== ==== ===== ====== ==== 0000 0000 0 1111 1111 −0 1111 1111 −0 1 1111 1110 −1 + 0000 0001 1 ================== 1111 1111 −0 

 0000 0000 0 0000 0000 0 1111 1111 −0 1111 1111 −0 − 1111 1111 −0 − 0000 0000 0 − 1111 1111 −0 − 0000 0000 0 =========== ==== =========== ==== =========== ==== ===== ====== ==== 1 0000 0001 1 0000 0000 0 0000 0000 0 1111 1111 −0 − 0000 0001 1 ============= ==== 0000 0000 0 

Cet exemple montre que sur les quatre conditions possibles lors de l'addition de seulement ±0, un additionneur produira −0 dans trois d'entre elles. Un soustracteur complémentaire produira −0 uniquement lorsque le premier opérande est −0 et le second 0.