1.11. Intermezzo : Le calcul binaire démythifié

Les esprits formés par un mode de connaissance qui répudie la complexité, donc l’ambivalence, ne savent concevoir l’ambivalence inhérente à l’activité scientifique, où connaissance et manipulation sont les deux faces du même processus. Plus généralement, la mentalité formée à un mode de pensée binaire, qui exclut l’ambiguïté, ne peut concevoir que la science soit à la fois bonne et mauvaise , bienfaisante et perverse, utile et néfaste — Edgar Morin, La Méthode : Tome 6, Éthique.

Le monde est binaire : Elvis et pas Johnny, Chandler et pas Agatha Christie, Gottlieb et pas Bally — Daniel Darc.

Dans le monde il y a 10 types de personnes, ceux qui comprennent le binaire, et les autres — Anonyme.

Après avoir suffisamment appris à manipuler les nombres du système de numération décimale et à leur appliquer les opérations élémentaires de l’Arithmétique, nous sommes capables d’embrasser d’autres systèmes avec la même facilité. Oui ! j’ai bien dit avec la même facilité. Nous nous intéresserons ici au système binaire, dont nous avons brièvement parlé dans le cours sur la préparation des outils. En effet, nous avons dit que le binaire est le seul langage compris par les machines électroniques, en général, et par l’ordinateur, en particulier. Cela est principalement dû à l’architecture des composants électroniques utilisés (tels que le transistor), qui n’ont que deux états de fonctionnement : l’état où ils laissent passer le courant et l’étant où ils bloquent le passage du courant. Ces deux états sont donc symbolisés par les chiffres 0 et 1. Ainsi, l’ordinateur ne comprend ni notre langue courante (le français, l’anglais, etc.) ni le système de numération décimale. Il ne comprend que le langage binaire. Il va donc sans dire que pour que nous puissions communiquer avec lui, il nous faut un intermédiaire qui, comme les interprètes, soit capable de traduire notre langage en ce langage des 0 et 1. Et justement, il y a deux types d’interprète : l’interpréteur et le compilateur. Ils diffèrent dans leur manière de traiter les informations.

Le langage binaire qui pourtant semble être le langage le plus efficace pour l’ordinateur, l’est moins comparé au langage ternaire, selon les études de certains scientifiques. Ces derniers ont démontré que le langage ternaire — composé des symboles 0, 1 et 2 — est le langage qui, s’il était utilisé par l’ordinateur, le rendrait quelques octaves plus rapide. Mais, il est évident que l’ordinateur actuel ne peut pas employer ce langage, à cause de l’architecture de ses composants électroniques. D’un autre côté, il y a la naissance de l’informatique quantique et des ordinateurs quantiques qui, contrairement aux ordinateurs ordinaires qui fonctionnent sur deux états, sont capables de fonctionner sur des états intermédiaires. La recherche scientifique est encore très active dans ce domaine. On attend de voir ce que ça donnera dans un proche avenir. D’ici-là, nous nous focaliserons sur l’ordinateur classique et son mode de fonctionnement binaire.

Le langage binaire est notoirement la bête noire des étudiants qui débutent en informatique. Cette phobie est créée par les enseignants même de cette science qui, parce qu’ils n’ont pas eux-mêmes bien cernés ce langage, racontent toute sorte de mythes pervers sur ce sujet. Il est temps de redorer le blason et de restituer ce langage à sa simplicité arithmétique. C’est de l’Arithmétique et rien d’autre. Celui qui a compris le système de numération décimale a, par ricochet, compris le système binaire, et c’est ce que je m’attèlerai à démontrer dans ce qui suit. Commençons donc !

De la nature des nombres binaires

Les nombres binaires sont des nombres composés uniquement des chiffres 0 et 1. Par exemple, 1001110, 101 et 1111111 sont des nombres binaires. L’importance des chiffres dépend de leur position. Plus un chiffre est loin à gauche d’un autre chiffre, plus il est important que ce dernier. Le système binaire n’a donc rien de différent du système décimal, à part seulement la base. Le système binaire a pour base 2 tandis que le système décimal à pour base 10.

