Écrire un entier naturel

Base binaire

On a vu dans l'activité qu'étant donné une base $b$, on peut représenter n'importe quel entier comme la somme de puissances de $b$ multipliées par des entiers inférieurs à $b$.

Base de représentation

La base de représentation est la valeur $b$ choisie pour décomposer un nombre lors de son écriture.

L'écriture en base $b$ d'un nombre $n$ sera uniquement composée de chiffres inférieurs à $b$.

Ainsi, si 1534 est écrit en base 10 ce nombre correspond à la valeur $1 \times 10^3 + 5 \times 10^2 + 3 \times 10^1 + 4 \times 1 = 1534$. Par contre, si 1534 est écrit en base 8, ce nombre correspond à la valeur $1 \times 8^3 + 5 \times 8^2 + 3 \times 8^1 + 4 \times 1 = 860$.

Par convention, pour dire qu'un nombre est écrit dans la base $b$ on écrira : 1534_b, ainsi : 1534₁₀ désigne la quantité 1534 mais 1534₈ représente 860.

En informatique, tout les nombres sont représentés en binaire (base 2).

Bit

Un bit (binary digit) est un chiffre qui peut valoir 0 ou 1, c'est l'unité fondamentale de mesure de l'information.

Octet

Un octet est une suite de 8 bits, on travaillera le plus souvent avec des valeurs encodées sur des octets entiers.

Exemples à faire

Quel est la valeur de : 101₁₀ ? 101₄ ? 101₂ ? Est ce que 100010119 est une valeur correcte en binaire ? Combien y a a-t-il de bits dans ce nombre : 1001 0011 1111 0111₂ ? D'octets ?

En python, on a accès à la représentation binaire et aux conversions via quelques fonctions:

🐍 Script Python

    0b1010 # Le nombre représenté par 1010 en binaire
    0b... # permet d'écrire un nombre en binaire directement
    int("10234",6) # donne la valeur de 10234 en base 6
    int(suite_chiffre,b) # donne la valeur de la suite de chiffre dans la base b
    bin(n) # donne la représentation binaire de n

Du binaire au décimal

Les 10 premiers chiffres binaires sont :

Décimal	Binaire
0	0
1	1
2	10
3	11
4	100
5	101
6	110
7	111
8	1000
9	1001

Que remarque t on sur l'écriture des entiers pairs ? Impairs ?

Les entiers pairs s'écrivent avec un 0 comme dernier chiffre. Les entiers impairs eux, s'écrivent avec un 1 comme dernier chiffre

Quels sont les nombres s'écrivant comme un 1 suivi par des 0 en base 2 ? Et en base 10 ?

Les puissances de 2 : $1_2 = 2^0,10_2 = 2^1, 100_2 = 2^2, 1000_2 = 2^3$ En base 10, ce sont les puissances de 10 : 1₁₀,10₁₀,100₁₀,1000₁₀

Base hexadécimale

La base hexadécimale ou base 16 est la deuxième base la plus utilisée en informatique. On la retrouve sur le web pour représenter les couleurs, ainsi que dans la programmation système ou bas niveau.

Elle permet de facilement représenter de grands nombres binaires, avec peu de chiffres.

Base hexadécimale

La base 16 utilise 16 chiffres, comme les chiffres décimaux ne vont que jusqu'à 9, on leur ajoute les lettres: A,B,C,D,E,F, qui vont représenter les valeurs de 10 à 15.

On peut écrire les lettres en majuscules ou minuscules, sans distinction.

Convertissez les nombres 9₁₆, D₁₆ et 11₁₆ en décimal

$9_{16} = 9 \times 16^0 =$

On a un lien très simple entre la base 2 et la base 16, du au fait que $16 = 2^4$.

Écrivez les nombre 9F₁₆, 9₁₆ et F₁₆ en binaire.

