Pour convertir en base \(2\) un entier écrit en base \(10\), nous pouvons utiliser la méthode des soustractions successives, qui un algorithme glouton.
Cet algorithme est identique à celui du rendu de monnaie, en considérant les puissances de \(2\) successives comme valeurs des pièces.
Par exemple, pour obtenir la représentation binaire de \(43\), on peut utiliser les valeurs \(32\), \(16\), \(8\), \(4\), \(2\) et \(1\), classées par ordre décroissant. On se limite à \(32\) car la puissance suivante, \(64\), est strictement supérieure à \(43\).
On procède alors ainsi :
Pour \(43\) on peut prendre \(32\) , il reste \(11\),
Pour \(11\) on ne peut pas prendre \(16\) (en effet \(16>11\)),
Pour \(11\) on peut prendre \(8\), il reste \(3\),
Pour \(3\) on ne peut pas prendre \(4\),
Pour \(3\) on peut prendre \(2\), il reste \(1\),
Pour \(1\) on peut prendre \(1\), il reste \(0\).
On obtient la représentation binaire en observant les différentes étapes : s'il est possible de prendre une puissance, on note un 1, si c'est impossible, on note un 0.
Puissance de 2
Possible ?
Bit correspondant
\(32\)
Oui
1
\(16\)
Non
0
\(8\)
Oui
1
\(4\)
Non
0
\(2\)
Oui
1
\(1\)
Oui
1
Dans la pratique, pour convertir « à la main » \(43\) en binaire, cela revient réaliser le tableau suivant :
\(32\)
\(16\)
\(8\)
\(4\)
\(2\)
\(1\)
1
0
1
0
1
1
On en déduit que \(43\) en décimal s'écrit 101011 en binaire.
Travail à faire
Une fonction binaire a été écrite qui prend en paramètre un entier positif ou nul écrit en base \(10\), et renvoie la chaîne de caractères la plus courte possible (sans zéros inutiles) représentant son écriture binaire.
Cependant, cette fonction contient des erreurs.
Corriger la fonction pour quelle puisse passer les tests.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)