Du décimal au binaire

Introduction du cours

Si je vous demandais comment représenter le nombre quarante-deux, qu'écririez-vous ? Nous avons l'habitude du système décimal, ainsi la réponse attendue est 42. Dans la mémoire de votre ordinateur, cependant, une information ne peut être représentée que comme une séquence de 0 et de 1. Comment peut-on alors y stocker le nombre quarante-deux ?

Il faut pour cela savoir jongler entre les systèmes décimal et binaire, c'est-à-dire entre un système utilisant dix chiffres et un autre en utilisant deux. Nous verrons également comment passer du binaire à l'hexadécimal (base 16) et à l'octal (base 8) et inversement, ce qui est intéressant parce que ces systèmes permettent une écriture plus compacte. La base correspond au nombre de chiffres qu'utilise un système de numération.

Nous verrons ici des méthodes pratiques pour passer d'une base à l'autre et nous les mettrons en œuvre de façon algorithmique. Nous justifierons ces méthodes en énonçant des résultats mathématiques. Le tout est rédigé de sorte que les personnes uniquement intéressées par l'aspect pratique puissent sauter les autres passages sans être pénalisées.

Notion de chiffreQu'est-ce qu'un chiffre ?

Tout nombre entier b ≥ 2 peut être utilisé comme base pour représenter des nombres. Pour pouvoir écrire des nombres en base b, il faut avant tout trouver b symboles différents. Chacun représentera un nombre compris entre zéro et b - 1. Ces symboles sont appelés des chiffres.

Pour peu que vous sachiez à quel nombre correspond chaque symbole, vous pourrez connaître l'entier représenté par une écriture en base b. Toutefois, si vous voulez vous faire comprendre, il est préférable d'utiliser les chiffres conventionnels, à savoir :

• en base 2, dans cet ordre, 0 et 1 ;

• en base 8, dans cet ordre, 0, 1, 2, 3, 4, 5, 6 et 7 ;

• en base 10, dans cet ordre, 0, 1, 2, 3, 4, 5, 6, 7, 8 et 9 ;

• en base 16, dans cet ordre, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E et F (A pour dix, B pour onze, C pour douze, etc.).

On voit un premier problème apparaître : si les bases ont des chiffres communs, comment savoir en quel base est écrit un nombre ? Quand vous écrivez dans une base autre que la base 10, il est important de bien le préciser, par exemple en l'indiquant en indice : $101010_2 = 52_8 = 42_{10} = 2A_{16}$.

Avant d'écrire des algorithmes

Vous pouvez sauter ce paragraphe si c'est uniquement l'aspect pratique qui vous intéresse.

En prévision des futurs algorithmes de conversion que nous étudierons, nous allons avoir besoin de deux fonctions que je vous invite à écrire dans votre langage préféré :

• chiffre(n) prendra en argument un nombre entier et retournera le chiffre qui lui est associé sous forme de caractère ;

• nombre(ch) prendra en argument un chiffre sous forme de caractère et retournera le nombre qui lui est associé.

Le résultat attendu est le suivant :

>>> chiffre(12) 'C' >>> nombre('C') 12

Exemple en Python :

# cette définition permet d'utiliser des bases b ≤ 36 # rajouter des symboles si besoin CHIFFRES = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" NOMBRES = {c : n for (n, c) in enumerate(CHIFFRES)} def chiffre(n): return CHIFFRES[n] def nombre(ch): return NOMBRES[ch] Lecture d'une représentation en base bApproche mathématique

Pour calculer l'entier représenté par une telle écriture, plaçons nous en base b : nous avons b chiffres représentant chacun un nombre entre 0 et b - 1. La notation $n = (c_p ... c_0)_b$ où les $c_i$ sont des chiffres est en fait un raccourci signifiant $n = n_p b^p + \dots + n_2 b^2 + n_1 b + n_0 = \sum_{i = 0}^p n_i b^i$ où $n_i$ est le nombre représenté par le chiffre $c_i$.

Pour mieux comprendre, revenons au nombre quarante-deux. Pour utiliser l'écriture binaire, nous allons avoir besoin des puissances de deux :
$\begin{matrix} 2^0 = 1 & 2^1 = 2 & 2^2 = 4 & 2^3 = 8 & 2^4 = 16 & 2^5 = 32 & 2^6 = 64 & 2^7 = 128 & 2^8 = 256 & \dots \end{matrix}$

Vérifions que $101010_2 = 52_8 = 42_{10} = 2A_{16}$ :

• $42_{10} = 4 \times 10 + 2 = 42$ donc 42 est bien l'écriture décimale de quarante-deux ;

• on a bien $52_8 = 5 \times 8 + 2 = 42$ ;

