Écriture binaire d'un entier

Les exercices de cette feuille sont à traiter sans machine. Il s'agit de maîtriser le sens d'une écriture binaire.

Du binaire au décimal.

  1. Donner l'écriture décimale de l'entier a = 101010deux.
  2. Donner l'écriture décimale de l'entier a = 100deux.
  3. Quels sont les entiers qui s'écrivent (en base 2) sous la forme d'un 1 suivi uniquement de chiffres 0 ?

Résolution de l'exercice "Du binaire au décimal".

  1. a = 101010deux = 0⨯20 + 1⨯21 + 0⨯22 + 1⨯23 + 0⨯24 + 1⨯25 d'où a=42.
  2. a = 100deux= 0⨯20 + 0⨯21 + 1⨯22. On a donc a=4.
  3. Ce sont les puissances de 2.

Du décimal au binaire.

Déterminer l'écriture binaire des entiers suivants (donnés par leur écriture en base dix) par des divisions en cascade.

  1. n1= 17
  2. n2=25

Résolution de l'exercice "Du décimal au binaire".

n1= 17

quotient dans la division par 2 reste dans la division par 2Division
8117 = 2⨯ 8+ 1
408 = 2⨯ 4 +0
204 = 2⨯ 2+0
102 = 2⨯ 1+0
011 = 2⨯ 0 + 1
D'où l'écriture binaire de 17 : 17 = 10001deux. Ce que vous pouvez confirmer à l'aide de python : 
print( bin(17) )
0b10001

n2= 25

quotient dans la division par 2 reste dans la division par 2Division
12125 = 2⨯ 12+ 1
6012 = 2⨯ 6+ 0
306 = 2⨯ 3+ 0
113 = 2⨯ 1+ 1
011 = 2⨯ 0+ 1
D'où l'écriture binaire de 25 : 25 = 11001deux. Ce que python confirme : 
print( bin(25) )
0b11001

Justifier la terminaison des cascades.

Soit n un entier naturel. On lui applique l'algorithme des divisions en cascade avec la base 2. 


Entrée     : un entier n.
Traitement : a ← n
             tant que a est non nul :
                 r ← reste de la division de a par 2
                 a ← quotient de la division de a par 2
Sortie     : les valeurs successives de r

Justifier que l'algorithme se terminera nécessairement, c'est à dire que l'on obtiendra nécessairement un quotient nul lors d'une étape de l'algorithme.

Résolution de l'exercice "Justifier la terminaison des cascades".

Lorsqu'on divise un entier non nul n par 2, on obtient un quotient strictement plus petit que n.

Si l'on note q0=n l'entier de départ, puis q1, q2, q3... les quotients successifs dans l'algorithme, on a donc q0>q1>q2>q3>...

Supposons qu'il n'y ait pas de quotient nul dans cette suite. Alors on peut continuer indéfiniment les divisions et on obtient une suite infinie d'entiers q0, q1, q2, q3... tous différents et tous compris entre 1 et n. Ceci est évidemment impossible : il n'existe pas une infinité d'entiers distincts entre 1 et n. L'algorithme aboutit donc nécessairement à un quotient nul lors d'une étape, ce qui prouve la terminaison de l'algorithme des divisions en cascade.

Remarques :

  1. Cette preuve de la terminaison montre également l'affirmation du cours : "tout entier naturel possède une écriture binaire."
  2. L'argument utilisé (argument de la "descente infinie") est spécifique aux entiers. Si les nombres utilisés étaient des réels, l'argument ne serait pas valable : entre 1 et n>1, il existe une infinité de réels distincts.

Nombre d'entiers représentables.

  1. Sur un octet, combien d'entiers positifs peut-on représenter (ces entiers étant codés sous leur forme binaire) ?
    Donner la valeur de l'entier le plus grand ainsi codé.
  2. Sur n bits, combien d'entiers positifs peut-on représenter (ces entiers étant codés sous leur forme binaire) ?

Résolution de l'exercice "Nombre d'entiers représentables".

Sur un octet, on code les entiers de 0000 0000 à 1111 1111, c'est à dire de 0 à \( 2^0+2^1+2^2+\dots+2^7 = 2^8 -1 = 255\).
On code donc 256 entiers.

Sur n bits, on code 2n entiers : le plus petit étant 0, le plus grand étant \( \sum_{j=0}^{n-1} 2^j = 2^n -1\).