Écriture d’un entier positif dans une base b >= 2

Système décimal ou base 10

Dans le système décimal que l'on utilise tous les jours, les nombres sont écrit à l'aide des 10 chiffres bien connus : 0, 1, 2, 3, 4, 5, 6, 7, 8 et 9.

C'est la position d'un chiffre dans un nombre qui indique son importance, ou poids, dans ce nombre. Par exemple, le nombre qui s'écrit 2083 est égal à 2 milliers plus 8 dizaines plus 3 unités. Il n'est pas égal au nombre 8320, même s'il s'écrit avec les mêmes chiffres 0, 2, 8 et 3.

Tout nombre entier naturel peut s’écrire comme combinaison linéaire de puissance de 10. Par exemple, les chiffres du nombre 2083 correspondent à :

chiffre	2	0	8	3
i	3	2	1	0
\(10^i\)	\(10^3\)	\(10^2\)	\(10^1\)	\(10^0\)
combinaison	\(2 \times 10^3\)	\(0 \times 10^2\)	\(8 \times 10^1\)	\(3 \times 10^0\)

\(2083 = 2 \times 10^3 + 0 \times 10^2 + 8 \times 10^1 + 3 \times 10^0\)

De manière générale, un nombre \(n\) qui s'écrit dans le système décimal avec \(p\) chiffres \(d_{p−1}d_{p−2}...d_2d_1d_0\) (chaque \(d_i\) est un chiffre valant entre 0 et 9)¹ est égal à :

\(n = d_{p−1} \times 10^{p−1} + d_{p−2} \times 10^{p−2} + ... + d_2 \times 10^2 + d_1 \times 10^1 + d_0 \times 10^0\)

ou encore avec la formule mathématique d'une somme de \(0\) à \(p-1\) : \(n = \sum_{i=0}^{p-1} d_i × 10^i\)

Noter qu'on peut écrire 10 nombres allant de 0 à 9 avec 1 seul chiffre, 100 nombres allant de 0 à 99 avec 2 chiffres, 1000 nombres allant de 0 à 999 avec 3 chiffres, ... \(10^p\) nombres allant de 0 à \(10^p-1\) avec \(p\) chiffres.

Quand on ajoute un chiffre 0 à droite d'un nombre \(n\), tous les chiffres sont décalés vers la droite, les puissances de 10 correspondantes sont augmentées d'une unité, donc le nombre \(n\) est multiplié par 10.

Réciproquement, on peut écrire chacun des chiffres d'un nombre décimal \(n\) qui s'écrit dans le système décimal avec \(p\) chiffres \(d_{p−1}d_{p−2}...d_2d_1d_0\) par un algorithme simple qui consiste à effectuer une succession de divisions entières par 10 :

L'opérateur de division entière // et l’opération modulo % utilisés avec des entiers (de type int) donnent respectivement le quotient et le reste d'une division euclidienne : si a et b sont des entiers tels que \(a = b \times q + r\), alors a // b renvoie \(q\) et a % b renvoie \(r\).

Le reste de la division entière de \(n\) par \(10\), n % 10 en Python, renvoie \(d_0\). Cela permet d'obtenir le dernier chiffre de l'écriture décimale de \(n\).
Le quotient de la division entière de \(n\) par \(10\), n // 10 en Python, renvoie \(d_{p−1}d_{p−2}...d_2b_1\). On remplace \(n\) par ce nombre pour trouver les autres chiffres.

Il suffit alors de répéter l'opération jusqu'à ce que \(n\) soit égal à 0, on aura bien obtenu tous les chiffres de l'écriture décimale de \(n\).

Prenons l'exemple du nombre \(n = 2083\), le reste de la division entière par 10 est 3 et le quotient 208.

Divisions euclidiennes successives de 2083 par 10

>>> 2083 % 10
3
>>> 2083 // 10
208

On a déjà trouvé le dernier chiffre : 3. Continuons avec 208. Le reste de la division entière de 208 par 10 est 8 et le quotient 20.

Divisions euclidiennes successives de 2083 par 10

>>> 208 % 10
8
>>> 208 // 10
20

On obtient le 8. Continuons avec 20. Le reste de la division entière de 20 par 10 est 0 et le quotient 2.

Divisions euclidiennes successives de 2083 par 10

