Complément à deux : écrire les entiers négatifs en binaire

Sur 8 bits, on peut écrire 2 × 2 × … × 2 = 256 motifs différents. Pour les entiers positifs, ils codent 0 à 255. Pour coder aussi des entiers négatifs, la convention utilisée par les ordinateurs est le complément à deux :

Sur n bits, le bit de gauche (bit de poids fort) a pour poids −2ⁿ⁻¹ au lieu de +2ⁿ⁻¹ ; les autres bits gardent leur poids habituel.

Sur 8 bits, les poids deviennent donc −128, 64, 32, 16, 8, 4, 2, 1. Par exemple :

Valeur : −128 + 64 + 16 + 8 + 2 + 1 = −37.

Conséquences immédiates : un motif qui commence par 0 code un entier positif ou nul ; un motif qui commence par 1 code un entier négatif ; sur 8 bits, on code les entiers de −128 à 127.

Méthode pour coder −x (x positif). On écrit x sur n bits, on inverse tous les bits (0 ↔ 1), puis on ajoute 1. Pour −37 sur 8 bits : 37 s'écrit 0010 0101 ; inversé : 1101 1010 ; plus 1 : 1101 1011.

Une autre façon de le dire : sur 8 bits, le motif de −x est l'écriture binaire de 256 − x (ici 256 − 37 = 219). La fonction suivante suppose un entier x dans l’intervalle −128 à 127 ; elle ne vérifie pas elle-même cette précondition :

def code8(x):
    if x < 0:
        x = x + 256
    return format(x, "08b")

print(code8(37))
print(code8(-37))
print(code8(-128))

00100101
11011011
10000000

Dans l’autre sens, la fonction suivante suppose un motif composé d’exactement huit bits. Si sa valeur non signée atteint 128, il code un entier négatif : on lui retire 256.

def valeur8(motif):
    v = int(motif, 2)
    if v >= 128:
        v = v - 256
    return v

print(valeur8("11011011"))
print(valeur8("01111111"))
print(valeur8("10000000"))

-37
127
-128

Pourquoi cette convention ? Parce que l’addition binaire ordinaire, en ne conservant que n bits, calcule une somme modulo 2ⁿ. Elle donne la somme entière signée seulement si le résultat est représentable. Dans l’exemple suivant, cette condition est satisfaite : 37 + (−37) donne 0010 0101 + 1101 1011 = 1 0000 0000 ; on ne garde que les 8 bits de droite, 0000 0000, c'est-à-dire 0. Le processeur n'a pas besoin d'un circuit spécial pour les négatifs.

Tailles courantes. On utilise des entiers de 8, 16, 32 ou 64 bits ; sur n bits, l'intervalle codé va de −2ⁿ⁻¹ à 2ⁿ⁻¹ − 1. Un résultat qui sort de l'intervalle provoque un dépassement de capacité. Les entiers de Python, eux, n'ont pas de taille fixe.

Énoncé. Sur 8 bits en complément à deux, quel entier code le motif 1110 0101 ?

Résolution.

1. Le bit de gauche vaut 1 : l'entier est négatif, et ce bit pèse −128.
2. Les sept autres bits, 110 0101, valent 64 + 32 + 4 + 1 = 101.
3. L'entier est −128 + 101 = −27.

Contrôle par la méthode inverse. 27 s'écrit 0001 1011 ; inversé : 1110 0100 ; plus 1 : 1110 0101. On retrouve bien le motif de départ.

Les motifs se suivent comme sur un cercle : en ajoutant 1 au plus grand positif, on passe au plus petit négatif.

Tout motif commençant par 1 vaut sa valeur ordinaire moins 256.