Partie 2 : Représentation des entiers relatifs

B.O. spécial n° 1 du 22 janvier 2019 - NSI Première

Contenus	Capacités attendues	Commentaires
Représentation binaire d'un entier relatif	Évaluer le nombre de bits nécessaires à l'écriture en base 2 d'un entier, de la somme ou du produit de deux nombres entiers. Utiliser le complément à 2.	Il s'agit de décrire les tailles courantes des entiers (8, 16, 32 ou 64 bits). Il est possible d'évoquer la représentation des entiers de taille arbitraire de Python.

1. Le problème du signe

Jusqu'ici, nous avons représenté uniquement des entiers positifs (ou nuls). Mais comment représenter des nombres négatifs en binaire, alors que nous ne disposons que de 0 et de 1 ?

Plusieurs solutions ont été envisagées au cours de l'histoire de l'informatique.

1.1 Première idée : le bit de signe

L'idée la plus naturelle consiste à réserver le bit de poids fort (le bit le plus à gauche) pour indiquer le signe :

0 en tête = nombre positif ;
1 en tête = nombre négatif.

Sur 8 bits, le nombre +5 serait codé 00000101 et le nombre -5 serait codé 10000101.

Cette méthode n'est donc pas utilisée dans les ordinateurs modernes. On lui préfère le complément à 2.

2. Le complément à 2

Le complément à 2 est la méthode standard utilisée par tous les processeurs actuels pour représenter les entiers relatifs.

2.1 Principe général

On travaille toujours sur un nombre fixe de bits (par exemple 8 bits). Les règles sont :

Les entiers positifs sont codés normalement en binaire, avec un 0 en tête.
Les entiers négatifs sont obtenus par un procédé appelé complément à 2.
Le bit de poids fort indique le signe : 0 pour positif, 1 pour négatif.

2.2 Comment obtenir le complément à 2 d'un nombre ?

Pour coder un nombre négatif -N sur n bits :

Écrire N en binaire sur n bits.
Inverser tous les bits (0 devient 1, 1 devient 0). C'est le complément à 1.
Ajouter 1 au résultat.

2.3 Comment décoder un nombre en complément à 2 ?

Si le bit de poids fort vaut 0, le nombre est positif : on le lit directement.

Si le bit de poids fort vaut 1, le nombre est négatif. Pour trouver sa valeur absolue, on applique à nouveau le complément à 2 (la méthode est son propre inverse) :

Inverser tous les bits.
Ajouter 1.
Le résultat est la valeur absolue ; le nombre original est négatif.

2.4 Vérification par l'addition

La beauté du complément à 2, c'est que l'addition fonctionne naturellement, sans se soucier des signes. Vérifions que 45 + (-45) = 0 :

  00101101   (45)
+ 11010011   (-45)
----------
1 00000000

On obtient 9 bits, mais on travaille sur 8 bits : le bit de dépassement (le 1 tout à gauche) est ignoré. Le résultat est bien 00000000, soit 0. ✓

C'est l'avantage décisif du complément à 2 : les mêmes circuits électroniques servent pour l'addition des positifs et des négatifs.

3. Intervalle de valeurs selon le nombre de bits

Sur n bits en complément à 2, on peut représenter les entiers de -2ⁿ⁻¹ à 2ⁿ⁻¹ - 1.

Nombre de bits	Valeur minimale	Valeur maximale	Nombre de valeurs
8	-128	127	256
16	-32 768	32 767	65 536
32	-2 147 483 648	2 147 483 647	environ 4,3 milliards
64	environ -9,2 × 10¹⁸	environ 9,2 × 10¹⁸	environ 1,8 × 10¹⁹

Quelques valeurs remarquables sur 8 bits

Décimal	Binaire (8 bits)
127	`01111111`
1	`00000001`
0	`00000000`
-1	`11111111`
-2	`11111110`
-127	`10000001`
-128	`10000000`

4. Le dépassement de capacité (overflow)

Quand le résultat d'un calcul sort de l'intervalle représentable, on parle de dépassement de capacité (en anglais overflow).

En additionnant 100 et 50 sur 8 bits :

  01100100   (100)
+ 00110010   (50)
----------
  10010110   (-106 en complément à 2 !)

Le résultat attendu est 150, mais sur 8 bits signés, le maximum est 127. Le bit de poids fort est passé à 1 : l'ordinateur interprète le résultat comme -106, ce qui est faux.

5. Évaluer le nombre de bits d'une somme ou d'un produit

5.1 Somme de deux entiers

Si A est codé sur n₁ bits et B sur n₂ bits, leur somme A + B peut nécessiter au plus :

max(n₁, n₂) + 1 bits

Le « + 1 » correspond à une éventuelle retenue.

5.2 Produit de deux entiers

Si A est codé sur n₁ bits et B sur n₂ bits, leur produit A × B peut nécessiter au plus :

n₁ + n₂ bits

6. Les entiers en Python

6.1 Entiers de taille arbitraire

Contrairement à la plupart des langages de programmation, Python gère des entiers de taille arbitraire : il n'y a pas de limite au nombre de bits utilisés. Python adapte automatiquement la taille en mémoire.

>>> 2 ** 100
1267650600228229401496703205376

>>> 2 ** 1000   # un nombre de plus de 300 chiffres !
107150860718626732094842504906000181056140481170553360744375038837035105112493612249319
...

Aucun risque de dépassement de capacité en Python.

6.2 Simuler le complément à 2

En Python, les nombres négatifs ne sont pas stockés en complément à 2 (puisque la taille est variable). Mais on peut simuler le complément à 2 sur n bits :

def complement_a_2(n, bits=8):
    """Affiche le codage en complément à 2 de n sur un nombre donné de bits."""
    if n >= 0:
        return bin(n)[2:].zfill(bits)
    else:
        return bin((1 << bits) + n)[2:]

print(complement_a_2(45))    # 00101101
print(complement_a_2(-45))   # 11010011
print(complement_a_2(-1))    # 11111111
print(complement_a_2(-128))  # 10000000

7. Résumé

Concept	Détail
Méthode standard	Complément à 2
Bit de poids fort	0 = positif, 1 = négatif
Obtenir -N	Inverser tous les bits, puis ajouter 1
Intervalle sur n bits	De -2ⁿ⁻¹ à 2ⁿ⁻¹ - 1
Tailles courantes	8, 16, 32, 64 bits
Avantage principal	L'addition fonctionne sans distinction de signe
Dépassement de capacité	Le résultat sort de l'intervalle représentable
Python	Entiers de taille arbitraire (pas de dépassement)