É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 ?

  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

n1= 17

Cascade de divisions pour l'écriture binaire de 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

Cascade de divisions pour l'écriture binaire de 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
                    fin_tant_que
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.

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) ?

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\).