>>> 20 % 10
0
>>> 20 // 10
2

On obtient le 0. Continuons avec 2. Le reste de la division entière de 2 par 10 est 2 et le quotient 0.

Divisions euclidiennes successives de 2083 par 10

>>> 2 % 10
2
>>> 2 // 10
0

On a obtenu le dernier chiffre 2. Le quotient est 0, inutile de continuer les divisions, tous les chiffres ont été trouvés.

Divisions euclidiennes successives de 2083 par 10

Noter qu'on a obtenu les chiffres de l'écriture décimale de 2083, mais de gauche à droite, il faut donc les lire de droite à gauche pour retrouver 2083.

On peut traduire cet algorithme en Python, par exemple pour écrire une fonction etoile qui renvoie une chaîne de caractère composées de tous les chiffres d'un nombre entier n suivis d'une étoile.

def etoile(n):
    n_etoile = ''
    while n > 0:
        n_etoile =  str(n % 10) + '*' + n_etoile
        n = n // 10
    return n_etoile

>>> etoile(2083)
'2*0*8*3*'

On note que le cas ou n est égal à 0, la fonction n'entre pas dans la boucle while et renvoie une chaîne vide. On peut traiter le cas séparément en ajoutant les lignes :

def etoile(n):
    if n == 0:
        return '0*'
    n_etoile = ''
    while n > 0:
        ...

Exercice corrigé

