Représenter les entiers

Cours complet · NSI (première), chapitre 1 · première, spécialité numérique et sciences informatiques

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

« Toute machine informatique manipule une représentation des données dont l'unité minimale est le bit 0/1, ce qui permet d'unifier logique et calcul. » — Programme de NSI, rubrique Représentation des données : types et valeurs de base

Une machine ne sait pas ce qu'est le nombre douze. Elle sait mettre un fil sous tension ou l'y laisser, aimanter une plage de disque dans un sens ou dans l'autre, laisser passer un courant ou le bloquer. Deux états, rien de plus. Tout le reste — les entiers, les textes, les images, les sons — se construit sur ce choix binaire, et ce chapitre construit le premier étage : les entiers.

1.1 Compter dans une base quelconque

1.1.1 Ce que veut dire « écrire un nombre »

Écrire $2043$ en base dix, c'est décider que le chiffre le plus à droite compte les unités, son voisin les dizaines, le suivant les centaines : $2043 = 2 \times 1 0^{3} + 0 \times 1 0^{2} + 4 \times 1 0^{1} + 3 \times 1 0^{0}$ . La base dix n'a rien de nécessaire ; elle vient de nos dix doigts. Remplaçons dix par un entier $b \geq 2$ quelconque, et le mécanisme tient encore.

Définition 1.1Écriture en base

b

Soit $b \geq 2$ un entier. Écrire l'entier $n \geq 1$ en base $b$ , c'est le donner sous la forme

$n = a_{k} b^{k} + a_{k - 1} b^{k - 1} + \dots + a_{1} b + a_{0},$

où les chiffres $a_{i}$ sont des entiers vérifiant $0 \leq a_{i} < b$ , et où le chiffre de poids fort $a_{k}$ est non nul. On note cette écriture $a_{k} a_{k - 1} \dots a_{1} a_{0}^{b}$ .

◆Théorème 1.2Existence et unicité de l'écriture

Pour tout entier $b \geq 2$ et tout entier $n \geq 1$ , il existe une écriture de $n$ en base $b$ , et une seule.

Ce théorème dit une chose simple, qu'il vaut la peine de voir écrite : dans une écriture positionnelle, ce n'est pas le chiffre seul qui compte, mais le chiffre et sa place.

Figure : L'écriture positionnelle en base

b

. Chaque position porte une puissance de

b

— son poids — et le nombre est la somme des chiffres multipliés par leur poids.

Démonstration

Existence. Procédons par divisions euclidiennes successives. Posons $n_{0} = n$ , puis tant que $n_{i} > 0$ , écrivons la division euclidienne $n_{i} = b n_{i + 1} + a_{i}$ avec $0 \leq a_{i} < b$ . La suite $(n_{i})$ est strictement décroissante d'entiers positifs — car $n_{i + 1} = ⌊ n_{i} / b ⌋ < n_{i}$ dès que $n_{i} \geq 1$ et $b \geq 2$ — donc elle atteint $0$ en un nombre fini d'étapes. En remontant les substitutions, on obtient bien $n = \sum a_{i} b^{i}$ .

Unicité. Supposons deux écritures d'un même $n$ . Le chiffre $a_{0}$ est le reste de la division de $n$ par $b$ : il est donc déterminé de façon unique. En retranchant $a_{0}$ et en divisant par $b$ , on est ramené au même problème pour $⌊ n / b ⌋$ , strictement plus petit. Une descente finie conclut.

La démonstration ne fait pas que prouver : elle donne l'algorithme. Les restes successifs de divisions par $b$ sont les chiffres, lus de droite à gauche.

Capacité attendue

« Passer de la représentation d'une base dans une autre. »

1.1.2 De la base $b$ vers la base dix

Le sens facile. On applique la définition — mais pas naïvement. Écrire $a_{k} b^{k} + \dots + a_{0}$ en calculant chaque puissance $b^{i}$ séparément coûte cher ; on préfère factoriser :

