Représenter les entiers

Cours · NSI (première), chapitre 1 · première, spécialité numérique et sciences informatiques · le début du chapitre, la suite sur Adloun

La représentation binaire d'un entier : 1 fois 64, plus 1 fois 32, plus 1 fois 4, plus 1 fois 1 donne 101.

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

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

Exercices du chapitre

La suite du cours · Tous les exercices du chapitre