Le nombre 9F₁₆ s'écrit comme les nombres 9₁₆ et F₁₆ collés en binaire. Soit : 9₁₆ = 1001₂, F₁₆ = 1111₂, 9F₁₆ = 1001 1111₂. Il prend 8 bits, donc 1 octet.

On peut donc remarquer qu'un nombre hexadécimal s'écrit sur un octet, mais est-ce toujours le cas ?

Faites de même pour 52₁₆ ? À quoi faut il faire attention ?

52₁₆ s'écrit : 0101 0010₂ On doit bien ajouter des 0 pour faire 4 bits pour chaque chiffre hexadécimal

Conversion binaire depuis hexadécimal:

Pour convertir un nombre hexadécimal en binaire, il suffit d'écrire chaque chiffre hexadécimal sur 4 bits, dans l'ordre. On peut faire cela car $16 = 2^4$, c'est une base puissance de la base binaire.

La correspondance entre les trois bases est la suivante:

Décimal	Binaire	Hexadécimal
0	0000	0
1	0001	1
2	0010	2
3	0011	3
4	0100	4
5	0101	5
6	0110	6
7	0111	7
8	1000	8
9	1001	9
10	1010	A
11	1011	B
12	1100	C
13	1101	D
14	1110	E
15	1111	F

Écrivez 66₁₆, 5F₁₆ et 11₁₆ en binaire.

• 66₁₆ s'écrit: 0110 0110
• 5F₁₆ s'écrit: 0101 1111
• 11₁₆ s'écrit: 0001 0001

Devoir ?

Sans calculer leur valeur décimale, comment écrire les nombres suivants en hexadécimal:

• 1111₂ =
• 1000₂ =
• 1111 1000₂ =
• 1010 0110₂ =
• 1110 0111 1100₂ =

Conversion binaire vers hexadécimal:

Pour convertir un nombre en binaire vers de l'hexadécimal, on groupe ses bits par 4 en partant de la droite, puis on convertit chaque groupe de 4 bits en un chiffre hexadécimal.

De même que pour le binaire, l'hexadécimal est assez répandu pour avoir ses propres écritures en python:

🐍 Script Python

    0x5D # Le nombre représenté par 5D en hexadécimal
    0x5d # Le même nombre
    0x... # permet d'écrire un nombre en hexadécimal directement
    int("ABC1E",16) # donne la valeur de ABC1E en base 16
    hex(n) # donne la représentation hexadécimale de la valeur n

Devoir ?

Dans la fiche suivante, faites les exercices 2,4,5.1 et 6.

Base décimale

On a l'habitude d'écrire nos nombres en base 10. Pour passer à l'écriture dans une autre base on peut utiliser l'algorithme des divisions successives:

Algorithme des divisions successives:

Pour décomposer un entier dans une base, on le divise par la base jusqu’à avoir un quotient nul. La suite des restes obtenus est alors la représentation du nombre dans la base donnée. On effectue donc l'algorithme suivant:

1. Soit $n$ le nombre dont on veut la représentation dans la base $b$.
2. On calcule le quotient et le reste dans la division entière de $n$ par $b$ soit : $n = q \times b + r$ avec $r < b$
3. On recommence avec $n \leftarrow q$, tant que $n$ n'est pas nul.
4. La suite des restes obtenus est alors la représentation de $n$ dans la base $b$.

Représentation de 25 en base 2

Division	$n$	Représentation
$25 = 12 \times 2 + 1$	$n$ devient 12	"...1"
$12 = 6 \times 2 + 0$	$n$ devient 6	"...01"
$6 = 3 \times 2 + 0$	$n$ devient 3	"...001"
$3 = 1 \times 2 + 1$	$n$ devient 1	"...1001"
$1 = 0 \times 2 + 1$	$n$ devient 0	"...11001"

$n$ est nul, donc on s'arrête. Donc 25₁₀ s'écrit 11001₂, on peut l'écrire sur un octet comme : 0001 1001₂

Algorithme des soustractions successives:

