Chapitre 2 : Représentation des entiers relatifs¶

Programme officiel (B.O.)¶

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.

Inconvénients de cette méthode

Le zéro a deux représentations : 00000000 (+0) et 10000000 (-0). C'est gênant pour les tests d'égalité.
Les opérations arithmétiques (addition, soustraction) ne fonctionnent pas directement : il faut des circuits spéciaux selon le signe.

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.

Exemple : coder -45 sur 8 bits

Écriture de 45 en binaire sur 8 bits : 00101101
Inversion de tous les bits : 11010010
Ajout de 1 : 11010010 + 1 = 11010011

Le codage de -45 sur 8 bits est donc : 11010011

Exemple : coder -1 sur 8 bits

Écriture de 1 en binaire sur 8 bits : 00000001
Inversion : 11111110
Ajout de 1 : 11111111

Le codage de -1 sur 8 bits est donc : 11111111

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.

Exemple : décoder 11010011 (sur 8 bits)

Le bit de poids fort est 1 : le nombre est négatif.

Inversion : 00101100
Ajout de 1 : 00101101
Conversion en décimal : 32 + 8 + 4 + 1 = 45

Conclusion : 11010011 représente -45. ✓

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¹⁹

À retenir

Sur n bits en complément à 2 :

Intervalle : de -2ⁿ⁻¹ à 2ⁿ⁻¹ - 1
Il y a un négatif de plus que de positifs (par exemple, sur 8 bits, on va de -128 à +127).
Le zéro n'a qu'une seule représentation : 00000000.

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).

Exemple sur 8 bits

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.

Attention

Le dépassement de capacité est une source de bugs dans les programmes. Le 4 juin 1996, la fusée Ariane 5 a explosé 37 secondes après le décollage à cause d'un dépassement de capacité : une valeur calculée sur 64 bits a été convertie en 16 bits, provoquant un résultat aberrant qui a fait dévier la trajectoire.

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.

Exemple

A = 200 nécessite 8 bits. B = 100 nécessite 7 bits.
A + B = 300 nécessite 9 bits (car 300 > 255 = 2⁸ - 1).

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

Exemple

A = 15 nécessite 4 bits. B = 15 nécessite 4 bits.
A × B = 225 nécessite 8 bits (car 225 < 256 = 2⁸). On a bien 4 + 4 = 8.

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)