Quel est donc l’impact de la base sur la représentation des nombres dans la base ? Le moment où on passe d’une octave (ou d’un rang ou d’une puissance) à une autre est défini par la base. En base 10, on comptait : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … Remarquez qu’au départ, nous avons des nombres à un chiffre (des unités) et à partir de 9 (un seul chiffre), on a 10 (deux chiffres), nous sommes passés à une octave supérieure et les nombres ont maintenant deux chiffres (dizaines et unités). On recommence à compter les unités depuis 0, ce qui donne 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, … Dès qu’on atteint encore 9 aux unités, on recommence à 0 et on ajoute un au chiffre des dizaines. On continue cette programmation jusqu’à ce que le chiffre des dizaines atteigne également 9 et on a 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, … Vous voyez bien qu’à partir de 99, le fait d’ajouter une unité au chiffre 9 des unités, le fait passer à 10, on pose 0 comme unités et on retient 1 qu’on ajoute au chiffre 9 des dizaines. Ce qui donne également 10, on a donc 100 qui est un nombre à trois chiffres. Nous sommes donc encore une fois passés à une octave supérieure. Puisque nous sommes en base 10, ce sont des octaves de 10.

Ce que nous venons de dire est exactement pareil pour le système binaire. En effet, puisque la base est 2, chaque fois qu’on atteint deux (le deux ici n’a rien à voir avec le deux décimal, il s’agit du sens réel du nombre) en comptant, on met 0 et on ajoute un à chiffre de gauche. Si le chiffre de gauche atteint deux, on met 0 et on ajoute 1 au chiffre de gauche. S’il n’y a pas de chiffre à gauche, ça signifie que nous passons à une octave supérieure. Voici les dix premiers chiffres en base binaire :

$$0,~~1,~~10,~~11,~~100,~~101,~~110,~~111,~~1000,~~1001,~~1010$$

On voit bien qu’à chaque octave de deux, on avons un chiffre de plus :

\(
\begin{split}
10~~\text{correspond à}~~ & 2^1 = 2~~ (1^{\text{ère}}~~ \text{octave de 2})\\
100~~\text{correspond à}~~ & 2^2 = 4~~ (2^{\text{ème}}~~ \text{octave de 2})\\
1000~~\text{correspond à}~~ & 2^3 = 8~~ (3^{\text{ème}}~~ \text{octave de 2})\\
\ldots
\end{split}
\)

Le nombre 24235 se décompose dans le système décimal comme suit :

$$24235 = 20000 + 4000 + 200 + 30 + 5 = 2 \times 10000 + 4 \times 1000 + 2 \times 100 + 3 \times 10 + 5$$

Ou plus simplement sous forme de puissance :

$$24235 = 2 \times 10^4 + 4 \times 10^3 + 2 \times 10^2 + 3 \times 10^1 + 5 \times 10^0$$

On voit bien, dans cette dernière décomposition, que tout nombre décimal se décompose en la somme des produits de ses chiffres par la puissance de 10 du numéro de leur position. Le numéro de la position se comptant de la droite vers la gauche en commençant par 0.

Puisque la numération binaire ne diffère de la numération que par la base, on peut dire par analogie que tout nombre binaire se décompose en la somme des produits de ses chiffres par la puissance de 2 du numéro de leur position. Le numéro de la position se comptant de la droite vers la gauche en commençant par 0.

Par exemple, le nombre binaire 1001110 se décompose comme suit :

$$1001110 = 1 \times 2^6 + 0 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 0 \times 2^0$$

Et par la même analogie, cette règle s’applique à tout système auquel vous pouvez penser, qu’il soit ternaire, quaternaire, octal, hexadécimal ou autre. C’est seulement la base qui change. Nous verrons en Algèbre l’expression générale pour la décomposition d’un nombre dans n’importe quelle base.

Notez que l’ajout de 0 à gauche du nombre ne change pas ce nombre. Donc 000011001 ou 0011001 est le même et unique nombre 11001.

J’imagine certains parmi vous en train de tenter de prononcer les nombres binaires comme on le fait pour les nombres de la base 10. Arrêtez s’il vous plaît ! le système binaire n’est pas doté d’un système de dénomination des nombres comme le système décimal. Aussi, on lit un nombre binaire soit en énonçant chacun de ses chiffres, soit en le traduisant en nombre de la base 10 et en énonçant ce nombre. Par exemple 1101 se lirait un-un-zéro-un.

Maintenant que nous savons ce que sont les nombres binaires, voyons comment passer d’un nombre du système décimal à un nombre binaire et vice-versa.

Du passage du système binaire au système décimal et vice-versa