Un nombre harshad, ou nombre de Niven, est un entier naturel qui est divisible par la somme de ses chiffres dans une base donnée [...]. En base dix, les vingt premiers nombres harshad strictement supérieurs à 10 sont (suite A005349 de l'OEIS) : 12, 18, 20, 21, 24, 27, 30, 36, 40, 42, 45, 48, 50, 54, 60, 63, 70, 72, 80 et 81. Source : https://fr.wikipedia.org/wiki/Nombre_harshad.

Écrire un programme demande un nombre entier et affiche s'il est un nombre harshad ou pas.

Réponse

n = int(input())
n_initial = n
somme = 0
while n > 0:
    somme = somme + n % 10
    n = n // 10
if n_initial % somme == 0:
    print(n_initial, "est un nombre de harshad")
else:
    print(n_initial, "n'est pas un nombre de harshad")

Système binaire ou base 2

Cours

En binaire, ou base 2, les seuls chiffres utilisés pour écrire des nombres sont 0 et 1, aussi appelés « bits » pour binary digits, ou « chiffres binaires » en français.

8 bits forment un octet.

Par exemple on peut écrire \(1101\), que l'on note aussi \(1101_2\), pour indiquer qu'il est écrit en binaire.

Il convient également de ne pas lire ces nombres comme on lirait des nombres décimaux. Ainsi, \(1101_2\) ne se dit pas « mille cent un » mais plutôt « un un zéro un ».

Comme dans le système décimal, c'est la position qui indique le poids de chaque bit dans un nombre. Mais en binaire, c'est une combinaison linéaire de puissances de 2. Par exemple, les bits du nombre \(1101_2\) correspondent à :

bits	1	1	0	1
i	3	2	1	0
\(2^i\)	\(2^3=8\)	\(2^2=4\)	\(2^1=2\)	\(2^0=1\)
combinaison	\(1 \times 2^3=8\)	\(1 \times 2^2=4\)	\(0 \times 2^1=0\)	\(1 \times 2^0=1\)

\(1101_2 = 1 × 2^3 + 1 × 2^2 + 0 × 2^1 + 1 × 2^0 = 13_{10}\)

Noter le \(..._{10}\) pour indiquer que \(13\) est un nombre en base 10.

Cours

De manière générale, un nombre \(n\) qui s'écrit dans le système binaire avec \(p\) bits \(b_{p−1}b_{p−2}...b_2b_1b_0\) (chaque \(b_i\) est un bit valant 0 ou 1) a une valeur décimale égale à :

\(n = b_{p−1} \times 2^{p−1} + b_{p−2} \times 2^{p−2} + ... + b_2 \times 2^2 + b_1 \times 2^1 + b_0 \times 2^0\)

ou encore avec la formule mathématique d'une somme de \(0\) à \(p-1\) : \(n = \sum_{i=0}^{p-1} b_i × 2^i\)

Écrire un nombre binaire en décimal

La formule précédente permet d'écrire facilement un nombre binaire en décimal. Il suffit de multiplier chaque bit par la puissance de 2 correspondante et de faire la somme des valeurs obtenues.

Énumérons les premiers nombres binaires et quelques autres :

binaire	combinaison	décimal
\(0\)	0	0
\(1\)	\(1 \times 2^0\)	1
\(10\)	\(1 \times 2^1\)	2
\(11\)	\(1 \times 2^1 + 1 \times 2^0\)	3
\(100\)	\(1 \times 2^2\)	4
\(101\)	\(1 \times 2^2 + 1 \times 2^0\)	5
\(110\)	\(1 \times 2^2 + 1 \times 2^1\)	6
\(111\)	\(1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0\)	7
\(1000\)	\(1 \times 2^3\)	8
\(1 \space 0000\)	\(1 \times 2^4\)	16
\(10 \space 0000\)	\(1 \times 2^5\)	32
\(100 \space 0000\)	\(1 \times 2^6\)	64
\(1000 \space 0000\)	\(1 \times 2^7\)	128
\(1111 \space 1111\)	\(1 \times 2^8 + 1 \times 2^7 + 1 \times 2^6 +...1 \times 2^0\)	255

Exercice corrigé

Calculer la valeur décimale des nombres binaires suivants :

11010
10101
11100110

Réponse

\(11010_2 = 1 \times 2^4 + 1 \times 2^3 + 1 \times 2^1 = 16 + 8 + 2 = 26_{10}\)

\(1 \space 0101_2 = 1 \times 2^4 + 1 \times 2^2 + 1 \times 2^0 = 16 + 4 + 1= 21_{10}\)

\(1110 \space 0110_2 = 1 \times 2^7 + 1 \times 2^6 + 1 \times 2^5 + 1 \times 2^2 + 1 \times 2^1 = 128 + 64 + 32 + 4 + 2=230_{10}\)

Traduisons cela en Python. Pour plus de simplicité, on peut parcourir le nombre binaire de gauche à droite.

def bin_to_dec(n):
    """ str -> int
    Renvoie l'écriture décimale de la chaine de caractère n représentant un nombre binaire
    """
    dec = 0
    for i in range(len(n)):
        dec = dec + int(n[-i-1]) * 2**i
    return dec

En Python, les nombres binaires s'écrivent avec le préfixe 0b et l'équivalent en décimal est affiché automatique dans la console :

>>> 0b1101
13

Écrire un nombre décimal en binaire

Il existe plusieurs méthodes pour écrire un nombre décimal en binaire :

Trouver les puissances de 2 est la méthode la plus simple qui aide à comprendre la structure du binaire, mais elle est peu utilisée en pratique.
Effectuer des divisions successives par 2 est pratique pour un calcul algorithmique.
Utiliser une fonction Python.

Trouver les puissances de 2

On peut faire l'opération inverse de l'écriture d'un nombre binaire en décimal en essayant de retrouver la combinaison linéaire de puissances de 2 d'un nombre binaire.

Cherchons pas exemple, l'écriture binaire du nombre \(13_{10}\). Il faut remplir le tableau des puissances de 2 suivant :

i	4	3	2	1	0
\(2^i\)	\(2^4=16\)	\(2^3=8\)	\(2^2=4\)	\(2^1=2\)	\(2^0=1\)
binaire	?	?	?	?	?

On pourrait commencer par remplir le tableau à droite, du côté des petites puissances de 2 : \(2^0 = 1\)

i	4	3	2	1	0
\(2^i\)	\(2^4=16\)	\(2^3=8\)	\(2^2=4\)	\(2^1=2\)	\(2^0=1\)
binaire	?	?	?	?	1

Puis on continue : \(2^0 + 2^1 = 1+2=3\)

i	4	3	2	1	0
\(2^i\)	\(2^4=16\)	\(2^3=8\)	\(2^2=4\)	\(2^1=2\)	\(2^0=1\)
binaire	?	?	?	1	1

Et encore : \(2^0 + 2^1 + 2^2 = 1+2+4=7\)

i	4	3	2	1	0
\(2^i\)	\(2^4=16\)	\(2^3=8\)	\(2^2=4\)	\(2^1=2\)	\(2^0=1\)
binaire	?	?	1	1	1

Mais quand on arrive là, on est coincé ! La puissance suivante est \(2^3 = 8\), c'est trop grand pour obtenir \(13\) et toutes les autres puissances seront encore plus grande.

Il faut donc procéder dans l'autre sens, en partant de la gauche, du côté des grandes puissances².

\(2^4 = 16\), c'est plus grand que \(13\), on ne peut pas prendre le bit correspondant, on met 0 !

i	4	3	2	1	0
\(2^i\)	\(2^4=16\)	\(2^3=8\)	\(2^2=4\)	\(2^1=2\)	\(2^0=1\)
binaire	0	?	?	?	?

\(2^3 = 8\), c'est plus petit que \(13\), on met 1 pour le bit correspondant. Il reste \(13-8=5\) à trouver.

i	4	3	2	1	0
\(2^i\)	\(2^4=16\)	\(2^3=8\)	\(2^2=4\)	\(2^1=2\)	\(2^0=1\)
binaire	0	1	?	?	?

\(2^2 = 4\), c'est plus petit que \(5\), on met 1 pour le bit correspondant. Il reste \(5-4=1\) à trouver.

i	4	3	2	1	0
\(2^i\)	\(2^4=16\)	\(2^3=8\)	\(2^2=4\)	\(2^1=2\)	\(2^0=1\)
binaire	0	1	1	?	?

\(2^1 = 2\), c'est plus grand que \(1\), on ne peut pas prendre le bit correspondant, on met 0.

i	4	3	2	1	0
\(2^i\)	\(2^4=16\)	\(2^3=8\)	\(2^2=4\)	\(2^1=2\)	\(2^0=1\)
binaire	0	1	1	0	?

\(2^0 = 1\), c'est le dernier bit que l'on cherchait, on met 1.

i	4	3	2	1	0
\(2^i\)	\(2^4=16\)	\(2^3=8\)	\(2^2=4\)	\(2^1=2\)	\(2^0=1\)
binaire	0	1	1	0	1

On a bien trouvé l'écriture binaire de \(13_{10}\), c'est \(1101_2\).

Voilà l'algorithme que l'on a suivi :

On repère la plus grande puissance de 2 plus petite ou égale au nombre.
On soustrait, puis on continue avec le reste.
On met 1 si la puissance est utilisée, 0 sinon.

Exercice corrigé

Compléter le tableau pour écrire \(22_{10}\) et \(29_{10}\) en binaire :

i	4	3	2	1	0
\(2^i\)	\(2^4=16\)	\(2^3=8\)	\(2^2=4\)	\(2^1=2\)	\(2^0=1\)
\(22_{10}\)
\(29_{10}\)

Réponse

i	4	3	2	1	0
\(2^i\)	\(2^4=16\)	\(2^3=8\)	\(2^2=4\)	\(2^1=2\)	\(2^0=1\)
\(22_{10}\)	1	0	1	1	0	\(= 10110_2\)
\(29_{10}\)	1	1	1	0	1	\(= 11101_2\)

C'est une méthode simple et intuitive, mais en pratique elle est inefficace et peu utilisée, en particulier pour les grands nombres, car elle consiste à calculer et garder en mémoire de nombreuses puissances de 2 inutiles.

Effectuer des divisions successives par 2

De la même manière qu'on a utilisée précédemment pour trouver les chiffres en base 10 d'un nombre par une succession de divisions entières par 10, on peut écrire un nombre décimal \(n\) sous sa forme binaire \(b_{p−1}b_{p−2}...b_2b_1b_0\) en effectuant des divisions entières par 2 :

Le reste de la division entière de \(n\) par \(2\), n % 2 en Python, renvoie \(b_0\). Cela permet d'obtenir le dernier bit de l'écriture binaire de \(n\).
Le quotient de la division entière de \(n\) par \(2\), n // 2 en Python, renvoie \(b_{p−1}b_{p−2}...b_2b_1\). On remplace \(n\) par ce nombre pour trouver les autres bits.

Il suffit alors de répéter l'opération jusqu'à ce que \(n\) soit égal à 0, on aura bien obtenu tous les bits de l'écriture binaire de \(n\).

Attention, on obtient les bits de la gauche vers la droite.

Prenons l'exemple de \(n_{10} = 13\), le reste de la division entière par 2 est 1 et le quotient 6.