Pour décomposer un entier dans une base, on lui soustrait la plus grande puissance de deux possible. Si on peut soustraire $2^n$, alors on écrit un 1 à la $n$-ième position, puis on recommence avec la différence obtenue.

On effectue donc l'algorithme suivant:

1. Soit $n$ le nombre dont on veut la représentation dans la base $b$.

2. On trouve le plus grand $k$ tel que $2^k \leq n$

3. On le soustrait à $n$ et on recommence avec le nouveau nombre

4. La suite des nombres soustraits donne les coefficients de la décomposition en base 2.

Représentation de 25 en base 2:

Puissance inférieure	$n$	Représentation
$16 < 25$ et $32 > 25$	$25$ devient $25-16=9$	$16+...$
$8 < 9$ et $16 > 9$	$9$ devient $9-8=1$	$16+8+...$
$1 \leq 1$ et $2 > 1$	$1$ devient $1-1=0$	$16+8+1$

$n$ est nul, donc on s'arrête. Donc 25₁₀ s'écrit $16+8+1 = 1 \times 2^4 + 1 \times 2^3 + 1 \times 2^0 = 11001_2$, on peut l'écrire sur un octet comme : 0001 1001₂

Utilisez ces algorithmes pour calculer la représentation de 13 et 38 en base 2

On applique notre algorithme:

$8 < 13 < 16 \rightarrow 13 - 8 = 5$.

$4 < 5 < 8 \rightarrow 5 - 4 = 1$.

$1 \le 1 < 2 \rightarrow 1 - 1 = 0$.

Donc $13 = 8 + 4 + 1 = 1101_2$

$32 < 38 < 64 \rightarrow 38 - 32 = 6$.

$4 < 6 < 8 \rightarrow 6 - 4 = 2$.

$2 \le 2 < 4 -> 2 - 2 = 4$

Donc $38 = 32 + 4 + 2 = 100110_2$

Taille d'entiers

Un octet ne permet pas de stocker tout les nombres possibles, seulement les nombres de 0 à 255. Lorsque l'on cherche à stocker un nombre qui ne rentre pas dans un octet, on a un phénomène dit d'overflow, de l'information est perdue.

