Complément à deux et entiers signés

Un octet contient 8 bits, soit 256 motifs. Lus comme un nombre non signé, ils valent de 0 à 255. Mais les programmes ont aussi besoin de nombres négatifs, et il n’y a pas de signe moins en mémoire : il faut donner un sens négatif à certains des 256 motifs. Il y a plusieurs façons de choisir lesquels. Ce chapitre compare les quatre qui ont servi dans de vraies machines, et explique pourquoi tous les CPU modernes utilisent la même, le complément à deux.

Tous les exemples utilisent 8 bits. Tout fonctionne de la même façon avec 16, 32 ou 64.

Signe et valeur absolue

L’idée évidente est celle qu’on utilise sur papier : garder un bit pour le signe (0 pour +, 1 pour −) et les 7 bits restants pour la valeur absolue. C’est la représentation signe et valeur absolue (sign-magnitude).

+6 = 0000 0110
−6 = 1000 0110

Elle se lit facilement, mais pose deux problèmes. D’abord, il y a deux zéros : 0000 0000 (+0) et 1000 0000 (−0), qu’une comparaison doit traiter comme égaux. Ensuite, l’arithmétique est malcommode : pour additionner deux nombres, le matériel doit d’abord comparer leurs signes, puis additionner ou soustraire les valeurs absolues, et dans le second cas trouver la plus grande. L’addition binaire brute des motifs donne n’importe quoi : 0000 0110 + 1000 0110 donne 1000 1100, soit −12, et non 0.

Cette représentation n’est pas morte : les nombres à virgule flottante l’utilisent, avec un bit de signe séparé, comme le montre le chapitre sur la virgule flottante.

Complément à un

Le complément à un prend l’opposé d’un nombre en inversant tous ses bits :

+6 = 0000 0110
−6 = 1111 1001

L’addition marche mieux : on peut additionner les motifs directement, à condition de réinjecter en bas la retenue sortie du bit de poids fort (la retenue circulaire, end-around carry). Mais il y a toujours deux zéros : 0000 0000 et 1111 1111. Des machines comme le CDC 6600 et la série UNIVAC 1100 utilisaient le complément à un. Le complément à un est aujourd’hui obsolète dans les CPU ; son principal survivant aujourd’hui est la somme de contrôle Internet des en-têtes IPv4, TCP et UDP, qui est une somme en complément à un de mots de 16 bits.

Notation en excédent k (biaisée)

L’excédent k stocke une valeur v sous la forme du nombre non signé v + k. Avec 8 bits et k = 128, −128 est stocké comme 0 (0000 0000), 0 comme 128 (1000 0000) et +127 comme 255 (1111 1111). −6 est donc stocké comme 122 :

−6 + 128 = 122 = 0111 1010

Son avantage : l’ordre des motifs de bits suit l’ordre des valeurs, si bien que comparer deux nombres en excédent k se réduit à une comparaison non signée. C’est pourquoi la norme IEEE 754 stocke ainsi les exposants des nombres à virgule flottante, avec un biais de 127 pour un float et de 1023 pour un double. Sur 8 bits, l’excédent 128 se révèle être le complément à deux avec le bit de poids fort inversé.

Le complément à deux

Pensez au compteur kilométrique d’une voiture, avec trois roues décimales. En partant de 000 et en reculant d’un cran, on obtient 999. Dans un monde de nombres à 3 chiffres, 999 se comporte donc exactement comme −1 : ajoutez-lui 1 et vous obtenez 000, la retenue tombant au bout. Le complément à deux applique la même idée en binaire. Sur n bits, le nombre négatif −x est stocké comme le nombre non signé 2ⁿ − x :

−1 = 256 − 1 = 255 = 1111 1111
−6 = 256 − 6 = 250 = 1111 1010

À la main, il y a plus rapide : inverser tous les bits, puis ajouter 1.

+6            0000 0110
invert        1111 1001
add 1         1111 1010   = −6