$a_{3} b^{3} + a_{2} b^{2} + a_{1} b + a_{0} = ((a_{3} b + a_{2}) b + a_{1}) b + a_{0} .$

Cette réécriture s'appelle le schéma de Horner. Elle transforme le calcul en une seule boucle : partir de zéro, et pour chaque chiffre lu de gauche à droite, multiplier par $b$ puis ajouter le chiffre.


CHIFFRES = "0123456789ABCDEF"

def depuis_base(s, b):
    """Valeur de l'entier écrit s en base b (2 <= b <= 16).

    Précondition : s ne contient que des chiffres valides en base b.
    """
    n = 0
    for c in s:
        n = n * b + CHIFFRES.index(c)
    return n

Exemple 1.3Lecture pas à pas

Calculons depuis_base("1011", 2). La variable n vaut successivement $0$ , puis $1$ , puis $2$ , puis $5$ , puis $11$ . On retrouve bien $101 1_{2} = 8 + 0 + 2 + 1 = 11$ .

1.1.3 De la base dix vers la base $b$

Le sens que donne la démonstration : diviser, garder le reste, recommencer sur le quotient. Les restes sortent dans l'ordre inverse de l'écriture, d'où la construction de la chaîne par la gauche.


def vers_base(n, b):
    """Écriture de l'entier n >= 0 en base b (2 <= b <= 16), sous forme de chaîne."""
    if n == 0:
        return "0"
    s = ""
    while n > 0:
        s = CHIFFRES[n % b] + s
        n = n // b
    return s

Figure : Conversion de

214

en base deux par divisions successives. Le dernier reste obtenu est

le premier chiffre écrit : c'est pourquoi la fonction vers_base construit la chaîne par la gauche.</div>

Attention

Le cas $n = 0$ est traité à part, et ce n'est pas un caprice : la boucle while n > 0 ne s'exécute jamais pour $n = 0$ et renverrait la chaîne vide. C'est le genre d'oubli qu'un jeu de tests bien choisi attrape immédiatement — nous y reviendrons au chapitre 3.

Méthode : Vérifier une conversion sans refaire le calcul

Convertir dans un sens puis dans l'autre doit redonner le point de départ. Sur machine : depuis_base(vers_base(n, b), b) == n doit être vrai pour tout $n$ et tout $b$ admissibles. Cette propriété — deux fonctions inverses l'une de l'autre — vaut mieux qu'une vérification à la main, parce qu'elle se teste sur des milliers de valeurs.

1.2 Les trois bases qui comptent

Le programme privilégie explicitement les bases $2$ , $10$ et $16$ . Ce n'est pas un appauvrissement : ce sont les seules qu'on rencontre en pratique, et la troisième n'existe que pour servir la première.

1.2.1 La base deux

Un seul chiffre binaire s'appelle un bit — de l'anglais binary digit. Un groupe de huit bits forme un octet.

En base deux, les poids sont les puissances de deux : lire un octet ne demande donc aucun calcul, seulement une addition des poids des bits allumés.

Figure : Les huit poids d'un octet. Lire

1101011 0_{2}

, c'est additionner les poids des bits à

1

128 + 64 + 16 + 4 + 2 = 214

1.2.2 La base seize, ou l'art d'abréger le binaire

L'écriture binaire est fidèle à la machine, mais illisible pour l'humain : un octet demande huit caractères. La base seize résout ce problème par une coïncidence heureuse, $16 = 2^{4}$ :

Proposition 1.4Regroupement par paquets de quatre

Pour convertir un nombre du binaire vers l'hexadécimal, il suffit de découper son écriture binaire en paquets de quatre bits en partant de la droite, et de remplacer chaque paquet par le chiffre hexadécimal correspondant. La conversion inverse remplace chaque chiffre hexadécimal par ses quatre bits.

Démonstration