Pour remédier ce phénomène, on utilise plusieurs octets pour stocker les entiers. La question est alors: Combien faut il de bits (d'octets) pour représenter un entier donné ?

Questions

Quels entiers peut on écrire avec 4 bits ? 8 bits ?

Avec 4 bits, on peut écrire les entiers de 0000₂ à 1111₂ soit 0₁₀ à 15₁₀. Avec 8 bits, on peut écrire les entiers de 00₁₆ à FF₁₆ soit 0₁₀ à 255₁₀

Encadrer la taille d'un entier, sans calculer sa représentation

Pour un entier $n$ donné, il faut autant de bits pour le stocker, que pour stocker la plus petite puissance de 2 immédiatement supérieure.

Ainsi, pour évaluer la taille en binaire de 57, on doit trouver $k$ tel que $2^{k-1} < n \leq 2^{k}$. Pour 57, on sait que $32 < 57 \leq 64$ soit $2^5 < 57 \leq 2^6$, donc il faudra 6 bits pour représenter 57.

Combien faut il de bits pour représenter 1₁₀ ? 7₁₀ ? 15₁₀ ?1023₁₀ ?

1,3,4,10

Complétez ceci pour 1,3,$n$ octets

Nombre d'octets	Nombre de bits	Nombre d'entiers stockables	Maximum
1	8	$2^8$	$2^8-1$
3
n

Pour chaque intervalle, on peut stocker un nombre minimum (0) et un nombre maximum, qui correspond à mettre tout les bits à 1.

Nombres binaire de la forme : 1111...

Le plus grand nombre binaire représentable sur $n$ bits est celui où les $n$ bits sont à 1.

Ce nombre vaut $1 + 2 ... + 2^{n-1} = 2^n - 1$ Pourquoi ?

Extremums:

Avec $k$ bits, on peut stocker les nombres de 0 à $2^k-1$ On peut donc stocker $2^k$ nombres sur $k$ bits.

Problème: Si on additionne deux entiers, combien faut il de bits pour stocker le résultat ?

Pour répondre, essayons sur deux entiers : 3 et 2 puis 8 et 6, écrivez les en binaires, puis leur somme en binaire

$3 + 2 = 5 = 101_2, 3 = 11_2, 2 = 10_2$

et pour 8 et 6

$8 + 6 = 14 = 1110_2, 8 = 1000_2, 6 = 110_2$

Ici, additionner deux entiers de taille 2 crée un entier de taille 3, mais additionner un entier de taille 4 et un de taille 3 donne un entier de taille 4.

Taille de la somme:

Soit $n,p$ deux entiers encodés en binaire, de même taille $t$.

Leur somme demandera au maximum $t+1$ bits pour être stockée.

Démonstration

Le plus grand nombre codable sur $t$ bits est $2^t-1$. La plus grande somme possible de nombres sur $t$ bits est donc $2^t-1 + 2^t-1=$

$2 \times ( 2^t - 1 )=$

$2 \times 2^{t} - 2=$

$2^{t+1} -2$.

comme $2^{t} < 2^{t+1} - 2 < 2^{t+1}$, il faut $t+1$ bits pour le stocker.

De la même manière, on peut calculer la taille maximale du produit de deux entiers codés sur $t$ bits.

Taille du produit:

Soit $n,p$ deux entiers encodés en binaire, de même taille $t$.

Leur somme demandera au maximum $2 \times t$ bits pour être stockée.

Démonstration

Le plus grand nombre codable sur $t$ bits est $2^t-1$. Le plus grand produit possible de nombres sur $t$ bits est donc $(2^t-1) \times (2^t-1)=$

$( 2^t - 1 )^2=$

$(2^t)^2 - 2 \times (2^t) \times 1 + (-1)^2=$

$2^{2 \times t} - 2^{t + 1} + 1=$

or $2^{2 \times t -1} < 2^{2 \times t} - 2^{t + 1} + 1 < 2^{2 \times t}$ il faut donc $2 \times t$ bits pour le stocker au maximum.

Opérations sur les entiers

Ici on décrit les opérations en base 2 et 10, mais la même logique s'applique pour la base 16. Il vous suffit de mettre la retenue quand la somme est supérieure ou égale à 16 et non à 10 ou 2.

Addition

On sait poser une addition en base 10 avec des retenues.

📋 Texte

     1 5
 + 1 9 8
 --------
   2 1 3

Pour poser une addition en binaire on exécute exactement les mêmes opérations, sauf que la retenue arrive dès que l'on dépasse 1

Multiplication

Pour la multiplication, on peut aussi la poser comme en base 10 et les retenues sont effectuées de la même façon.

📋 Texte

       1 1 = 3
   * 1 0 1 = 5
   -------
       1 1 = 3
+    0 0 0 = + 0
+  1 1 0 0 = + 12
 ---------
   1 1 1 1 = 15 = 3 * 5

Le décalage

On a remarqué que les entiers 100... sont toutes les puissances de 2, on va maintenant observer l'opération qui consiste à ajouter des 0 devant un nombre binaire.

Comment passer de 11₁₀ à 1100₁₀ ? de 23₁₀ à 2300₁₀ ?

On ajoute 2 zéros à droite, ce qui correspond à multiplier par 100.

Si ajouter 4 zéros multiplie par $2^4$, que fait on quand on ajoute 5 zéros ? 8 zéros ? $n$ zéros ?

Comme en base 10, cela permet de multiplier par $2^n$.

Décalage de bits:

Lorsqu'on ajoute $k$ zéros à droite d'un nombre écrit en binaire, on le multiplie par $2^k$. En règle générale, ajouter $k$ zéros à droit d'un nombre écrit en base $b$ le multiplie par $b^k$. C'est pour cela que les nombres de la forme $100..._b$ correspondent aux puissances de $b$.