Pour traduire un nombre d’une base A vers une base B, on utilise l’algorithme suivant :

  1. On divise le nombre initial par la valeur de B. On obtient un premier quotient et un premier reste. Ce reste est le premier chiffre du nombre dans la base B, on le note quelque part.
  2. On divise le quotient obtenu précédemment par la valeur de B. On obtient un deuxième quotient et un deuxième reste. On place ce reste à gauche du précédent.
  3. On divise le quotient obtenu précédemment par la valeur de B. On obtient un troisième quotient et un troisième reste. On place ce reste à gauche du précédent.
  4. On continue ainsi jusqu’à ce que le quotient soit plus petit que la valeur de B. Ce quotient est le dernier chiffre du nombre dans la base B, on le place à gauche de l’avant-dernier chiffre. Le nombre ainsi obtenu est la traduction du nombre initial dans la base B.

Cet algorithme est général, il s’applique à toutes les bases. Toutefois, nous ne l’appliquerons ici qu’aux bases 2 et 10.

Avant de passer aux exemples, je veux introduire une nouvelle notation pour différencier les nombres de la base 2 et ceux de la base 10. Car convenez avec moi qu’on ne peut pas a priori affirmer que le nombre 10010 est un nombre binaire. Il peut très bien correspondre au nombre dix mille dix de la base 10. Aussi, pour faire la différence, nous allons écrire la base en indice du nombre. Contrairement à l’exposant qui se place en haut à droite du nombre, l’indice se place en bas à droite. Par exemple \(10010_2\) et \(10010_{10}\) représentent le nombre 10010 dans la base 2 et 10, respectivement. Mais, \(10010_2\) et \(10010_{10}\) sont différents.

Soit à traduire le nombre \(2452_{10}\) en base 2.

  • On divise 2452 par 2, on obtient 1226 comme quotient et 0 comme reste. \(\mathbf{0}_2\) est donc la traduction temporaire en base 2.
  • On divise maintenant 1226 par 2, on obtient 613 comme quotient et 0 comme reste. On place ce reste à gauche de \(0_2\), ce qui donne maintenant \(\mathbf{0}0_2\).
  • On divise 613 par 2, on obtient 306 comme quotient et 1 comme reste. On place ce reste à gauche de \(00_2\), ce qui donne maintenant \(\mathbf{1}00_2\).
  • On divise 306 par 2, on obtient 153 comme quotient et 0 comme reste. On place ce reste à gauche de \(100_2\), ce qui donne maintenant \(\mathbf{0}100_2\).
  • On divise 153 par 2, on obtient 76 comme quotient et 1 comme reste. On place ce reste à gauche de \(0100_2\), ce qui donne maintenant \(\mathbf{1}0100_2\).
  • On divise 76 par 2, on obtient 38 comme quotient et 0 comme reste. On place ce reste à gauche de \(10100_2\), ce qui donne maintenant \(\mathbf{0}10100_2\).
  • On divise 38 par 2, on obtient 19 comme quotient et 0 comme reste. On place ce reste à gauche de \(010100_2\), ce qui donne maintenant \(\mathbf{0}010100_2\).
  • On divise 19 par 2, on obtient 9 comme quotient et 1 comme reste. On place ce reste à gauche de \(0010100_2\), ce qui donne maintenant \(\mathbf{1}0010100_2\).
  • On divise 9 par 2, on obtient 4 comme quotient et 1 comme reste. On place ce reste à gauche de \(10010100_2\), ce qui donne maintenant \(\mathbf{1}10010100_2\).
  • On divise 4 par 2, on obtient 2 comme quotient et 0 comme reste. On place ce reste à gauche de \(110010100_2\), ce qui donne maintenant \(\mathbf{0}110010100_2\).
  • On divise 2 par 2, on obtient 1 comme quotient et 0 comme reste. On place ce reste à gauche de \(0110010100_2\), ce qui donne maintenant \(\mathbf{0}0110010100_2\).
  • Puisque le quotient, 1, est plus petit que la base, 2, on place cette unité à gauche de \(00110010100_2\) et on obtient \(\mathbf{1}00110010100_2\). C’est fini.

Le nombre \(\mathbf{100110010100_2}\) est donc la traduction binaire du nombre \(2452_{10}\). On peut aussi écrire que :

$$2452_{10} = 100110010100_2$$

Cette égalité ne souffre d’aucune ambiguïté puisque les bases sont bien précisées.

On peut représenter cette opération de deux manières comme le montre la figure ci-après :

Conversion du nombre décimal 2452 en nombre binaire 100110010100

Conversion du nombre décimal 2452 en nombre binaire 100110010100

Dans la représentation de gauche, on montre tous les détails des divisions successives par la base 2 tandis que dans la représentation de droite, on se dispense de ces détails. On fait seulement apparaître les dividendes et les restes successifs. On forme le nombre binaire en lisant les restes dans le sens de la flèche rouge.

