Algorithmes de conversion entre binaire et décimal

Bien que python offre déjà toutes les facilités pour convertire vers et depuis le binaire, il est important de bien comprendre les algorithmes sous-jacents et aussi de savoir les implémenter en python.

Le premier algorithme présenté permet de déterminer la représentation binaire d’un entier (donné initialement sous forme décimale) en utilisant la même méthode que celle utilisée «à la main» un peu plus haut dans l’exemple et l’exercice correspondant.

Le second réalise la même tâche mais selon une méthode diamétralement différente. Il a l’avantage d'être finalement plus simple et plus court. Il est aussi plus efficace (bien que cela n’ait guère d’importance en pratique sur des nombres comportant peu de chiffres).

Enfin, le dernier algorithme présenté réalise la tâche inverse, à savoir déterminer un nombre entier à partir de sa représentation en base 2.

Conversion décimal \(\rightarrow\) binaire

Lorsque l’on a cherché une représentation en base 2 d’un entier donné, on a plus ou moins procédé comme suit:

Déterminer la plus grande puissance de 2 inférieure ou égale à N. Notons-la P.

Tant que P est positif faire:
    Si P est inférieur ou égal à N alors:
        Afficher 1
        Soustraire P à N
    Sinon:
        Afficher 0
    Diviser P par deux (division euclidienne)

La première partie de l’algorithme peut (et doit) elle même être précisée, comme suit:

P prend la valeur 1
Tant que 2P est inférieur ou égal à N faire:
    P prend la valeur 2P

Tant que P est positif faire:
    Si P est inférieur ou égal à N alors:
        Afficher 1
        Soustraire P à N
    Sinon:
        Afficher 0
    Diviser P par deux (division euclidienne)

À la sortie de la boucle, \(P\) sera la plus grande puissance de 2 inférieur ou égal à \(N\), excepté si \(N = 0\): l’algorithme ne fonctionne d’ailleurs pas dans ce cas là, puisqu’aucune des deux boucles n’est exécutée. Il faudra traiter le cas nul à part.

Remarquons aussi que cet algorithme réalise la même chose que la fonction bin(nombre) préexistance en python.


Exercice 5: Implémenter l’algorithme précédent en python, sous la forme d’une fonction bin1(nombre) prenant pour paramètre un entier naturel et renvoyant en valeur de retour une chaîne de caractère contenant la représentation binaire correcte du nombre. Dit plus simplement: la fonction bin1() doit réaliser exactement la même chose que la fonction bin() de python.

Attention: La fonction bin1(nombre) a pour vocation de renvoyer une valeur, elle ne devra rien afficher dans la console (sauf éventuellement durant la phase de mise au point)

En python il existe deux opérateurs de division: le simple slash / est une division «à virgule»: son résultat est toujours un nombre à virgule flottante (donc une valeur approchée) même si mathématiquement il s’agit d’un entier.

>>> 4 / 5
0.8
>>> 4 / 2
2.0

