Représenter des entiers en machine : le système binaire #

pdf pour impression et diaporama

Binaire #

Différentes bases #

Dans la vie courante on utilise la base 10.

En informatique on rencontre d’autres manières de représenter les nombres :

• binaire
• complément à 2
• octal
• hexadécimal etc.
• nombres à virgules flottantes

Système de représentation par position #

Qu’on utilise la base 10, 2, 8, 16 ou autre, on emploie toujours la numération par position.

Représentation par position : La position d’un chiffre définit la valeur associée à ce chiffre.

Numération par position #

Exemple : En base 10 :

$345 = 3\times100 + 4\times10 + 5 = 3\times 10^2 + 4\times10^1+5\times10^0$

Le $3$ de $345$ représente donc $300$, le $4$ représente $40$ etc. On a pourtant $3 < 4$…

En binaire, on a deux chiffres. Chaque chiffre est un bit (=binary digit).

$0b1101 = 1 \times 2^3 + 1\times 2^2 + 0\times2^1 + 1\times2^0 = 13$

Afin d’indiquer une représentation binaire on utilise $0b$ avant le nombre ou $_2$ après le nombre :

$0b$

Les puissances de 2 #

Les puissances de 10 c’est facile : 1, 10, 100, 1000 etc. mais celles de 2 demandent un effort.

Conseil : retenez les par coeur en jouant à 2048.

Vocabulaire #

• bit : symbole 0 ou 1. Ce sont les chiffres de la représentation binaire.
• octet : bloc de 8 bits. La mémoire de l’ordinateur n’est pas capable de lire 1 bit à la fois. Elle répond avec des blocs d’un ou de plusieurs octets.
• byte : traduction anglaise de l’octet.

Par exemple : 2MB = 2 Mega Octets = $2 \times 10^6$ octets = $16\hspace{2mm}000\hspace{2mm}000$ bits.

Du binaire au décimal. #

Pour convertir un entier donné en binaire on le lit depuis la droite et on fait la somme.

$0b10011$ = 1 + 2 + 0 + 0 + 16 = 19.

Autre notation : $10011_2 = 19_{10}$

Autre exemple :

La représentation décimale de $0b101010$ est

$$1\times2^5+0\times2^4+1\times2^3+0\times2^2+1\times2^1+0\times2^0$$ $$=32+8+2$$ $$=42$$

Encore un :

$0b10011011 = 2^7 + 2^4+2^3+2^1+2^0 = 128 + 16 + 8 + 2 + 1 = 155$

Exercice 1 #

• Donnez les valeurs entières représentées par $0b0100$, $0b10101$, $0b101$, $0b0101$ et $0b00101$.

• Trier par ordre croissant $0b11$, $0b100$, $0b111$ et $0b1000$.

Du décimal au binaire. #

Deux algorithmes majeurs.

• Facile à programmer : les divisions successives.
• Facile de tête : soustraire des puissances de 2.

Décimal au binaire avec les puissances de 2. #

Écrire 57 en base 2 (=donner sa représentation binaire).

• $32<57<64$.

  Donc on fait $57 = 32 + 25 = 2^5 + 25$. On a un chiffre 1 à la position 6.

• $16<25<32$.

  Donc on fait $25 = 16 + 9 = 2^4 + 9$. On a un chiffre 1 à la position 5.

• $8<9<16$.

  Donc on fait $9 = 8 + 1 = 2^3 + 1$. On a un chiffre 1 à la position 4.

• $1=2^0$.

  On peut s’arrêter dès qu’on atteint une puissance de 2. On a un chiffre 1 à la position 1.

$$57 = 0b111001$$

En une ligne : $57 = 32 + 16 + 8 + 1 = 0b111001$

Autre exemple :

$$123 = 64 + 59 = 64 + 32 + 27$$ $$123 = 64 + 32 + 16 + 11$$ $$123 = 64 + 32 + 16 + 8 + 3$$ $$123 = 64 + 32 + 16 + 8 + 2 + 1$$

Donc

$$123 = 0b1111011$$

Du décimal au binaire avec les divisions successives #

Algorithme des divisions successives

1. On divise par 2 jusqu’à ce que le quotient soit 0
2. On lit les bits en montant de droite à gauche :

Pour nous, c’est plus facile, le diviseur est toujours 2 donc le reste est toujours 0 ou 1.

Dans $n : 2$, le reste est $0$ si $n$ pair et $1$ si $n$ est impair.

Donner la représentation binaire de 167.

167 = 0b10100111

Exercice 2 #

Quelle est la représentation binaire de 14 et 78 ?

Binaire en Python #

Python dérivant du langage C, les nombres en binaire sont notés 0bxxxx

Python converti naturellement un entier d’une base b vers le décimal avec int(nombre, b)

La conversion vers le binaire se fait avec bin et renvoie une chaîne de caractères.

>>> 0b111011
59
>>> a = '0b11'
>>> int(a, 2)
3
>>> b = 10
>>> bin(b)
'0b1010'

Faites bien attention :

• 0b111011 est un int qu’on a écrit sous forme binaire et dont la valeur est 59.
• "0b111011" est une str qu’on peut convertir en entier avec int.

Les nombres en mémoire #

ATTENTION En mémoire, ce sont des entiers encodés en binaire.

>>> 4 + 5
9

Ainsi, pour réaliser l’opération 4+5 Python converti d’abord en binaire, additionne puis converti en décimal pour afficher 9.

Taille d’un nombre en binaire #

Le nombre de bit d’un entier nous indique l’espace mémoire minimal qu’il faudra pour le stocker.

$123 = 0b1111011$ il faut au moins 7 bits pour stocker ce nombre.

En pratique, les machines utilisent des blocs de taille 1 octet (=8 bits), ce nombre entre dans un octet.

Taille et opérations #

Si $x$ occupe n bits et $y$ occupe p bits alors :

• SOMME : $x + y$ occupe au plus max(n, p) + 1 bits,
• PRODUIT : $x \times y$ occupe au plus n + p bits.

Nombre	$x$	$y$	$x+y$	$x\times y$
Nombre de bits	$n$	$p$	$\leq max(n, p) + 1$	$\leq n + p$

Le logarithme binaire #

En mathématique, la fonction $\ln$ pour logarithme népérien ou logarithme naturel est une fonction ayant d’importantes propriétés.

Rendue populaire par Napier, elle a permis de considérablement simplifier les calculs à la main.

Vous verrez en mathématiques qu’elle permet de transformer les produits en somme : $\ln (a \times b) = \ln a + \ln b$

Une de ses propriétés est de donner une mesure du nombre de chiffres d’un nombre dans une base :

Si $t$ est la taille de $x$ en base $b$ alors $$\frac{\ln(n)}{\ln(b)} \leq t < 1 + \frac{\ln(n)}{\ln(b)}$$

Pour nous, cela se traduit ainsi :

En notant $\log_2 (n) = \frac{\ln n}{\ln 2}$ et $\lceil x \rceil$ l’arrondi supérieur de $x$ :

Le nombre de bits d’un entier $n$ est $\lceil \log_2(x + 1) \rceil$.