Une autre façon de lire un nombre en complément à deux : le bit de poids fort a un poids négatif. Sur 8 bits, les bits valent −128, 64, 32, 16, 8, 4, 2, 1. 1111 1010 vaut −128 + 64 + 32 + 16 + 8 + 2 = −6. Le bit de poids fort donne donc aussi le signe : 1 veut dire négatif. C’est pourquoi on l’appelle toujours le bit de signe, même s’il n’est pas un signe séparé.

La roue complète des nombres à 3 bits montre la structure :

Il n’y a qu’un zéro, et l’intervalle est asymétrique : n bits vont de −2ⁿ⁻¹ à 2ⁿ⁻¹ − 1. Avec 2ⁿ motifs (un nombre pair) et un seul zéro, positifs et négatifs ne peuvent pas être équilibrés ; le complément à deux donne le motif en trop aux négatifs.

L’intrus, le minimum, n’a pas d’équivalent positif. Prendre l’opposé de −128 (1000 0000) en inversant et en ajoutant 1 donne 0111 1111 + 1 = 1000 0000 : encore −128.

Les quatre systèmes côte à côte

Pourquoi le complément à deux a gagné

La propriété décisive : additionner les motifs de bits comme des nombres non signés donne le bon résultat en complément à deux, à condition d’ignorer la retenue sortie du bit de poids fort. −6 + 10 :

  1111 1010    (−6, or 250 unsigned)
+ 0000 1010    (10)
= 1 0000 0100  → drop the carry → 0000 0100 = 4

En non signé, c’était 250 + 10 = 260, et 260 − 256 = 4. En signé, c’était −6 + 10 = 4. Les deux lectures sont justes en même temps. Un CPU n’a donc besoin que d’un additionneur et d’une instruction add pour les nombres signés et non signés, et la soustraction n’est que l’addition de l’opposé : a − b = a + (b inversé) + 1, ce qu’un additionneur réalise en inversant une entrée et en mettant sa retenue entrante à 1. Le chapitre sur les additionneurs construit ce circuit.

Tous les CPU courants utilisent aujourd’hui le complément à deux, et la norme C23 en a enfin fait la seule représentation autorisée en C. Puisque les bits seuls ne disent pas si une valeur est signée, c’est l’instruction qui le dit : le x86 a des versions signées et non signées des comparaisons, de l’élargissement, des décalages à droite, de la multiplication et de la division. Le chapitre sur les types de données en donne la liste.

L’extension de signe

Pour élargir un nombre en complément à deux (de 8 à 16 bits, par exemple), on recopie le bit de signe dans toutes les nouvelles positions. C’est l’extension de signe :

−5 in 8 bits:              1111 1011
−5 in 16 bits:   1111 1111 1111 1011
+5 in 8 bits:              0000 0101
+5 in 16 bits:   0000 0000 0000 0101

Cela marche parce que les copies totalisent le même poids négatif : sur 16 bits, les bits 15 à 7 de −5 valent −32 768 + 16 384 + … + 256 + 128 = −128, exactement ce que valait à lui seul le bit de signe sur 8 bits. Les nombres non signés s’élargissent avec des zéros (extension par des zéros). Confondre les deux est un bogue classique : l’octet 0xFB devient 251 ou −5 selon l’extension choisie par le compilateur, qui dépend du type déclaré.

Le débordement et sa détection

Avec un nombre fixe de bits, certains résultats ne tiennent pas. Pour les nombres non signés, le résultat est faux quand une retenue sort du bit de poids fort : 200 + 100 = 300 ne tient pas dans un octet. Pour les nombres signés, la règle est différente, et il y a trois façons équivalentes de l’énoncer :

1. Les signes : additionner deux nombres de même signe donne un résultat de signe opposé. (Additionner des nombres de signes opposés ne déborde jamais.)
2. Les retenues : la retenue entrant dans le bit de signe diffère de celle qui en sort.
3. L’intervalle : le vrai résultat sort de −128 à 127.

