I. Les entiers positifs¶

Cours¶

Une machine n'utilise que des 0 et des 1. Il faut donc une méthode pour représenter n'importe quel nombre, avec uniquement ces 2 valeurs.

A. La base 10 (décimale)¶

Définitions

Elle est constituée de 10 chiffres, de 0 à 9, et chacun des chiffres utilisé a une valeur différente en fonction de sa position, nommée rang du chiffre. A chaque rang est associée une puissance de 10 différente.

Exemples

Prenons le nombre \(2005_{10}\) (la notation \(nombre_{10}\) indique que l'on considère sa représentation dans la base 10).

Rang Chiffre

3 2

2 0

1 0

0 5

On peut décomposer ce nombre de la manière suivante :

\(2005_{10} = 2\times10^3 + 0\times10^2 + 0\times10^1 + 5\times10^0 = 2000 + 5\)
Faire la même chose avec le nombre \(1990_{10}\).

Solution

\(1990_{10} = 1\times10^3 + 9\times10^2 + 9\times10^1 + 0\times10^0 = 1000 + 900 + 90\)

Qu'a-t-on fait pour décomposer ces nombres dans la base 10 ?

On a multiplié chacun de ses chiffres par \(10^{rang}\).

B. La base 2 (binaire)¶

Définition

La base binaire est constituée de 2 nombres : 0 et 1 (un bit), et est très utilisée en informatique.

B.1. Du binaire au décimal¶

Pour passer d'un nombre écrit en binaire à sa représentation en base décimale, on multiplie chaque chiffre par la puissance de 2 associée à son rang (comme pour la base décimale, mais avec 2 au lieu de 10).

Les puissances de 2 usuelles sont à connaître et/ou à savoir retrouver :

Puissance de 2	\(2^0\)	\(2^1\)	\(2^2\)	\(2^3\)	\(2^4\)	\(2^5\)	\(2^6\)	\(2^7\)	\(2^8\)	\(2^9\)	\(2^{10}\)
Valeur	1	2	4	8	16	32	64	128	256	512	1024

Exemples

Pour convertir \(1010_2\), remplir le tableau puis écrire sa décomposition en fonction des puissances de 2.

Rang	Chiffre
3
2
1
0

Solution

Rang	Chiffre
3	1
2	0
1	1
0	0

\(1010_2 = 1\times2^3 + 0\times2^2 + 1\times2^1 + 0\times2^0 = 8 + 2 = 10_{10}\)

Faire la même chose avec le nombre \(0110 0100_2\).

Solution

\(0110 0100_2 = 1\times2^6 + 1\times2^5 + 1\times2^2 = 64+32+4 = 80_{10}\)

B.2. Du décimal au binaire¶

Pour passer d'un nombre en écriture décimale à sa représentation en binaire, on utilise l'algorithme suivant : 1. On fait la division euclidienne ce nombre par 2 et on stocke le reste. 2. On remplace ce nombre par le quotient de sa division euclidienne par 2, et on revient à l'étape 1. 3. On s'arrête lorsque ce quotient devient 0. 4. Le nombre en représentation binaire se lit en associant les restes des divisions successives, en commençant par la dernière.

Exemple

On peut utiliser une autre méthode :

B.3. Nombre de bits nécessaires¶

Pour trouver le nombre de bits nécessaires pour représenter un nombre décimal, on cherche la puissance de 2 supérieure ou égale la plus proche de ce nombre. Le nombre de bits est donné par la puissance.

Exemple

Combien de bits faut-il pour représenter 9 ?

Solution

La puissance de 2 strictement supérieure est \(16 = 2^4\). Il faut donc 4 bits pour représenter 9 en binaire.

C. La base 16 (hexadécimale)¶

La base 2 est à la base du fonctionnement de l'informatique, mais son utilisation peut être laborieuse lorsque l'on veut manipuler des nombres relativement grands. On utilise alors la base 16, ou base hexadécimale.

Définition

La base hexadécimale est une base de 16 symboles, utilisant l'ensemble des chiffres de 0 à 9 pour coder ses 10 premiers éléments, et ensuite les lettres de A à F, représentant les nombres \(10_{10}\) à \(15_{10}\).

Base 10	Base 16
10	A
11	B
12	C
13	D
14	E
15	F

C.1. De l'hexadécimal au décimal¶

Pour passer d'un nombre écrit en hexadécimal à sa représentation décimale, on multiplie chaque chiffre par la puissance de 16 associée à son rang. Pour les lettres de A à F, on utilise le nombre correspondant dans la base 10 (voir le tableau ci-dessus).

Exemples

\(5_{16}\)

\(5_{16} = 5\times16^0 = 5_{16}\)

\(2A_{16}\)

\(2A_{16} = 2\times16^1 + 10\times16^0 = 32 + 10 = 42_{16}\)

\(1BF_{16}\)

\(1BF_{16} = 1\times16^2 + 11\times16^1 + 15\times16^0 = 256 + 176 + 15 = 447_{16}\)

C.2. Du décimal à l'hexadécimal¶

Pour passer d'un nombre en base 10 à sa représentation en base 16, on utilise le même algorithme que pour passer de la base 10 à la base 2, sauf que l'on divise successivement par 16.

Exemple

C.3. Hexadécimal et binaire¶

Cette base est facile d'utilisation de par sa relation avec la base binaire : il est facile de passer de l'une à l'autre. Pour représenter une valeur de 0 à 15, il faut 4 bits, donc pour représenter 1 octet on utilise 2 nombres en hexadécimal.

Pour passer de l'hexadécimal au binaire, on associe la représentation binaire de chacun de ses symboles.

Exemple

\(2A_{16} = 00101010_2\)

Pour passer du binaire à l'hexadécimal, on regroupe les bits par 4 (on ajoute des \(0\) si nécessaire) et on convertit chaque groupe dans sa représentation hexadécimale.

Exemple

\(10001110_{2} = 8E_{16}\)

Exercice

Pour représenter la couleur des pixels d'une image, on utilise des valeurs allant de 0 à 255 pour chacune des composantes rouge, vert et bleu (R, V, B).

Combien de bits faut-il pour représenter la valeur d'une composante ?

\(255 = 2^8-1\)
Il faut donc 8 bits pour représenter la valeur d'une composante.

Pourquoi est-il intéressant d'utiliser la base hexadécimale ?

Il est intéressant d'utiliser la base hexadécimale car il suffit de 2 valeurs pour représenter chaque composante R, V ou B.

D. Une base quelconque¶

Les principes de conversion entre les bases décimale, binaire et hexadécimale sont les mêmes pour les autres bases (base 5, 7, 18, ou pourquoi pas 666...). Chaque nombre est décomposable dans n'importe quelle base comme la somme des puissances de la base coefficientées.

Exemple : Représenter \(32_{10}\) en base 5.

TD : Représentation des entiers positifs¶

Exercice 1 : représentation binaire des chiffres¶

Calculer la représentation binaire de l'ensemble des chiffres de \(0_{10}\) à \(9_{10}\).

Exercice 2 : conversions binaire/décimal¶

Convertir en décimal :
- \(11_2\)
- \(101_2\)
- \(1010_2\)
- \(100111_2\)
Convertir en binaire, et vérifier que le résultat est correct :
- \(13_{10}\)
- \(18_{10}\)
- \(26_{10}\)

Exercice 3 : nombre de bits nécessaires à l'écriture d'un entier¶

Calculer la représentation décimale de l'entier représenté en binaire par \(1111\).
Calculer la représentation décimale de l'entier représenté en binaire par \(111111\).
Quelle est la valeur maximale représentable sur 4 bits ? Sur 6 bits ? (les exprimer avec des puissances de 2)
Comment peut-on généraliser pour \(n\) bits ?
En déduire combien de nombres sont représentables sur \(n\) bits.
Je considère le nombre \(35_{10}\). Comment savoir combien de bits est-ce qu'il faut utiliser pour le représenter en binaire ?

Exercice 4 : addition d'entiers positifs (attention à l'overflow !)¶