• d'autre part $2A_{16} = 2 \times 16 + 10 = 42$ ;

• enfin $101010_2 = 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 1 \times 2 + 0 = 32 + 8 + 2 = 42$.

Ça y est, nous savons calculer un nombre connaissant son écriture binaire, voire octale ou hexadécimale !

Première application algorithmique

Vous pouvez sauter ce paragraphe si c'est uniquement l'aspect pratique qui vous intéresse.

Pour vérifier que vous avez bien compris, essayez d'écrire dans votre langage préféré une fonction lire_repr(rep, b) qui prenne en argument une chaîne de caractères représentant un nombre écrit en en base b ainsi que la base en question et qui retourne ce nombre sous la forme d'un entier. Vous utiliserez la fonction nombre(ch) précédemment définie.

Pour nos calculs, nous avons noté $n = (c_p ... c_0)_b$. Or les langages de programmation usuels utilisent des indices dans le sens inverse, de 0 à p. Faites bien attention à ce détail.

Le résultat attendu est le suivant :

>>> lire_repr("2A", 16) 42

Exemple en Python :

def lire_repr(rep, b): nb_chiff = len(rep) somme = 0 b_puiss_i = 1 for i in range(nb_chiff): c_i = rep[nb_chiff - i - 1] somme = somme + nombre(c_i) * b_puiss_i b_puiss_i = b_puiss_i * b return somme

On calcule la somme terme par terme. Quelques commentaires :

• l'appel len(rep) retourne la longueur de la chaîne ;

• on utilise une boucle faisant évoluer trois variables :

  • i qui varie de 0 à nb_chiff - 1 ;

  • somme qui contient la somme des termes que l'on a calculés jusqu'ici ;

  • b_puiss_i qui est égal à $b^i$ ;

• il faut faire attention aux indices comme le montre la ligne surlignée.

Dans la plupart des langages, cette fonction est disponible dans la bibliothèque standard et/ou des notations permettent de rentrer directement des nombres en hexadécimal et/ou en octal et/ou en binaire. Renseignez-vous sur le vôtre. Dans le cas de Python :

>>> 0x2A, 0o52, 0b101010 # hexadécimal, octal, binaire (42, 42, 42) >>> int("2A", 16), int("52", 8), int("101010", 2) # base quelconque (42, 42, 42) Application pratique

Notre calcul revient à calculer la valeur du polynôme $n = n_p X^p + \dots + n_2 X^2 + n_1 X + n_0 = \sum_{i = 0}^p n_i X^i$ au point b.
Pour le faire plus efficacement, on peut appliquer la méthode dite de Horner, comme suit.

Prenons $n = n_p b^p + n_{p-1} b^{p-1} + \dots + n_1 b + n_0$.

On peut l'écrire sous la forme $n = (( \dots ((n_p b + n_{p-1}) b + n_{p-2}) b + \dots) b + n_1) b + n_0$.

En faisant les calculs dans cet ordre, on obtient n sans avoir à calculer les puissances de b.

Par exemple $101010_2 = ((((1 \times 2 + 0) \times 2 + 1) \times 2 + 0) \times 2 + 1) \times 2 + 0 = 42$ avec un simple calcul mental.

Nouvelle application algorithmique

Vous pouvez sauter ce paragraphe si c'est uniquement l'aspect pratique qui vous intéresse.

Cette méthode est très intéressante d'un point de vue algorithmique parce qu'elle simplifie considérablement notre code. Essayez de réécrire la fonction lire_repr(rep, b) dans votre langage préféré en appliquant la méthode de Horner.

Exemple en Python :

def lire_repr(rep, b): n = 0 for ch in rep: n = n * b + nombre(ch) return n

On parcourt la chaîne caractère par caractère en faisant évoluer un nombre n. Après la lecture du premier caractère n sera égal au nombre représenté par ce caractère, c'est bien ce que l'on veut donc l'initialisation de n à zéro convient.

Avançons un peuReprésentation en base b

Le résultat mathématique fondamental qui permet de justifier notre écriture est le suivant :

Citation : Représentation en base b

Fixons un nombre entier b ≥ 2 qu'on appellera base (b = 2, 8, 10 ou 16 en pratique).
Alors tout nombre entier n > 0 peut se décomposer dans cette base :
il existe une unique famille de nombres entiers $n_0, \dots, n_p$ tels que
$n = n_p b^p + \dots + n_2 b^2 + n_1 b + n_0 = \sum_{i=0}^p{n_i b^i}$
avec $0 \le n_i \le b - 1$ pour tout i et $n_p \ne 0$.
On écrit ce nombre $n = (c_p \dots c_0)_b$ où $c_i$ est le chiffre représentant le nombre $n_i$ en base b.