Un paquet de quatre bits en position $i$ (en comptant les paquets depuis la droite, à partir de $0$ ) représente une valeur $v_{i}$ avec $0 \leq v_{i} \leq 15$ , pesant $2^{4 i} = 1 6^{i}$ . La somme $\sum v_{i} 1 6^{i}$ est donc exactement l'écriture en base seize, et les $v_{i}$ en sont les chiffres.

Exemple 1.5Un octet, trois écritures

$D 1101 60110 ⟶ D6_{16} ⟶ 13 \times 16 + 6 = 214.$

Huit caractères en binaire, deux en hexadécimal, pour la même information. C'est pourquoi les couleurs d'une page Web, les adresses mémoire et les empreintes de fichiers s'écrivent en hexadécimal — nous les retrouverons au chapitre 10.

Figure : Un octet se lit en hexadécimal par paquets de quatre bits, pris depuis la droite.

Huit caractères deviennent deux, sans le moindre calcul.</div>

iRemarque

Python sait lire et écrire ces trois bases sans qu'on programme quoi que ce soit : bin(214) donne '0b11010110', hex(214) donne '0xd6', et int("D6", 16) redonne 214. Écrire soi-même vers_base n'était donc pas utile à la machine : c'était utile à vous.

Repère historique : Leibniz, 1703

L'arithmétique binaire n'est pas née avec les ordinateurs. En 1703, Leibniz publie dans les Mémoires de l'Académie royale des sciences une « Explication de l'arithmétique binaire » où il expose le calcul en base deux avec les seuls caractères $0$ et $1$ . Il y voit d'abord une curiosité philosophique et arithmétique ; il faudra attendre les premières machines, deux siècles et demi plus tard, pour que ce choix devienne celui de toutes les machines à calculer.

Le programme demande que ces repères soient « construits au fur et à mesure de la présentation des concepts » : vous en trouverez donc un dans chaque chapitre, jamais un chapitre entier.

1.3 Combien de bits faut-il ?

Capacité attendue

« É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. »

1.3.1 Pour un entier

Proposition 1.6Capacité de

n

bits

Avec $n$ bits, on écrit exactement les $2^{n}$ entiers de $0$ à $2^{n} - 1$ .

Démonstration

Chacun des $n$ bits vaut $0$ ou $1$ indépendamment des autres : il y a donc $2^{n}$ écritures possibles. Elles représentent des entiers deux à deux distincts par l'unicité de l'écriture en base deux, et la plus grande, $11 \dots 1^{2}$ , vaut $\sum_{i = 0}^{n - 1} 2^{i} = 2^{n} - 1$ .

Réciproquement, le nombre de bits de l'écriture de $n \geq 1$ est le nombre de fois qu'on peut diviser $n$ par deux avant d'atteindre zéro, c'est-à-dire $⌊ lo g_{2} n ⌋ + 1$ .


def nb_bits(n):
    """Nombre de bits de l'écriture binaire de n >= 0 (0 s'écrit sur 1 bit)."""
    if n == 0:
        return 1
    k = 0
    while n > 0:
        n = n // 2
        k = k + 1
    return k

Exemple 1.7Les tailles courantes

Taille	Valeurs	Plus grand entier positif
8 bits (1 octet)	$256$	$255$
16 bits	$65536$	$65535$
32 bits	$\approx 4, 3 \times 1 0^{9}$	$4294967295$
64 bits	$\approx 1, 8 \times 1 0^{19}$	$18446744073709551615$

1.3.2 Pour une somme et pour un produit

Proposition 1.8

Soient $a$ et $b$ deux entiers strictement positifs, écrits respectivement sur $p$ et $q$ bits. Alors :

$a + b$ s'écrit sur au plus $max (p, q) + 1$ bits ;
$a \times b$ s'écrit sur $p + q - 1$ ou $p + q$ bits.

Démonstration

Écrire $a$ sur $p$ bits signifie $2^{p - 1} \leq a < 2^{p}$ , et de même pour $b$ .

