CHAPITRE 3 : LE COMPLÉMENT À 1

Le binaire signé échouait parce que le bit de signe n'avait aucun rapport arithmétique avec le reste du nombre. Le complément à 1 corrige ce défaut : au lieu de poser un drapeau, il transforme le nombre entier. Le résultat est presque bon, et ce « presque » est instructif.

La règle

On l'appelle aussi complément logique (CL) ou complément restreint (CR). Sa définition tient en deux lignes.

• Les nombres positifs sont codés exactement comme en binaire pur. Rien ne change.
• Un nombre négatif est codé en inversant chaque bit de la représentation de sa valeur absolue : les 0 deviennent des 1, les 1 deviennent des 0.

On note cette convention (cà1).

Un exemple complet : −24 sur 8 bits

1. valeur absolue        |-24| = 24
2. en binaire pur, 8 bits    24 = 00011000
3. on inverse chaque bit           11100111

resultat : 11100111  (ca1)

Contrôle utile : un nombre et son opposé doivent avoir, bit par bit, des valeurs toujours différentes. 00011000 et 11100111 n'ont effectivement aucun bit en commun à la même position.

Pour lire un motif en complément à 1, on regarde d'abord le bit de poids fort. S'il vaut 0, le nombre est positif et se lit en binaire pur. S'il vaut 1, le nombre est négatif : on inverse tous les bits et on lit la valeur obtenue, à laquelle on met un signe moins.

Exemple : 10110110 commence par 1, donc négatif. En inversant : 01001001 = 73. Le motif vaut −73.

L'étendue de codage

Elle est identique à celle du binaire signé :

de −(2ⁿ⁻¹ − 1) à +(2ⁿ⁻¹ − 1)

Sur 8 bits : −127 à +127. Sur 4 bits : −7 à +7. Là encore, un motif de trop.

Le zéro est toujours en double

Appliquons la règle à zéro :

• 00000000 est +0, en binaire pur ;
• en inversant chaque bit on obtient 11111111, qui est donc −0.

Le défaut n'a pas disparu : il a seulement changé de motif. Il est passé de 10000000 à 11111111.

L'addition : ça marche presque

Voilà le vrai progrès. Reprenons l'addition qui échouait au chapitre précédent, mais en complément à 1.

  00011000   (+24)
+ 11100111   (-24)
----------
  11111111   = -0 en ca1

Le résultat est −0, c'est-à-dire zéro. L'additionneur ordinaire, celui du binaire pur, a donné une réponse juste. C'est un progrès considérable : on n'a plus besoin de comparateur ni de soustracteur.

Essayons maintenant −45 + 73, dont la réponse est 28.

  11010010   (-45 en ca1)
+ 01001001   (+73)
----------
 100011011
 ^
 |__ retenue sortante

Le résultat tient sur 9 bits. On ne garde que les 8 de droite, 00011011, soit 27. Or la réponse est 28. Il manque exactement 1, et il se trouve qu'une retenue est sortie.

La règle du complément à 1 est là : quand une retenue sort du mot, il faut la réinjecter à droite. On appelle cela le report circulaire (end-around carry).

  00011011   (le resultat tronque, 27)
+        1   (la retenue reinjectee)
----------
  00011100   = 28

Le compte est bon. Mais cette réinjection a un coût réel : le circuit doit effectuer une seconde addition dès qu'une retenue sort, ce qui allonge le chemin critique. Et surtout, elle doit être prévue dans le matériel pour toutes les additions, puisque l'on ne sait pas d'avance si une retenue sortira.

Le complément à 1 a sauvé l'additionneur, mais il garde deux zéros et il réclame un tour de piste supplémentaire. Il reste un défaut à corriger.

Le lien avec la soustraction

Une remarque qui prépare le chapitre suivant. Inverser tous les bits d'un nombre N codé sur n bits revient exactement à calculer (2ⁿ − 1) − N.

Sur 8 bits, 2⁸ − 1 = 255 = 11111111. Vérifions avec 24 : 255 − 24 = 231, et 231 s'écrit bien 11100111, le motif trouvé plus haut.

D'où le nom : on complète le nombre jusqu'à 2ⁿ moins un. C'est un complément « restreint », parce qu'il s'arrête un cran avant la puissance de deux. Le chapitre suivant va franchir ce cran, et tout se mettra en place.

  11111010   (-5)
+ 00000011   (+3)
----------
  11111101

  01001001   (+73)
+ 11100111   (-24)
----------
 100110000
 ^
 |__ retenue sortante

  00110000   (48)
+        1
----------
  00110001   = 49