cours1 min de lecture

Entiers relatifs et complément à deux

Comment représenter un entier négatif en binaire et pourquoi le complément à deux s'est imposé.

programme

Introduction

Vous savez désormais représenter un entier positif en binaire. Mais comment fait-on pour coder un nombre négatif comme $-5$ ? Il n'y a pas de signe moins disponible — seuls les bits 0 et 1 existent. Plusieurs solutions ont été imaginées au fil de l'histoire de l'informatique, mais une seule s'est imposée universellement : le complément à deux.

Ce codage a une propriété quasi magique : il permet d'additionner un positif et un négatif comme s'il s'agissait de deux entiers ordinaires, sans distinction de signe. Les circuits arithmétiques s'en trouvent considérablement simplifiés.

Le bit de signe — première idée

L'idée la plus naïve consiste à réserver le bit de poids fort comme bit de signe : 0 pour le positif, 1 pour le négatif. Les autres bits codent la valeur absolue.

Sur 4 bits :

0101 représenterait $+5$ .
1101 représenterait $-5$ .

Cette approche, appelée signe et valeur absolue, semble naturelle… mais elle souffre de défauts rédhibitoires :

Il existe deux zéros : 0000 et 1000, ce qui complique les comparaisons.
L'addition d'un positif et d'un négatif ne fonctionne plus de façon élémentaire : il faut un circuit dédié pour gérer le signe.

Ce n'est pas ce codage qui est utilisé en pratique. Il est présenté ici uniquement pour comprendre pourquoi le complément à deux a été inventé.

Le complément à deux

Sur $n$ bits, le complément à deux d'un entier $x$ se définit ainsi : on écrit $x$ comme un entier non signé, on inverse tous les bits (les 0 deviennent 1 et inversement), puis on ajoute 1.

Exemple sur 8 bits : représenter $-5$ .

Étape	Valeur
1. Écrire $5$ sur 8 bits	`0000 0101`
2. Inverser tous les bits	`1111 1010`
3. Ajouter 1	`1111 1011`

Donc $-5 = (1111\,1011)_2$ en complément à deux sur 8 bits.

Le bit de poids fort indique toujours le signe : 0 pour les positifs, 1 pour les négatifs. Mais contrairement au codage signe/valeur absolue, les autres bits ne sont pas la valeur absolue — ils résultent de la double opération « inversion + 1 ».

Pourquoi ça marche — l'addition modulo $2^n$

Sur $n$ bits, l'arithmétique se fait modulo $2^n$ . Coder un entier négatif $-x$ revient à utiliser la valeur positive $2^n - x$ qui, modulo $2^n$ , se comporte exactement comme $-x$ .

Vérification : sur 8 bits, $-5$ correspond à $256 - 5 = 251 = (1111\,1011)_2$ . C'est bien le résultat trouvé plus haut.

Et l'addition fonctionne :

5 + (-5) = (0000\,0101)_2 + (1111\,1011)_2 = (1\,0000\,0000)_2

Le 9ᵉ bit déborde de l'octet et est ignoré : il reste $(0000\,0000)_2 = 0$ . L'opération donne bien zéro.

Deux opérateurs Python utilisés ci-dessous : a << n décale les bits de a de n rangs vers la gauche (équivaut à multiplier par

2^n

) ; a & b réalise un ET bit-à-bit (chaque bit du résultat vaut 1 seulement si les deux bits correspondants de a et b valent 1). Combinés, x & ((1 << n) - 1) ne garde que les n bits de poids faible de x.

⏵ Ctrl+↵ pour exécuter

Aucune exécution pour l'instant.

Sortie attendue :

-5 sur 8 bits : 0b11111011 (251 non signé)

Étendue représentable

Sur $n$ bits en complément à deux, on couvre l'intervalle :

-2^{n-1} \leq x \leq 2^{n-1} - 1

Bits	Minimum	Maximum
8	$-128$	$+127$
16	$-32\,768$	$+32\,767$
32	$-2\,147\,483\,648$	$+2\,147\,483\,647$
64	$-2^{63}$	$2^{63} - 1$

On remarque que l'intervalle n'est pas symétrique : il y a un entier négatif de plus que d'entiers positifs. C'est la conséquence du fait qu'il n'existe qu'un seul zéro (qui est compté comme positif au sens large).

Sur 8 bits en complément à deux, combien d'entiers distincts peut-on représenter ?

Bits nécessaires pour une somme ou un produit

Combien de bits faut-il prévoir si l'on additionne ou si l'on multiplie deux entiers ?

Somme de deux entiers de $n$ bits : il peut y avoir une retenue qui ajoute 1 bit. Le résultat tient sur $n+1$ bits.
Produit de deux entiers de $n$ bits : le résultat peut atteindre $(2^n - 1)^2 \approx 2^{2n}$ , donc il faut prévoir $2n$ bits.

En pratique, sur un processeur 64 bits, multiplier deux entiers de 32 bits tient encore largement dans 64 bits, donc sans débordement.

Le cas Python — entiers de taille arbitraire

Python (à partir de la version 3) ne limite pas la taille des entiers : ils peuvent croître autant que la mémoire le permet.

print(2 ** 100)
# 1267650600228229401496703205376

print(-1 << 8)
# -256

print(bin(-5))
# -0b101  — Python affiche le signe, pas le complément à deux

Cette commodité a un coût : un entier Python n'a pas une taille fixe en mémoire, donc les opérations sont un peu plus lentes que sur un entier 32 ou 64 bits d'un langage bas niveau comme C.

Que vaut −1-1−1 en complément à deux sur 8 bits ?

Pièges courants

Le bit de poids fort vaut 1 pour tout négatif, mais ce n'est pas l'opposé en valeur absolue : il faut vraiment refaire « inverser + 1 ».
Sur un type entier de taille fixe (C, Java), additionner deux grands positifs peut donner un négatif à cause du débordement (overflow). Python vous protège de cela.
Pour passer de la représentation interne (positive) au nombre signé, on utilise toujours la convention : si le bit de poids fort est 1, on soustrait $2^n$ .

Pour aller plus loin

Le complément à deux explique aussi pourquoi le décalage à droite d'un nombre négatif est subtil : il faut propager le bit de signe pour préserver la sémantique de division entière. Vous croiserez cette opération en bas niveau (C, assembleur) ou en manipulation de bits.