Somme. On a $a + b < 2^{p} + 2^{q} \leq 2^{m a x (p, q) + 1}$ , donc $a + b$ tient sur $max (p, q) + 1$ bits.

Produit. D'une part $ab < 2^{p} \times 2^{q} = 2^{p + q}$ , donc au plus $p + q$ bits. D'autre part $ab \geq 2^{p - 1} \times 2^{q - 1} = 2^{p + q - 2}$ , donc au moins $p + q - 1$ bits.

Figure : L'addition binaire se pose comme en base dix : seule la table change. Ici, le résultat

demande sept bits alors que les deux opérandes en demandaient six — c'est le bit de plus annoncé par la proposition.</div>

Important

Retenez l'ordre de grandeur, il servira souvent : additionner coûte un bit, multiplier coûte le total des deux. C'est la raison pour laquelle multiplier deux entiers de 32 bits demande un résultat de 64 bits — et pourquoi un langage qui ne le prévoit pas produit silencieusement un résultat faux.

1.4 Les entiers relatifs : le complément à deux

Rien dans ce qui précède ne permet d'écrire $- 5$ . Il faut donc une convention. La plus naïve consiste à réserver un bit pour le signe — et elle est mauvaise : elle donne deux zéros, $+ 0$ et $- 0$ , et elle oblige le processeur à traiter l'addition différemment selon les signes. Les machines emploient un autre codage.

Capacité attendue

« Utiliser le complément à 2. »

Définition 1.9Complément à deux sur

n

bits

Sur $n$ bits, on représente les entiers $x$ tels que $- 2^{n - 1} \leq x < 2^{n - 1}$ de la façon suivante :

