Représentation des entiers : bases et binaire

Un ordinateur ne connaît que deux états : courant ou pas, aimanté ou non, $0$ ou $1$.

Toute donnée (nombre, texte, image, son) doit donc être traduite en suites de bits.

Ce chapitre commence par les entiers : comment les écrire en base $2$ (binaire) et en base $16$ (hexadécimal), combien de bits il faut pour les écrire, et comment représenter les entiers relatifs grâce au complément à 2.

1. Écrire un entier dans une base

1.1 Le principe positionnel

En base $10$, le nombre $4\,072$ signifie $4 \times 10^3 + 0 \times 10^2 + 7 \times 10^1 + 2 \times 10^0$.

Chaque chiffre est multiplié par une puissance de la base, qui dépend de sa position.

1.2 De la base 2 à la base 10

On additionne les puissances de $2$ qui correspondent aux bits à $1$.

$\overline{1011\,0101}^{\,2} = 128 + 32 + 16 + 4 + 1 = 181.$

def decimal(s):
    n = 0
    # à toi
    return n

1.3 De la base 10 à la base 2 : les divisions successives

Donc $45 = \overline{101101}^{\,2}$. Vérification : $32 + 8 + 4 + 1 = 45$.

Le programme suit exactement la méthode des divisions, et affiche chaque étape.

def binaire(n):
    """Écriture binaire de l'entier positif n, sous forme de chaîne."""
    if n == 0:
        return "0"
    s = ""
    while n > 0:
        print(n, "= 2 x", n // 2, "+", n % 2)
        s = str(n % 2) + s   # le reste se place devant
        n = n // 2
    return s

print(binaire(45))

Python possède aussi des fonctions toutes faites.

>>> bin(45)
'0b101101'
>>> int("101101", 2)
45

Le préfixe 0b signale une écriture binaire.

1.4 La base 16 : l'hexadécimal

$\overline{1011\,0101}^{\,2} \to \overline{1011}^{\,2} = 11 = \text{B},\ \overline{0101}^{\,2} = 5 \quad\Rightarrow\quad 181 = \overline{\text{B5}}^{\,16}.$

L'hexadécimal sert à écrire de façon compacte des contenus binaires : couleurs, adresses mémoire, adresses MAC, codes Unicode.

print(hex(181))
print(int("B5", 16))

couleur = "FF6600"
rouge = int(couleur[0:2], 16)
vert = int(couleur[2:4], 16)
bleu = int(couleur[4:6], 16)
print(rouge, vert, bleu)

2. Combien de bits ?

2.1 Nombre de bits d'un entier

Un octet (byte) vaut $8$ bits. Les préfixes : $1$ ko $= 10^3$ octets, $1$ Mo $= 10^6$, $1$ Go $= 10^9$. À ne pas confondre avec $1$ Kio $= 2^{10} = 1\,024$ octets.

def nb_bits(n):
    # à toi
    return 0

2.2 Somme et produit

Par exemple, $255 + 255 = 510 < 512 = 2^9$, et $255 \times 255 = 65\,025 < 65\,536 = 2^{16}$.

Python, lui, manipule des entiers de taille arbitraire : il n'y a pas de débordement, la mémoire s'adapte. Ce n'est pas le cas de la plupart des langages (C, Java), où un int occupe $32$ bits.

# Python n'a pas de limite de taille
print(2 ** 100)

# On simule un registre de 8 bits : on ne garde que le reste modulo 256
print((200 + 100) % 256)

2.3 Addition binaire

On additionne colonne par colonne, avec retenue, comme en base $10$.

   1 1 1 1 1 1     (retenues)
   0 1 0 1 1 0 1   = 45
 + 0 0 1 1 0 1 1   = 27
 ---------------
   1 0 0 1 0 0 0   = 72

3. Les entiers relatifs : le complément à 2

3.1 Le problème du signe

Pour représenter des entiers négatifs, l'idée naïve est de réserver un bit de signe ($0$ pour $+$, $1$ pour $-$), suivi de la valeur absolue.

Elle a deux défauts : elle donne deux zéros ($+0$ et $-0$), et elle complique l'addition.

Les processeurs utilisent une autre représentation : le complément à 2.

3.2 Le principe

Sur $8$ bits, les poids sont donc $-128, 64, 32, 16, 8, 4, 2, 1$.

• $\overline{0010\,0101}^{\,2} = 32 + 4 + 1 = 37$
• $\overline{1101\,1011}^{\,2} = -128 + 64 + 16 + 8 + 2 + 1 = -37$

3.3 Calculer l'opposé

$37 = \overline{0010\,0101}^{\,2} \xrightarrow{\text{inversion}} \overline{1101\,1010}^{\,2} \xrightarrow{+1} \overline{1101\,1011}^{\,2} = -37.$

La même opération redonne $37$ à partir de $-37$.

def complement_a_2(x, n):
    """Motif sur n bits de l'entier relatif x (positif ou négatif)."""
    motif = bin(x % 2 ** n)[2:]          # x % 2**n vaut 2**n - |x| si x est négatif
    return "0" * (n - len(motif)) + motif

print(complement_a_2(37, 8))
print(complement_a_2(-37, 8))
print(complement_a_2(-202, 16))

Essaie les valeurs extrêmes sur $8$ bits : $127$, $-128$, puis $-1$. Que donne $128$, qui n'est pas représentable ?

3.4 Un même motif, deux lectures

Le motif $\overline{1101\,1011}^{\,2}$ vaut $219$ si on le lit comme un entier non signé, et $-37$ si on le lit comme un entier signé.

def valeur_signee(motif):
    n = int(motif, 2)
    # à toi : que faire si le bit de poids fort vaut 1 ?
    return n

4. Exemple résolu pas à pas

Vérifie tout cela en une fois :

print(bin(202), hex(202))
print(bin(202 + 202), bin(202 * 202))
print(hex(2 ** 16 - 202))
print(int("11110000", 2), int("11110000", 2) - 256)

À retenir