Pour passer du binaire au décimal, en utilisant l’algorithme précédent, on a besoin de savoir diviser en binaire. Ce que nous n’avons pas encore vu. Mais, il y a une méthode permettant de traduire les nombres de toute base en nombres de la base 10. C’est la décomposition que nous avons vue à la section précédente. Appliquons ça au nombre binaire, \(100110010100_2\), trouvé dans l’exemple précédent et voyons si nous retrouvons le nombre en base 10. Ce nombre contient 12 chiffres donc le plus grand exposant de sa base est 11 (\(12 – 1 = 11\)). On a :

\(
\begin{split}
100110010100_2 & = 1 \times 2^{11} + 0 \times 2^{10} + 0 \times 2^9 + 1 \times 2^8 \\
&~~+ 1 \times 2^7 + 0 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 0 \times 2^0 \\
& = 2048 + 0 + 0 + 256 + 128 + 0 + 0 + 16 + 0 + 4 + 0 + 0 \\
& = 2452_{10}
\end{split}
\)

Nous retrouvons bien le nombre \(2452_{10}\). Appliquons la même méthode pour trouver le nombre décimal correspondant au nombre binaire \(101101_2\). Ce nombre a 6 chiffres donc le plus grand exposant de sa base est 5 (\(6 – 1 = 5\)). On a :

\(
\begin{split}
101101_2 &= 1 \times 2^5+ 0 \times 2^4+ 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 \\
& = 32+ 0 + 8 + 4 + 0+ 1 \\
& = 45_{10}
\end{split}
\)

Des opérations binaires

Dans cette section, nous omettrons l’indice des nombres car nous ne ferons que des opérations binaires. Donc, retenez bien que tous les nombres que nous manipulerons sont des binaires.

L’addition binaire

L’addition binaire ne diffère en rien de l’addition décimale. Il faut juste remarquer qu’on prend la retenue lorsque le résultat d’une opération partielle donne une valeur plus grande ou égale à 2. En base 10, on prenait la retenue lorsque le résultat d’une opération partielle donnait une valeur plus grande ou égale à 10. Avant de faire l’addition des grands nombres, voici quelques petites opérations :

$$0 + 0 = 0, ~~1 + 0 = 1, ~~1 + 1 = \mathbf{1}0$$

La dernière opération nécessite quelques explications. Puisque un plus un en binaire devrait donner deux et qu’on sait que dès qu’on atteint deux en binaire, on passe à une octave supérieure, on écrit 0 et on retient 1. En décimal, dès qu’on atteint 10 (la base), on écrit 0 et on retient 1.

À l’aide de ces opérations élémentaires, nous pouvons effectuer toutes les opérations d’addition. Voici deux exemples :

\(
\begin{array}{c}
\phantom{+}~\phantom{0}~1~1~1~1~1~\phantom{0}\\ \hline
\phantom{+}~\phantom{0}~1~0~1~1~0~1\\
+~\phantom{0}~\phantom{0}~1~1~0~1~1\\ \hline
=~1~0~0~1~0~0~0
\end{array}
\)
\(
\begin{array}{c}
\phantom{+}~\phantom{0}~\phantom{0}~3~3~2~2~2~3~2~1~\phantom{0}\\ \hline
\phantom{+}~\phantom{0}~\phantom{0}~\phantom{0}~1~0~1~1~0~1~1~0\\
+~\phantom{0}~\phantom{0}~\phantom{0}~1~1~1~0~0~1~0~1\\
+~\phantom{0}~\phantom{0}~\phantom{0}~\phantom{0}~1~0~0~1~1~0~0\\
+~\phantom{0}~\phantom{0}~\phantom{0}~\phantom{0}~1~0~1~0~1~1~1\\
+~\phantom{0}~\phantom{0}~\phantom{0}~1~1~0~1~1~0~1~1\\ \hline
=~~1~1~0~0~0~1~1~0~0~1
\end{array}
\)

Comme pour l’addition décimale, la première ligne est la ligne des retenues. Pour effectuer ces opérations, on procède comme pour les opérations simples vues plus haut. Avec un peu d’expérience, il est possible de faire ce calcul sans réfléchir. Le mathématicien Leibniz, qui a consacré une bonne partie de ses recherches au système binaire, a fait remarquer que l’addition binaire se réduit à un simple comptage d’unités. Il est en effet facile de connaître le résultat d’une addition partielle et la retenue pour l’addition suivante. Puisqu’on sait que le calcul binaire ne comporte que les chiffres 0 et 1, on est assuré que le résultat d’une addition sera 0 ou 1.

