CHAPITRE 4 : LE COMPLÉMENT À 2

Nous arrivons à la convention qui a gagné. Tous les processeurs que vous utiliserez, du microcontrôleur à huit bits au serveur à soixante-quatre, codent leurs entiers relatifs en complément à 2. Les types int, long et short de tous les langages courants reposent dessus. Ce chapitre explique la règle, puis montre pourquoi elle est la bonne.

La règle

On l'appelle aussi complément vrai (CV). Elle se déduit de la précédente en ajoutant un geste.

• Les nombres positifs sont codés en binaire pur, comme toujours.
• Un nombre négatif est codé en prenant son complément à 1, puis en lui ajoutant 1.

On note cette convention (cà2).

Un exemple complet : −24 sur 8 bits

1. valeur absolue           |-24| = 24
2. en binaire pur               24 = 00011000
3. complement a 1                    11100111
4. on ajoute 1                     + 00000001
                                   ----------
resultat : 11101000  (ca2)

Pour relire un motif, deux méthodes au choix.

Méthode 1, la symétrique. Si le bit de poids fort vaut 1, on applique exactement le même traitement : on inverse tous les bits et on ajoute 1, et on met un signe moins devant le résultat. Sur 11101000 : inversion donne 00010111, plus 1 donne 00011000 = 24. Le motif vaut −24.

Méthode 2, la directe. On lit le motif en binaire pur, mais en donnant au bit de poids fort un poids négatif. Sur 8 bits, ce poids est −128.

11101000 = −128 + 64 + 32 + 8 = −24

Cette seconde lecture est celle du circuit. Elle explique tout le reste du chapitre : en complément à 2, le bit de poids fort n'est pas un drapeau ajouté à côté du nombre, c'est un chiffre ordinaire qui porte simplement un poids négatif. Voilà pourquoi l'arithmétique fonctionne sans aménagement.

Un seul zéro, enfin

Appliquons la règle à zéro, sur 8 bits :

0 en binaire pur        00000000
complement a 1          11111111
+ 1                   + 00000001
                      -----------
                     1 00000000
                     ^
                     |__ cette retenue sort du mot et se perd

On retombe sur 00000000. Le zéro négatif a disparu : il n'existe qu'un seul motif nul. Tester si un registre vaut zéro redevient une comparaison unique, et l'égalité entre deux nombres redevient une comparaison de motifs.

Une étendue asymétrique

Le motif libéré par la disparition du −0 n'est pas gaspillé : il sert à représenter une valeur négative de plus.

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

Les 256 motifs d'un octet représentent 256 valeurs distinctes : aucun n'est perdu. En revanche l'étendue n'est pas symétrique : il y a un négatif de plus que de positifs.

Conséquence amusante et réelle : sur 8 bits, l'opposé de −128 n'est pas représentable. Si l'on applique la règle à 10000000, on inverse en 01111111, on ajoute 1 et on retombe sur 10000000. En C, -x appliqué au plus petit int ne change rien, c'est un piège classique, et un cas que les analyseurs de code signalent.

L'addition : plus rien à faire

C'est l'argument décisif. En complément à 2, on additionne les motifs bit à bit, on jette la retenue qui sort du mot, et le résultat est juste. Pas de report circulaire, pas de comparateur, pas de cas particulier.

  00011000   (+24)
+ 11101000   (-24)
----------
 100000000
 ^ on jette ce bit
   il reste 00000000 = 0   correct

  00101101   (+45)
+ 10110111   (-73)
----------
  11100100   = -128+64+32+4 = -28   correct

  11010011   (-45)
+ 10110111   (-73)
----------
 110001010
 ^ on jette
   il reste 10001010 = -128+8+2 = -118   correct

Et la soustraction ? Elle devient gratuite : soustraire B, c'est additionner l'opposé de B. Le processeur n'a pas besoin d'un circuit soustracteur ; il lui suffit d'un inverseur et d'une retenue initiale à 1, ce qui ne coûte presque rien.

Un seul additionneur fait l'addition et la soustraction, sur les nombres positifs comme négatifs, sans jamais regarder les signes. C'est la raison d'être du complément à 2.

Le débordement : comment le détecter

Un résultat juste suppose qu'il tienne dans l'étendue. Sinon, le calcul est faux, et silencieusement faux.

  01100100   (+100)
+ 00101101   (+45)
----------
  10010001   = -111

attendu : +145, qui depasse +127

Deux nombres positifs ont donné un résultat négatif. Le débordement se repère par cette règle simple :

Le processeur applique cette règle en matériel et range la réponse dans un indicateur appelé flag de débordement (overflow, noté OF ou V). Un autre indicateur, la retenue (carry, C), signale le débordement pour les nombres non signés. Ce sont deux indicateurs distincts, et confondre les deux est une erreur fréquente : dans l'exemple ci-dessus, aucune retenue ne sort, pourtant il y a bien débordement signé.

L'extension de signe

Dernier point pratique. Que se passe-t-il quand on range un entier 8 bits dans une variable 16 bits ? Si l'on se contente de compléter par des zéros à gauche, −45 = 11010011 deviendrait 0000000011010011, soit 211. Le nombre a changé de signe et de valeur.

La règle correcte est de recopier le bit de signe autant de fois que nécessaire.

  +45 sur  8 bits : 00101101
  +45 sur 16 bits : 0000000000101101   (on complete par des 0)

  -45 sur  8 bits : 11010011
  -45 sur 16 bits : 1111111111010011   (on complete par des 1)

Vérification sur 16 bits avec la lecture directe : le poids du bit de tête est −32 768, et la somme des bits à 1 donne bien −45. Les processeurs disposent d'instructions dédiées pour cela, MOVSX sur x86, par exemple, distinctes de celles qui complètent par des zéros pour les nombres non signés.

  10011100   (-100)
+ 11010011   ( -45)
----------
 101101111
 ^ on jette la retenue
   il reste 01101111 = +111