Le CPU calcule les deux conditions à chaque addition et soustraction, et les enregistre dans deux indicateurs : CF, l’indicateur de retenue (débordement non signé), et OF, l’indicateur de débordement (débordement signé). Quelques cas, vérifiés bit à bit :

Le simulateur montre les mêmes indicateurs. Exécutez le programme pas à pas et regardez CF et OF après chaque instruction :

neg al transforme 5 en 0xFB, affiché 251 en non signé, qui vaut −5. 100 + 50 laisse 0x96 (−106 en signé) avec OF = 1 et CF = 0 : correct en non signé (150), faux en signé. −100 + −50 laisse 106 avec les deux indicateurs à 1 : faux dans les deux lectures. −1 + 1 donne 0 avec CF = 1 mais OF = 0 : en non signé, 255 + 1 a débordé ; en signé, la réponse est juste. 5 − 7 donne 0xFE, −2, avec CF = 1 : après une soustraction, l’indicateur de retenue du x86 signifie emprunt : le résultat non signé aurait été négatif. (ARM fait l’inverse : après une soustraction, son indicateur de retenue vaut 1 quand il n’y a pas eu d’emprunt.) La dernière instruction prend l’opposé de −128 et retrouve −128, avec OF = 1.

C’est au programme de choisir quel indicateur compte : jo et les comparaisons signées (jl, jg) regardent OF ; jc et les non signées (jb, ja) regardent CF. Le chapitre sur les indicateurs montre comment les compilateurs s’en servent.

Le débordement dans les vrais programmes

Le matériel reboucle en silence ; les langages ne s’accordent pas sur ce que cela signifie.

• En C et en C++, le débordement signé est un comportement indéfini : le compilateur peut supposer qu’il n’arrive jamais, et optimiser en conséquence. L’arithmétique non signée, elle, est définie comme rebouclant modulo 2ⁿ.
• Rust panique sur un débordement dans les compilations de débogage et reboucle dans les compilations optimisées ; Java et Go rebouclent toujours.
• Le minimum asymétrique réserve ses propres surprises. abs(INT_MIN) renvoie INT_MIN, toujours négatif. Et INT_MIN / -1, dont le vrai résultat 2 147 483 648 ne tient pas, se comporte différemment selon l’architecture : l’instruction idiv du x86 lève une exception d’erreur de division (Linux la transforme en SIGFPE et le programme meurt), tandis que sdiv sur ARM64 renvoie tranquillement INT_MIN. Compilé avec gcc sous Linux ARM64, un programme de test a affiché INT_MIN / -1 = -2147483648 et a continué ; la même division dans le simulateur s’arrête sur une erreur de division #DE.

À retenir

• Le signe et valeur absolue et le complément à un ont deux zéros et demandent un matériel spécial pour l’arithmétique signée. L’excédent k stocke v + k et préserve l’ordre des valeurs, d’où son usage pour les exposants flottants.
• Le complément à deux stocke −x sous la forme 2ⁿ − x : inverser les bits et ajouter 1. Le bit de poids fort pèse −2ⁿ⁻¹. Intervalle : −2ⁿ⁻¹ à 2ⁿ⁻¹ − 1, un seul zéro, et un nombre négatif en trop qui est son propre opposé.
• Sa propriété décisive : le même additionneur sert au signé et au non signé, et la soustraction est l’addition de l’opposé. Tous les CPU courants l’utilisent ; C23 l’impose.
• L’extension de signe recopie le bit de signe lors d’un élargissement ; l’extension par des zéros est pour les valeurs non signées.
• Débordement non signé = retenue sortant du bit de poids fort (CF). Débordement signé = retenue entrant dans le bit de signe ≠ retenue sortante, ou, de façon équivalente, deux opérandes de même signe donnant un résultat de signe opposé (OF).
• Les langages traitent le débordement différemment : indéfini en C pour les types signés, une panique en Rust en débogage, un rebouclage en Java. INT_MIN / -1 déclenche une exception sur x86 et renvoie INT_MIN sur ARM64.