Pour trouver le résultat d’une addition partielle, il suffit de compter le nombre d’unités. Si ce nombre est pair, on met 0 comme résultat de l’addition et on retient la moitié de ce nombre. Sinon si ce nombre est impair, on met 1 comme résultat de l’addition et on retient la moitié de ce nombre.

Par exemple, si l’addition partielle est \(1 + 0 + 1 + 1 + 1 + 0\), on a quatre unités, ce qui est pair. Le résultat est donc 0 et on retient 2, car \(4 \div 2 = 2\). Si l’addition partielle est \(1 + 0 + 1 + 1 + 1 + 0 + 1 + 1 + 0 + 1\), on a sept unités, ce qui est impair. Le résultat est donc 1 et on retient 3, car \(7 \div 2 = 3\).

Reconnaissez que l’addition binaire est plus facile que l’addition décimale. Continuons !

La soustraction binaire

Voici les opérations simples qui nous permettront de réaliser des opérations plus compliquées :

$$0 – 0 = 0, ~~1 – 1 = 0, ~~1 – 0 = 1$$

Ces opérations sont triviales donc je ne m’étalerai pas sur elles. Il y a toutefois une opération manquante, c’est \(0 – 1\). Si dans une soustraction, cette opération partielle apparaît, il y aura forcément un chiffre 1 à une certaine position à gauche du 0. Supposons que le 1 soit juste une octave à gauche du 0. Plutôt que de chercher \(0 – 1\), on va chercher \(10 – 1\), car 0 étant plus petit que 1, nous ne pouvons pas actuellement effectuer cette opération. Pour calculer \(10 – 1\), il faut juste remarquer que \(10 = 1 + 1\). Alors, si on retranche 1 à 10, on retranche également 1 à \(1 + 1\), ce qui donne 1. Donc \(10 – 1 = 1\). Supposons maintenant que le 1 soit à deux octaves à gauche du 0. On va donc chercher \(100 – 1\). Il suffit de remarquer que \(100 = 11 + 1\). Si on retranche 1 à 100, on retranche également 1 à \(11 + 1\), ce qui fait 11. Donc \(100 – 1 = 11\). Supposons maintenant que le 1 soit à trois octaves à gauche du 0. On va donc chercher \(1000 – 1\). Il suffit de remarquer que \(1000 = 111 + 1\). Si on retranche 1 à 1000, on retranche également 1 à \(111 + 1\), ce qui fait 111. Donc \(1000 – 1 = 111\). Et ainsi de suite. Ces opérations sont posées ci-dessous :

\(
\begin{array}{c}
\phantom{-}~1~0\\
-~\phantom{0}~1\\ \hline
=~\phantom{0}~1
\end{array}
\)
\(
\begin{array}{c}
\phantom{-}~1~0~0\\
-~\phantom{0}~\phantom{0}~1\\ \hline
=~\phantom{0}~1~1
\end{array}
\)
\(
\begin{array}{c}
\phantom{-}~1~0~0~0\\
-~\phantom{0}~\phantom{0}~\phantom{0}~1\\ \hline
=~\phantom{0}~1~1~1
\end{array}
\)

Ceci peut se généraliser au cas où nous avons un nombre quelconque de zéros à droite du 1 dans le premier terme de la soustraction. Voici l’algorithme que Leibniz a proposé :

Soit à soustraire 1
Tant que au-dessus, il y a zéro
    Mettre 1 comme résultat
    Décaler d'une colonne (ou octave) vers la gauche,
Fin du Tant que
Au-dessus, il y a 1,
    Mettre 0 comme résultat,
C'est fini.

Après avoir décalé vers la gauche, si le chiffre du second terme est 1, plutôt que de mettre directement comme résultat de l’opération partielle, on retranche cette unité du chiffre du second terme. On a donc  \(1 – 1 =0\).

Grâce à cet algorithme, on effectue les opérations, que je viens de vous expliquer, sans réfléchir. Voici deux exemples de soustraction :

\(
\begin{array}{c}
\phantom{-}~1~0~0~0~1~1\\
-~\phantom{0}~\phantom{0}~\phantom{0}~1~0~1\\ \hline
=~0~1~1~1~1~0
\end{array}
\)
\(
\begin{array}{c}
\phantom{-}~1~0~1~1~0~0~1~0\\
-~1~0~0~1~1~1~1~1\\ \hline
=~0~0~0~1~0~0~1~1
\end{array}
\)