Nous aurons ici davantage besoin d’une division euclidienne (c’est-à-dire la division telle qu’aprise à l'école primaire, avec dividende et reste). L’opérateur double-slash // sert à cela, et son résultat est toujours un entier.

>>> 4 // 3
1
>>> 4 // 2
2

On peut calculer le reste d’une division euclidienne grâce à l’opérateur % (qu’il ne faut surtout pas confondre avec un pourcentage même s’il s’agit du même caractère. Il se prononce modulo en mathématiques):

>>> 4 % 3
1
>>> 4 % 2
0

Quelques outils sur les chaînes de caractères qui n’ont pas encore été étudiées cette année: Une chaîne de caractère est indifféremment entourée d’apostrophes ' ou bien de guillemets anglais " (à ne pas confondre avec des doubles apostrophes). On peut rajouter des caractères avant ou après une chaîne de caractères à l’aide de l’opérateur + qui sert alors de concaténation et non pas d’addition:

>>> s = "mot"
>>> s + "-suffixe"
'mot-suffixe'
>>> 'préfixe-' + s
'préfixe-mot'
>>> binaire = "1011"
>>> binaire = "00" + binaire + "01"
>>> binaire
'0000001011010101'
>>> "0b" + binaire
'0b0000001011010101'

Un algorithme plus efficace

L’algorithme précédent déterminait la représentation binaire d’un entier de la gauche vers la droite, c’est-à-dire du bit de poids fort vers le bit de poids faible.

L’algorithme présenté ici procède exactement à l’inverse: il détermine d’abord le bit de poids faible, puis procède de la droite vers la gauche.

Cet algorithme est basé sur quelques remarques très simples:

  • Le bit de poids faible d’un nombre représenté en binaire (c’est-à-dire celui situé le plus à droite ou encore le bit des unités) permet de savoir si un entier est pair ou impair: si ce bit est 0, alors l’entier est pair, sinon il est impair. En inversant l’argument précédent, il est donc aisé de déterminer le bit de poids faible en testant si un nombre est divisible par deux ou non. On utilise pour cela l’opérateur % de python donnant le reste d’une division euclidienne.
  • Une fois que l’on a déterminé le bit de poids faible, il suffit de recommencer pour les bits situés plus à gauche, en décalant le tout vers la droite. Un décalage vers la droite en binaire correspond exactement à une division euclidienne par deux (c’est l'équivalent d’une division par 10 en décimal qui elle aussi revient à décaler les chiffres décimaux d’un cran vers la droite).

On obtient alors l’algorithme suivant:

Tant que N est strictement positif faire:
    Si N est pair alors:
        Afficher 0
    Sinon:
        Afficher 1
        N prend la valeur N moins 1
    N prend la valeur N divisé par 2

Remarquons que cet algorithme affiche les bits à l’envers: pour éviter cet inconvénient, on créera plutôt une chaîne de caractère pour laquelle il sera facile d’ordonner les bits correctement (en effet, on peut toujours décider d’ajouter un caractère soit devant ou soit derrière une chaîne existante, selon ce que l’on cherche à obtenir).

Il est possible de détailler davantage le test de la conditionnelle:

Tant que N est strictement positif faire:
    Si N % 2 == 0 alors:
        Afficher 0
    Sinon:
        Afficher 1
        N prend la valeur N moins 1
    N prend la valeur N divisé par 2

En effet, dire que \(N\) est pair équivaut à dire que le reste de la division euclidienne de \(N\) par 2 vaut 0, ce qui se traduit en python par N % 2 == 0.


Exercice 6: Implémenter l’algorithme précédent en python, sous la forme d’une fonction bin2(nombre) prenant pour paramètre un entier naturel et renvoyant en valeur de retour une chaîne de caractère contenant la représentation binaire correcte du nombre. Dit plus simplement: la fonction bin2() doit réaliser exactement la même chose que la fonction bin() de python ou que la fonction bin1() précédente, mais avec un algorithme différent.

Remarquons en passant que l’on observe un des aspects importants des fonctions ici: il est impossible de deviner quel algorithme a été utilisé pour réaliser la tache assignée à la fonction en regardant simplement les paramètres et la valeur de retour. D’ailleurs, ce n’est pas souhaitable: on peut vouloir remplacer un algorithme par un autre, plus performat, à tout moment, sans qu’il soit pour autant nécessaire de modifier le reste du programme.


Conversion binaire \(\longrightarrow\) décimal

L’algorithme permettant de convertir un nombre donné en base 2 vers un nombre décimal est conceptuellement plus simple: il revient simplement à réaliser le calcul: \[N = b_n\times 2^n + b{n-1}\times 2^{n-1} + \cdots + b_2\times 2^2 + b_1\times 2^1 + b_0\times 2^0\] à partir des bits \(b_k\).


Exercice 7: Implémenter cet algorithme précédent en python, sous la forme d’une fonction décimal(chaîne) prenant pour paramètre une chaîne de caractère ne contenant que des 0 et des 1 (aucun test ne sera effectué pour s’en assurer) et renvoyant en valeur de retour l’entier correspondant.