Pour faire la somme de nombres binaires, on utilise les règles suivantes :

Somme binaire
\(0_2+0_2 = 0_2\)
\(0_2+1_2 = 1_2\)
\(1_2 + 1_2 = 0_2\) et on retient \(1\)

Faire la somme des entiers binaires \(0100 1101_2\) et \(11000110_2\), et vérifier votre résultat en utilisant la base décimale.
En machine, si on utilise uniquement 1 octet pour représenter chaque entier, que se passerait-il lorsqu'on ferait l'addition de la question précédente ?
En pratique, il faut vérifier que l'on dispose de suffisamment de bits avant de faire l'addition de 2 entiers. Exprimer en fonction de \(n\) le nombre maximal de bits nécessaires pour faire l'addition de deux entiers de taille \(n\).

Exercice 5 : multiplication d'entiers positifs¶

Pour faire la multiplication de nombres binaires, on utilise les règles suivantes :

Multiplication binaire
\(0_2*0_2 = 0_2\)
\(0_2*1_2 = 0_2\)
\(1_2 *1_2 = 1_2\)

On procède de la même manière qu'avec le système décimal.
Par exemple, \(1100_2*1010_2=11000+1100000=1111000_2\)

Poser la multiplication de \(1010_2\) par \(1110_2\).
Sur combien de bits s'écrivent les résultats de ces deux exemples ?
Généraliser en fonction de \(n\), combien de bits sont nécessaire au maximum pour effectuer la multiplication de deux entiers positifs codés sur \(n\) bits.

Exercice 6 : représentation hexadécimale¶

Calculer la représentation hexadécimale de l'ensemble des nombres de \(0_{10}\) à \(20_{10}\).

Exercice 7 : conversions hexadécimal/décimal¶

Convertir en décimal :
- \(3_{16}\)
- \(1C_{16}\)
- \(2D_{16}\)
- \(B1_{16}\)
Convertir en hexadécimal :
- \(18_{10}\)
- \(75_{10}\)
- \(926_{10}\)

Exercice 8 : conversions hexadécimal/binaire¶

Convertir en hexadécimal :
- \(01000101_2\)
- \(11010000_2\)
Convertir en binaire :
- \(16_{16}\)
- \(A5_{16}\)

Exercice 9 : adresses IP (bonus)¶

Le format d'une adresse IPv4 est le suivant : a.b.c.d avec a, b, c et d des entiers allant de 0 à 255.
- Combien de bits faut-il pour représenter chacun de ces entiers ?
- A combien d'octets cela correspond-il en tout ?
- Représenter l'adresse suivante en écriture binaire : 192.168.10.1
Une adresse IPv6 est constituée de 8 champs de 4 valeurs hexadécimales, séparés par des ":". Par exemple, celle du serveur de facebook.com est : 2a03:2880:f145:82:face:b00c:0:25de.
- Combien de bits faut-il pour représenter chaque champ ?
- Combien de bits faut-il en tout pour écrire une adresse au format IPv6 ?