La soustraction décimale est-elle plus facile que la soustraction binaire ? Je vous laisse apprécier.

La multiplication binaire

C’est la certainement la plus simple de toutes les opérations binaires et elle est nettement plus simple que la multiplication décimale, car elle n’exige pas la connaissance de la table de Pythagore ou de toute extension de cette table. Les seules opérations à connaître sont les suivantes :

$$0 \times 0 = 0, ~~0 \times 1 = 0, ~~1 \times 0 = 0, ~~1 \times 1 = 1$$

Ces opérations sont vraiment triviales. J’espère ne pas vous offenser en les reportant.

Voici un exemple de multiplication :

\(
\begin{array}{c}
\phantom{\times}~\phantom{0}~\phantom{0}~\phantom{0}~\phantom{0}~1~0~1~1~1~1~0~1\\
\times~\phantom{0}~\phantom{0}~\phantom{0}~\phantom{0}~\phantom{0}~\phantom{0}~\phantom{0}~\phantom{0}~1~1~1~0\\ \hline
\phantom{\times}~1~1~2~2~2~2~1~1~\phantom{0}~\phantom{0}~\phantom{0}\\ \hline
\phantom{\times}~\phantom{0}~\phantom{0}~\phantom{0}~\phantom{0}~0~0~0~0~0~0~0~0\\
\phantom{\times}~\phantom{0}~\phantom{0}~\phantom{0}~1~0~1~1~1~1~0~1~\phantom{0}\\
\phantom{\times}~\phantom{0}~\phantom{0}~1~0~1~1~1~1~0~1~\phantom{0}~\phantom{0}\\
\phantom{\times}~\phantom{0}~1~0~1~1~1~1~0~1~\phantom{0}~\phantom{0}~\phantom{0}\\ \hline
=~1~0~1~0~0~1~0~1~0~1~1~0
\end{array}
\)

Un seul exemple suffit car multiplier les exemples serait vraiment une insulte. Ai-je besoin de préciser que la multiplication binaire est de loin plus facile que la multiplication décimale ? Je ne crois pas, donc passons à la division.

La division binaire

Là encore, il n’y aucune différence avec la division décimale. Il faut juste savoir comparer deux nombres binaires afin de choisir aisément les chiffres du dividende partiel à chaque étape de sorte que ce dividende soit plus grand que le diviseur. Normalement, la comparaison des nombres constitue la deuxième partie de l’Arithmétique, que nous verrons prochainement. Mais, je peux ici donner quelques indications sur la comparaison des nombres entiers binaire, car c’est vraiment simple.

Soit à comparer deux nombres binaires. Voici les règles :

  • 0 est plus petit que 1, donc 1 est plus grand que 0. 0 n’est ni plus grand ni plus petit que 0 ; de même 1 n’est ni plus grand ni plus petit que 1.
  • S’ils ont des nombres de chiffres différents, celui qui a le plus grand nombre de chiffres, est le plus grand des deux. Évidemment, il faut d’abord avoir supprimé tous les zéros inutiles qui traîneraient à gauche de ces nombres.
  • Si ces nombres ont le même nombre de chiffres. En allant de gauche à droite, on compare chaque chiffre. Tant que les chiffres sont égaux, on décale d’une octave à droite et on continue la comparaison. Si les chiffres sont différents, c’est-à-dire que l’un est 1 et l’autre est 0, alors le nombre dont le chiffre actuel est 1 est le plus grand.

Nous sommes maintenant capables d’effectuer toute opération de division en base binaire. Par exemple, proposons-nous de diviser 101101101 par 1010. On choisit 1011 comme premier dividende partiel car le diviseur ayant quatre chiffres, le dividende doit en avoir au moins autant. Et remarquez bien que le dividende partiel ,1011, est plus grand que le diviseur 1010. La différence se situe au niveau du chiffre des unités. Dans 1011, il y a une fois 1010, on écrit donc 1 comme quotient partiel, et on fait la différence de 1011 et 1010. Et on obtient 1 comme reste. On fait descendre à droite du reste le chiffre suivant du dividende global, c’est-à-dire 0, et on a maintenant 10 comme dividende partiel. Dans 10, il y a zéro fois 1010 — car 10 est plus petit que 1010 — donc on met 0 à droite du précédent quotient partiel et on fait descendre le chiffre suivant à droite de 10. On a maintenant 101 comme dividende partiel. Il est également plus petit que 1010 donc on met un 0 à droite du précédent quotient partiel et on fait descendre le chiffre suivant du dividende global, à droite de 101. 1011 est le nouveau dividende partiel. Il y a une fois 1010 dans 1011, on met donc 1 à droite du quotient partiel précédent et on calcule la différence entre 1011 et 1010, ce qui donne 1 comme reste. On fait descendre le chiffre suivant du dividende global, à droite du reste, ce qui donne 10 comme nouveau dividende partiel. Il y a zéro fois 1010 dans 10, donc on met 0 à droite du quotient partiel précédent et on fait descendre le chiffre suivant du dividende global, à droite de 10. 101 est donc le nouveau dividende partiel. Comme 101 est plus petit que 1010, alors on met 0 à droite du quotient partiel précédent. Et on s’arrête là puisqu’il n’y a plus de chiffre du dividende global, à faire descendre. 100100 est donc le quotient de la division de 101101101 par 1010, avec un reste de 101.

