Dans un ordinateur, tout est stocké sous forme de bits (0 ou 1). Comment représenter des nombres entiers, positifs ou négatifs, ou des nombres à virgule ?

I. Entiers positifs

a) Écriture en base 2

Tout entier naturel s'écrit de manière unique en base 2 :

Par exemple, , qui s'écrit en base 2.

print(bin(13))          # l'écriture en base 2, précédée de 0b
print(int("1101", 2))   # et dans l'autre sens

b) Mots de taille fixe

Le processeur manipule des mots de taille fixe : 8, 16, 32 ou 64 bits. Sur un mot de bits, on peut représenter les entiers de à .

Que se passe-t-il si un calcul dépasse cette valeur ? Le résultat est calculé modulo : on parle de dépassement de capacité. Par exemple, sur 8 bits, donne .

def addition_8_bits(a, b):
    """Simule une addition sur un mot de 8 bits."""
    return (a + b) % 2 ** 8

print(addition_8_bits(200, 50))
print(addition_8_bits(200, 100))

II. Entiers signés : le complément à deux

Pour représenter des entiers négatifs sur bits, on utilise le complément à deux : on représente l'entier par l'écriture en base 2 de :

• si ;
• si .

Par exemple, sur 8 bits, on représente les entiers de à , et est représenté par , soit .

def complement_a_deux(x, n):
    """Renvoie la chaîne des n bits représentant x en complément à deux."""
    assert -2 ** (n - 1) <= x < 2 ** (n - 1)
    if x < 0:
        x += 2 ** n
    return bin(x)[2:].zfill(n)   # zfill complète avec des 0 à gauche

for x in [5, 1, 0, -1, -5, 127, -128]:
    print(x, "->", complement_a_deux(x, 8))

Par exemple, sur 8 bits : se calcule , et en ne gardant que 8 bits, on obtient .

III. Les entiers de Python

En Python, les entiers ne sont pas limités à 64 bits : ce sont des entiers multi-précision, dont la taille augmente selon les besoins.

print(2 ** 64)
print(2 ** 200)
print(len(str(2 ** 10000)), "chiffres")

C'est très pratique, mais cela a un coût : les opérations sur de grands entiers ne se font plus en temps constant. Par exemple, une addition de deux entiers de chiffres prend un temps proportionnel à : il devient difficile d'évaluer la complexité d'un programme qui manipule de très grands entiers.

IV. Nombres à virgule : les flottants

a) Réels, décimaux, flottants

• Les nombres réels ne peuvent pas tous être représentés en machine : il y en a une infinité non dénombrable.
• Même un nombre décimal comme n'a pas une écriture finie en base 2 : .

On représente donc les nombres à virgule de manière approchée, par des flottants.

b) Mantisse et exposant

Un flottant représente un nombre sous la forme :

où :

• est le signe (1 bit) ;
• est la mantisse, écrite en base 2 avec un nombre fixé de chiffres après la virgule : ;
• est l'exposant, un entier stocké sur un nombre fixé de bits.

Comme la mantisse commence toujours par , ce n'est pas stocké. Le nombre ne peut donc pas s'écrire ainsi : il a une représentation spéciale (exposant et mantisse nuls).

Par exemple, : le signe est , la mantisse , l'exposant .

En Python, les flottants sont stockés sur 64 bits : 1 bit de signe, 11 bits d'exposant, 52 bits de mantisse. On a donc environ 16 chiffres significatifs.

c) Conséquences sur les calculs

Les calculs sur les flottants sont arrondis à chaque opération :

print(0.1 + 0.2)
print(0.1 + 0.2 == 0.3)
print(1e16 + 1 - 1e16)

Il ne faut donc jamais tester l'égalité de deux flottants avec ==. On teste plutôt si leur différence est petite :

def presque_egaux(x, y, eps=1e-9):
    return abs(x - y) < eps

print(presque_egaux(0.1 + 0.2, 0.3))

Les erreurs d'arrondi peuvent aussi s'accumuler :

s = 0
for k in range(1000):
    s += 0.1
print(s)

Exercices

def valeur(bits):
    n = len(bits)
    x = int(bits, 2)
    if bits[0] == "1":   # nombre négatif
        x -= 2 ** n
    return x