Ouf ! Nous pouvons donc utiliser notre système sans problème. Deux informations primordiales se cachent dans cet énoncé :

• tout entier a une écriture en base b ;

• il y a unicité d'une telle écriture.

Quelques commentaires :

• le nombre zéro est un cas particulier qui n'est pas concerné par ce résultat, on le note 0 dans toutes les bases ;

• la condition $0 \le n_i \le b - 1$ signifie que chaque $n_i$ peut être représenté par un chiffre en base b ;

• la condition $n_p \ne 0$ signifie que le chiffre le plus à gauche n'est pas 0, ce qui est nécessaire pour assurer l'unicité de la décomposition car $42_{10} = 042_{10} = 0042_{10}$ ;

• en binaire, le chiffre $c_i$ est appelé bit de poids i (bit : contraction de binary digit, c'est-à-dire chiffre binaire en anglais) ;

• on parle de bit de poids fort ou MSB (Most Significant Bit) pour désigner le bit de poids maximal, ici $c_p$ ;

• on parle de bit de poids faible ou LSB (Least Significant Bit) pour désigner le bit de poids minimal, ici $c_0$.

Tout le problème est maintenant de savoir comment calculer les $n_i$ à partir du nombre n pour en déduire les $c_i$. Comme il y a unicité de la décomposition, il suffit d'en trouver une qui convient. Nous verrons deux méthodes pratiques pour y arriver.

Nombre de nombres à q chiffres

Un autre résultat intéressant est le suivant :

Citation : Nombre de nombres à q chiffres

On peut écrire $b^q$ nombres à q chiffres en base b, les chiffres de poids fort étant éventuellement nuls. Ce sont les nombres de 0 à $b^q - 1$.

Autrement dit en base 2 :

• avec trois bits, on peut écrire les nombres de 0 à 7, il y en a 8 ;

• avec quatre bits, on peut écrire les nombres de 0 à 15, il y en a 16 ;

• avec un octet, c'est-à-dire huit bits, on peut écrire les nombres de 0 à 255, il y en a 256.

Codage par divisions successivesApproche mathématique

Si les maths vous donnent des crises d'angoisse, vous pouvez directement passer à l'application pratique.

Pour cette méthode, nous allons utiliser la division euclidienne.

Citation : Division euclidienne de a par b

Soit a ≥ 0 et b > 0. Alors il existe un unique quotient q ≥ 0 et un unique reste r ≥ 0 avec r < b tels que $a = b q + r$.

Trois choses importantes cette fois : l'existence, l'unicité et le fait que r soit strictement inférieur à b.

Prenons un nombre n.
Nous savons qu'il s'écrit $n = n_p b^p + \dots + n_2 b^2 + n_1 b + n_0 = \sum_{i=0}^p{n_i b^i}$ avec $0 \le n_i \le b - 1$ pour tout i et $n_p \ne 0$.
Nous voulons déterminer les $n_i$.

En factorisant par b, on obtient $n = b (n_p b^{p-1} + \dots + n_2 b + n_1) + n_0$.
Posons $q = n_p b^{p-1} + \dots + n_2 b + n_1 = \sum_{i=1}^{p}{n_i b^{i-1}}}$ et $r = n_0$.
En remplaçant, on a $n = bq + r$ avec r < b !

Ainsi par unicité de la division euclidienne de n par b

• le reste de cette division est $r = n_0$ ;

• le quotient est $q = n_p b^{p-1} + \dots + n_2 b + n_1 = \sum_{i=1}^{p}{n_i b^{i-1}}} = \sum_{i=0}^{p-1}{n_{i+1} b^i}}}$.

Ce quotient est un nombre comme un autre, nous pouvons le décomposer dans la base b.

Mieux encore, nous connaissons déjà son écriture en base b !
En effet, on peut écrire que $q = n'_{p-1} b^{p-1} + \dots + n'_1 b + n'_0 = \sum_{i=0}^{p-1}{n'_i b^i}}}$ en posant $n'_i = n_{i+1}$.
Autrement dit, si $n = (c_p \dots c_0)_b$ alors $q = (c_p \dots c_1)_b$ et $r = (c_0)_b$ où q et r sont respectivement le quotient et le reste de la division euclidienne de n par b.

Application pratiqueMéthode générale

Si vous ne savez pas (ou plus :-° ) comment faire une division euclidienne, je vous invite à consulter ce lien, vous en aurez besoin.

Prenons un nombre n s'écrivant $n = (c_p \dots c_0)_b$ en base b.

On peut alors montrer qu'en divisant n par b

• le reste est $r = (c_0)_b =...