\(
\begin{array}{c|c}
1~0~1~1~0~1~1~0~1 & 1~0~1~0~\phantom{0}~\phantom{0} \\
1~0~1~0~\phantom{0}~\phantom{0}~\phantom{0}~\phantom{0}~\phantom{0} & \overline{1~0~0~1~0~0}\\
\overline{\phantom{0}~\phantom{0}~0~1}~1~1~\phantom{0}~\phantom{0} & \\
\phantom{0}~ \phantom{0}~\phantom{0}~\underline{1~0~1~0}~\phantom{0}~\phantom{0} & \\
\phantom{0}~ \phantom{0}~\phantom{0}~\phantom{0}~\phantom{0}~\phantom{0}~1~0~1 & \\
\end{array}
\)

Soit maintenant à diviser 100100 par 1010. On choisit 10010 comme premier dividende partiel. Il a un chiffre de plus que le diviseur 1010, car si on s’arrêtait à exactement quatre chiffres, le dividende partiel, 1001, serait plus petit que le diviseur, 1010, déjà partir du troisième chiffre. Il y a une fois 1010 dans 10010, on met donc 1 comme premier quotient partiel et on calcule la différence de 10010 et 1010. On obtient 1000 comme reste. On fait descendre à droite de ce reste, le prochain chiffre du dividende global, c’est-à-dire 0, et on obtient 10000 comme prochain dividende partiel. Il y a une fois 1010 dans 10000 donc on met 1 à droite du premier quotient partiel et on calcule la différence de 10000 et 1010. On obtient 110 comme reste. Et on a fini. 11 est donc le quotient de la division de 100100 par 1010, et on a un reste de 110.

\(
\begin{array}{c|c}
1~0~0~1~0~0 & \underline{1~0~1~0} \\
\underline{\phantom{0}~1~0~1~0}~\phantom{0} & 1~1~\phantom{0}~\phantom{0}\\
\phantom{0}~1~0~0~0~0 & \\
\phantom{0}~\underline{\phantom{0}~1~0~1~0} & \\
\phantom{0}~ \phantom{0}~\phantom{0}~1~1~0 & \\
\end{array}
\)

Remarquez bien que c’est seulement les soustractions partielles qui demande de la réflexion. Sinon le choix du quotient partiel est presque automatique, c’est soit 0, soit 1, contrairement au cas de la division décimale où on a jusqu’à neuf choix. La division binaire est-elle plus difficile que la division décimale ? Je ne dirai pas mot.

Retour sur le passage d’un nombre binaire vers un nombre décimal

Maintenant que nous savons effectuer la division binaire, revenons à notre problème de la traduction d’un nombre binaire en un nombre décimal. Il suffit d’employer le même algorithme que nous avons vu, sauf qu’on divise maintenant par le dix binaire, c’est-à-dire par 1010.

Soit donc à trouver le nombre décimal équivalent à 100110010100. La figure suivante présente le résultat en utilisant la seconde représentation de l’opération de traduction d’une base à une autre.

Traduction du binaire 100110010100 en décimal 2452

Traduction du binaire 100110010100 en décimal 2452

Contrairement à la traduction du décimal en binaire où les restes sont directement les chiffres du nombre binaire, les restes de la traduction binaire en décimal doivent être eux-mêmes traduits en décimal. Mais, tout ceci est vraiment simple. On retrouve bien les \(2452_{10}\).

J’espère que vous avez bien vu que le calcul binaire est beaucoup plus facile que le calcul en base 10. Cela est dû au fait qu’on ne manipule que deux symboles : 0 et 1. Toutefois, étant habitué au système décimal, il est difficile de s’accoutumer au système binaire à cause du manque de dénomination. Un autre inconvénient de ce système, par rapport au système décimal, est que les nombres construits sont très longs. Vous voyez bien qu’alors que le nombre \(2452_{10}\) ne contient que quatre chiffres, son équivalent binaire, \(100110010100_2\) contient, lui, douze chiffres. La différence est énorme et elle grandit très vite.