$on e ˊ crit en binaire sur n bits la valeur {x x + 2^{n} si x \geq 0, si x < 0.$

Exemple 1.10Sur 8 bits

$5$ s'écrit 00000101. Pour $- 5$ , on code $- 5 + 256 = 251$ , soit 11111011. Le plus petit entier représentable, $- 128$ , se code $128 =$ 10000000 ; le plus grand, $127$ , se code 01111111.

Figure : Les 256 configurations d'un octet, lues en complément à deux. En ajoutant

1

127

ne trouve pas $128$ — qui n'existe pas ici — mais $- 128$ .</div>

Proposition 1.11Le bit de poids fort donne le signe

Dans ce codage sur $n$ bits, un nombre est négatif si et seulement si son bit de poids fort vaut $1$ .

Démonstration

Si $0 \leq x < 2^{n - 1}$ , l'écriture de $x$ tient sur $n - 1$ bits : le bit de poids fort est nul. Si $- 2^{n - 1} \leq x < 0$ , alors $2^{n - 1} \leq x + 2^{n} < 2^{n}$ : la valeur codée est au moins $2^{n - 1}$ , donc son bit de poids fort vaut $1$ .

◆Théorème 1.12L'addition ne change pas

Si $x$ , $y$ et $x + y$ sont tous trois représentables sur $n$ bits, alors le codage de $x + y$ s'obtient en additionnant les codages de $x$ et de $y$ comme s'il s'agissait d'entiers positifs, puis en ignorant l'éventuelle retenue sortante.

C'est tout l'intérêt du codage, et il mérite d'être vu sur un cas : la retenue qui sort du dernier bit est simplement perdue, et cette perte est exactement ce qui réalise le calcul modulo $2^{n}$ .

Figure :

5 + (- 5)

sur huit bits. Les deux codages s'additionnent comme des entiers positifs ; la retenue sortante disparaît, et il reste bien

0

Démonstration

Notons $c (x)$ le codage de $x$ . Par définition, $c (x) \equiv x (mod 2^{n})$ , et de même pour $y$ . Donc $c (x) + c (y) \equiv x + y \equiv c (x + y) (mod 2^{n})$ . Ignorer la retenue sortante, c'est précisément réduire modulo $2^{n}$ . Les deux membres étant dans $[0, 2^{n} [$ , ils sont égaux.

Important

C'est là tout l'intérêt du procédé, et la raison pour laquelle toutes les machines l'emploient : un seul circuit additionneur suffit, il n'a pas à savoir si ses opérandes sont positifs ou négatifs. La soustraction elle-même devient une addition.


def complement_a_2(x, n):
    """Codage de x sur n bits en complément à 2, sous forme de chaîne de n bits.

    Précondition : -2**(n-1) <= x < 2**(n-1).
    """
    assert -2**(n - 1) <= x < 2**(n - 1), "x n'est pas representable sur n bits"
    if x < 0:
        x = x + 2**n
    return vers_base(x, 2).rjust(n, "0")


def depuis_complement_a_2(s):
    """Entier relatif codé par la chaîne de bits s, en complément à 2."""
    v = depuis_base(s, 2)
    if s[0] == "1":
        v = v - 2**len(s)
    return v

AttentionLe débordement

L'hypothèse du théorème compte : $x + y$ doit lui aussi être représentable. Sur 8 bits, $100 + 100 = 200$ n'est pas représentable, puisque le maximum est $127$ . Le calcul machine donne 11001000, dont le bit de poids fort vaut $1$ : la machine lit $- 56$ . Additionner deux nombres positifs a produit un négatif. Ce phénomène s'appelle un débordement, et il ne provoque aucune erreur : le résultat est simplement faux.

Hors programme : Ce que le programme n'exige pas

Le programme demande d'utiliser le complément à deux, pas d'en démontrer la théorie complète ni de connaître les jeux d'instructions des processeurs. De même, seules les bases $2$ , $10$ et $16$ sont au programme : la virtuosité en base sept ne sera demandée nulle part.

1.5 Et en Python ?

iRemarqueDes entiers sans limite de taille

Tout ce chapitre décrit ce que fait une machine avec un nombre fixé de bits. Python, lui, manipule des entiers de taille arbitraire : il alloue autant de mémoire que nécessaire, et 2**1000 se calcule exactement. Vous ne rencontrerez donc pas de débordement en Python sur les entiers.

Ne concluez pas que le problème n'existe pas. Il existe partout ailleurs — dans un processeur, dans un fichier, dans un échange réseau, dans la plupart des autres langages — et il a causé des pannes célèbres. Python vous protège ; il ne vous dispense pas de comprendre.

Piste de projet : Un visualiseur de représentations

Écrire un programme qui, pour un entier saisi par l'utilisateur et une taille en bits choisie, affiche côte à côte : son écriture décimale, binaire, hexadécimale, son codage en complément à deux, le nombre de bits strictement nécessaires, et un avertissement s'il n'est pas représentable. Une extension naturelle : animer l'addition bit à bit, avec les retenues, et signaler visuellement le débordement.

Ce sujet mobilise les deux chapitres suivants (interface, jeux de tests) et se prête bien à un groupe de deux.

Continuer sur Adloun : animation, QCM, fiches, exercices

Représenter les entiers

1.1 Compter dans une base quelconque

1.1.1 Ce que veut dire « écrire un nombre »

Capacité attendue

1.1.2 De la base b vers la base dix

1.1.3 De la base dix vers la base b

Méthode : Vérifier une conversion sans refaire le calcul

1.2 Les trois bases qui comptent

1.2.1 La base deux

1.2.2 La base seize, ou l'art d'abréger le binaire

Repère historique : Leibniz, 1703

1.3 Combien de bits faut-il ?

Capacité attendue

1.3.1 Pour un entier

1.3.2 Pour une somme et pour un produit

1.4 Les entiers relatifs : le complément à deux

Capacité attendue

Hors programme : Ce que le programme n'exige pas

1.5 Et en Python ?

Piste de projet : Un visualiseur de représentations

1.1.2 De la base $b$ vers la base dix

1.1.3 De la base dix vers la base $b$