Représentation des données : types et valeurs de base - les entiers
1 - Les entiers positifs
Écriture d'un entier positif dans une base b ≥ 2
Si \(x = a_n \times b^n + a_{n-1} \times b^{n-1} + ... + a_2 \times b^2 + a_1 \times b^1 + a_0 \times b^0\)
où les \(a_i\) sont des chiffres entre 0 et \(b-1\) alors \(a_n a_{n-1}... a_2 a_1 a_0\) est l'écriture en base \(b\) de \(x\).
Exemple en base 10:
\(4097 = 4 \times 10^3 + 0 \times 10^2 + 9 \times 10^1 + 7 \times 10^0\)
Codage en base 2
\(42 = 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0\)
Donc l'écriture en base 2 de 42 est 101010
On peut calculer l'écriture en binaire avec la fonction Python bin.
bin(42)
On peut aussi directement saisir un nombre en binaire en préfixant son
écriture par 0b.
0b101010
- Combien de nombres et quels nombres entiers peut-on coder avec 8 bits, 16 bits, 32 bits, 64 bits ?
Activité débranchée
Comptage en base 2 sur 8 bits avec 1 élève par bit.
| Elève 7 | Elève 6 | Elève 5 | Elève 4 | Elève 3 | Elève 2 | Elève 1 | Elève 0 |
|---|---|---|---|---|---|---|---|
| 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Selon sa position, chaque élève "vaut" \(1, 2, 4, 8... 128\).
Chaque élève peut avoir le bras levé (1) ou baissé (0). Chaque élève change la position de son bras quand son voisin de gauche baisse le sien. L'élève 0 réagit aux signaux du professeur et change de position à chaque signal.
Voir Computer science unplugged
Algorithme de conversion en binaire par suite de divisions
En divisant le nombre par la base, on obtient comme premier reste, le nombre d'unités. Si on recommence, on obtient les chiffres suivants de l'écriture en base \(b\).
Exemple en base 2
42 / 2 -> 21 reste 0
21 / 2 -> 10 reste 1
10 / 2 -> 5 reste 0
5 / 2 -> 2 reste 1
2 / 2 -> 1 reste 0
1 / 2 -> 0 reste 1
On obtient le code en écrivant les restes de gauche à droite à partir du dernier reste obtenu.
- Activité : écrire cette fonction avec une boucle
while.
L'utiliser pour mesurer le nombre de bits en fonction du nombre à coder.
Conversion de binaire en entier
Pour retrouver le nombre entier codé à partir de son code en base 2, il est inutile de calculer toutes les puissances de 2 et d'additionner les valeurs de chaque bit.
L'algorithme de conversion repose sur la factorisation suivante :
\(1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0\)
\(=\)
\(((((((1) \times 2)+0) \times 2+1) \times 2+0) \times 2+1) \times 2+0\)
L'algorithme consiste à prendre le premier bit du code (dans l'ordre naturel de lecture de gauche à droite) puis à multiplier par 2 et ajouter le bit suivant, puis à recommencer ce calcul jusqu'au dernier bit. On peut aussi - pour simplifier - partir de 0 et commencer le calcul avec le 1er bit.
def bin2int (s):
pass
bin2int('101010')
Codage en base 16
Pour coder un nombre en base 16, on a besoin de 16 chiffres :
L'avantage de la base 16 réside dans sa facilité de conversion de et vers la base 2. Un chiffre en base 16 remplace 4 bits (chiffres en base 2).
On peut expérimenter en Python le codage en base 16 grace à la fonction hex.
hex(2238)
On peut aussi directement saisir un nombre en base 16 en préfixant son écriture par 0x.
0x8BE
On peut alors vérifier la conversion par groupe de 4 bits entre base 16 et base 2.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
bin(0x8BE)