Avant de clore cet intermède, faisons une incursion en codage informatique.

Codage binaire

En informatique, le calcul binaire intervient beaucoup dans les considérations de mémoire. En effet, puisque les informations contenues dans l’ordinateur sont stockées en mémoire, il faut que la taille de la mémoire soit au moins égale à la quantité d’informations à stocker. Nous avons vu dans le cours sur le système informatique que l’unité utilisée pour exprimer la quantité de mémoire est l’octet (ou byte, en anglais). Un octet contient 8 bits. Un bit est soit 0 soit 1.

Lorsqu’on dit que votre clé USB a une mémoire de 16 GB, le GB est mis pour gigabyte. Ça signifie que votre clé peut contenir environ seize milliards (\(16 \times 10^9\) ou \(16 \times 2^30\)) d’octets (la valeur précise est \(16 \times 1073741824\) octets) d’informations.

En informatique, chaque caractère a un code binaire (ou hexadécimal, en fonction de la base). Ce code représente aussi la taille de mémoire que ce caractère utilise. Il y a plusieurs systèmes de codage, parmi lesquels on peut citer l’ASCII (American Standard Code for Information Interchange) et l’Unicode. L’ASCII est plus simple, il permet de coder les caractères sur 8 bits, soit \(2^8 = 256\) caractères possibles. L’Unicode est beaucoup plus complexe car il permet de coder plus de caractères, dont les accents et d’autres caractères spéciaux de presque toutes les langues.

Coder des caractères sur 8 bits veut dire que ces caractères ne peuvent avoir que 8 chiffres au maximum. Puisqu’un bit permet de coder 0 ou 1 (donc 2 caractères), 2 bits permettent de coder \(2 \times 2 = 2^2 = 4\) caractères, 3 bits permettent de coder \(2 \times 2 \times 2 = 2^3 = 8\) caractères, …, et 8 bits permettent de coder \(2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 = 2^8 = 256\) caractères. Voici des exemples de caractères sur 8 bits :

\(
0~0~0~0~0~0~0~0\\
0~0~0~0~0~0~0~1\\
0~0~0~0~0~0~1~0\\
0~0~0~0~0~0~1~1\\
0~0~0~0~0~1~0~0\\
…\\
1~1~1~1~1~1~1~1\\
\)

Le code ASCII de la lettre alphabétique A (majuscule) est 01000001 en binaire (65 en décimal et 41 en hexadécimal). Remarquez ici que les zéros à gauche du nombre sont importants car ils permettent de savoir sur combien de bits il est codé. La figure suivante donne la table ASCII complète.

Table ASCII

Table ASCII (Source: Wikipedia)

Considérons qu’au lieu du clé USB, vous ayez une disquette (un peu old school mais bon !) de taille 32 KB (kilobyte). Pourriez-vous y stocker ce poème de Maurice Carême ?

Mon père aimé, mon père à moi,
Toi qui me fais bondir
Sur tes genoux
Comme un chamois,
Que pourrais-je te dire
Que tu ne sais déjà ?
Il fait si doux
Quand ton sourire
Eclaire tout sous notre toit.
Je me sens fort, je me sens roi,
Quand je marche à côté de toi.

Notez que les espaces et les retours à la ligne sont comptés comme des caractères et ont leurs codes. Pour rester dans le cadre de l’ASCII, considérons que les caractères accentués sont sans accent. Par exemple, on considère que les “é”, “è” et “ê” sont des “e”.

Ce poème contient 260 caractères. Puisque chaque caractère de l’ASCII occupe un octet de mémoire (ou 8 bits), le poème requiert une mémoire de \(260 \times 8 = 2080\) octets, soit environ 2 KB. Et comme notre disquette a une mémoire de 32 KB, elle pourra donc contenir ce texte, et il lui resterait encore \(32 – 2 = 30\) KB de mémoire disponible.

Notez qu’on pourrait même traduire ce poème en binaire. Je vous laisse le soin de le faire si vous voulez vous amuser.

Bon codage ! 😉

PDF du cours

Intermezzo : Le calcul binaire démythifié.pdf
Intermezzo : Le calcul binaire démythifié
  •  
    21
    Shares
  • 21
  •  
  •  
  •  
  •  

Poster un Commentaire

avatar
  S’abonner  
Notifier de