Binaire 001 : compter et calculer comme un ordinateur

Comme on le sait tous, un ordinateur ne connaît que deux choses: les 1 et les 0. Chaque lettre dans cette phrase, chaque couleur, chaque seconde d’une vidéo ou d’un morceau de musique, chaque page web, chaque programme n’est qu’une longue succession de 1 et de 0. C’est le binaire, et si l’on souhaite pouvoir communiquer efficacement avec ces machines en tant que programmeurs, il faut comprendre comment marche ce système de numération en base 2.

Pourquoi les ordinateurs utilisent-ils le système binaire?

Nous, les humains, avons 10 doigts. Il nous est donc parfaitement logique de compter sur une base 10 c’est à dire avec un système décimal. Ceci est pourtant tout à fait arbitraire : si nous avions été des pieuvres avec 8 bras et aucun doigt, une base 8 (ou octale), nous paraîtrait naturel. Si nous étions des dauphins avec deux nageoires, nous ne pourrions considérer autre chose qu’une base 2, le binaire.

Un ordinateur n’est pas un dauphin, et n’a aucun bras ni doigt. Ce qu’il a, c’est du courant électrique. Il peut faire la distinction entre un composant électrique qui est sous tension et un autre qui ne l’est pas. On représente ces deux états avec les symboles 1 et 0 respectivement.

Comprendre la notation positionnelle décimale

Pour comprendre le système binaire qu’utilise un ordinateur, il faut d’abord décomposer notre système décimal humain.

En base 10, on a un symbole unique et distinct pour chaque chiffre de 0 à 9.

Nombre  Décimal
Zéro        0
Un          1
Deux        2
Trois       3
Quatre      4
Cinq        5
Six         6
Sept        7
Huit        8
Neuf        9
Dix         Pas de symbole !
Onze        Pas de symbole !

On n’a pas de symboles pour les nombres qui suivent, le dix, onze, douze, etc. On passerait nos vies entières à l’école s’il y avait autant de symboles à mémoriser qu’il y a de nombres ! Heureusement, on a conçu un système astucieux qui nous permet de réutiliser sans cesse ces dix chiffres de base pour exprimer des nombres plus importants : la notation positionnelle.

Avec cette notation, lorsqu’on arrive au nombre dix, il nous suffit d’ajouter un chiffre à gauche pour indiquer les dizaines, puis lorsqu’on arrive à cent, on en ajoute un autre à gauche pour indiquer les centaines, etc. Chaque chiffre à gauche de l’unité représente une puissance de dix.

Par exemple, prenons le nombre 54 627. Il y a dans ce nombre 7 unités, 2 dizaines, 6 centaines, 4 milliers et 5 dizaines de milliers. On peut donc écrire ce nombre comme ceci :

(5 x 10 000) + (4 x 1 000) + (6 x 100) + (2 x 10) + (7 x 1)

Pour résumer cela dans un tableau pratique :

Compter avec le système binaire

En binaire, il faut tout d’abord savoir que chaque chiffre dans un nombre s’appelle un bit (pour binary digit). Un bit peut prendre la valeur 0 ou 1.

Tout comme le système décimal, le binaire utilise aussi la notation positionnelle, seulement, il y a beaucoup moins de symboles. On compte 0, puis 1, et puis on n’a déjà plus de symboles de base. Donc on réutilise les symboles et on ajoute un bit à gauche : 2 en décimal s’écrit donc 10 en binaire, 3 s’écrit 11, 4 s’écrit 100, etc. En base 2, chaque bit à gauche de l’unité représente une puissance de 2.

Avoir si peu de symboles veut dire que les nombres binaires deviennent très longs très rapidement :

Décimal         Binaire
   0                 0
   1                 1
   2                10 <-- 2 puissance 1
   3                11
   4               100 <-- 2 puissance 2
   5               101
   6               110
   7               111
   8              1000 <-- 2 puissance 3
   9              1001
  10              1010
  11              1011
  12              1100
  13              1101
  14              1110
  15              1111
  16             10000 <-- 2 puissance 4
  17             10001
  18             10010
  19             10011
  20             10100
 ...    ...
 100           1100100
 ...    ...
1000        1111101000
 ...    ...
9000    10001100101000

Prenons le nombre binaire 101010. On peut déduire son équivalence décimale de la manière suivante :

  2^1 + 2^3 + 2^5
= 2 + (2 x 2 x 2) + (2 x 2 x 2 x 2 x 2)
= 2 + 8 + 32
= 42

101010 en binaire vaut donc 42 en décimal.

Les nombres négatifs en binaire

En décimal, il suffit de mettre un signe négatif (-) devant le nombre pour dénoter qu’il est négatif. Il serait logique de faire de même en binaire, et pour une utilisation humaine, cela marcherait très bien. Les ordinateurs, eux, ne comprennent absolument rien d’autre que les 0 et les 1. Ajouter un autre symbole pour dénoter le signe d’un nombre leur est impossible. Soit il y a du courant, soit il n’y en a pas, et c’est tout.

Pourtant, les ordinateurs comprennent les nombres négatifs et heureusement ! Alors comment font-ils, sans signe ? Pour le comprendre, il faut savoir comment un ordinateur stocke les nombres binaires.

Comment un ordinateur stocke-t-il un nombre binaire ?

Avant tout, il faut savoir qu’un nombre binaire, tout comme un nombre décimal, peut s’écrire précédé d’autant que 0 qu’on le souhaite sans changer sa valeur.

Binaire     Décimal
111     =   7
0111    =   7
00111   =   7

En effet, les ordinateurs stockent des nombres sur plusieurs bits quelle que soit la valeur de ce nombre. Typiquement, un entier est stocké sur 4 octets, c’est à dire 32 bits. C’est beaucoup, pour notre petit 7 :

0000 0000 0000 0000 0000 0000 0000 0111  =  7

NB : les espaces sont là pour la lisibilité, en réalité il n’y a aucune espace.

Ce n’est pas un hasard que le nombre maximal que peut contenir un entier non signé ( unsigned int) est 4 294 967 295, qui s’écrit comme suit sur 32 bits :

1111 1111 1111 1111 1111 1111 1111 1111

Comme on a pu l’apprendre à force de segfaults, un entier signé ( int), lui, peut contenir au maximum la valeur 2 147 483 647, ce qui correspond, en binaire, à :

0111 1111 1111 1111 1111 1111 1111 1111

Notons qu’ici, le bit tout à gauche semble ne pas être utilisé…

Voyons donc à quoi ressemble le nombre minimal qu’un entier signé ( int) peut contenir, -2 147 483 648, en binaire :

1000 0000 0000 0000 0000 0000 0000 0000

Surprise ! Tous les bits sont ici inversés, y compris le bit tout à gauche, qui fonctionne comme un signe. C’est ce principe d’inversement des bits que l’ordinateur utilise pour transformer un nombre positif en son homologue négatif.

Par ailleurs, il faut souligner le fait qu’il n’y a pas de différence intrinsèque entre les nombres positifs et les nombres négatifs pour un ordinateur.

1111 1111 1111 1111 1111 1111 1111 1010

Ce nombre peut signifier soit 4 294 967 290, soit -6. C’est pourquoi, dans beaucoup de langages de programmation de bas niveau, comme le C par exemple, on doit préciser si nos variables sont de type int ou de type unsigned int. C’est entièrement une question d’interprétation.

Pourquoi inverser les bits ?

En effet, inverser tous les bits d’un entier pour indiquer un nombre négatif, c’est beaucoup de travail. Pourquoi ne pas simplement indiquer un nombre binaire négatif en modifiant le bit tout à gauche ? Et voilà, le tour est joué. Non ?

Le premier problème avec cette approche c’est qu’on aurait deux représentations du 0 :

0000 =  0
1000 = -0

Pire, pour utiliser cette méthode, il faudrait modifier l’algorithme d’addition binaire (décrite plus loin). Si l’un des nombres est négatif dans notre addition usuelle, on reçoit un résultat tout faux :

Si le nombre est interprété comme un entier non signé, l’addition marche bien. Si le nombre est un entier signé par contre, l’addition est totalement faussée.

Cette double représentation du 0 ainsi que les problèmes d’arithmétique ont fait qu’il a fallu concevoir un meilleur système : inverser tous les bits.

Le complément à un

Le complément à un est la valeur qui résulte de l’opération d’inversement des bits d’un nombre.

0111 =  7
1000 = -7 (complément à un)

Cette représentation d’un nombre négatif marche parfaitement bien avec les opérations mathématiques binaires :

Mais cela ne résout pas le problème de la double représentation du zéro :

0000 =  0
1111 = -0

Avoir deux zéros possibles nécessite de créer deux tests distincts pour tester la valeur nulle d’un résultat, ce qui n’est pas très pratique. Pour contrer ce défaut, une nouvelle méthode à été conçue, que pratiquement tous les ordinateurs modernes utilisent, le complément à deux.

Le complément à deux

Pour réaliser le complément à deux, il suffit de rajouter une étape très simple après avoir inversé les bits dans un complément à un : ajouter 1.

1. On prend le nombre positif
2. On inverse les bits
3. On ajoute 1

  0111 =  7
  1000 -> on inverse les bits (complément à un)
+ 0001 -> on ajoute 1 (complément à deux)
  1001 = -7

Voila qui répond à nos deux problèmes précédents. Le zéro est maintenant un chiffre unique et distinct. Même si l’on tente de convertir 0 en son homologue négatif, le résultat sera toujours 0 :

  0000 =  0
  1111 -> on inverse les bits (complément à un)
+ 0001 -> on ajoute 1 (complément à deux)
  0000 = 0

On peut aussi vérifier que l’arithmétique binaire usuelle se fait sans erreur :

Calculer en binaire comme un ordinateur

On ne pourra jamais calculer aussi vite qu’un ordinateur, mais on peut toujours essayer ! Ou du moins, comprendre les méthodes particulières avec lesquelles les ordinateurs gèrent les additions, les soustractions, les multiplications et les divisions en binaire.

L’addition

La table d’addition en binaire est très simple :

Retournons en CE1, mais cette fois, prenons les nombres binaires 101010 (42 décimal) et 1111 (15 décimal). Pour les additionner, tout comme en décimal, on additionne chaque chiffre de droite à gauche en reportant une retenue sur la position suivante si besoin. Dans cet exemple on va rajouter deux 0 devant le nombre 1111 pour plus de clarté, ce qui n’altère pas plus sa valeur que d’écrire 0015 en décimal.

   111    <-- retenue
  101010  <-- 42
+ 001111  <-- 15
--------
  111001  <-- 57

Ce qu’on a fait ici s’explique en d’autres termes :

En partant de la droite :
0 + 1     = 1
1 + 1     = 0, avec 1 de retenue
0 + 1 + 1 = 0, avec 1 de retenue
1 + 1 + 1 = 1, avec 1 de retenue
0 + 0 + 1 = 1
1 + 0     = 1
Pour le résultat final : 111001

La soustraction

La soustraction est une opération plus complexe que l’addition, que ce soit en décimal ou en binaire.

On a certainement au moins de vagues souvenirs de la méthode par emprunt (dite aussi par cassage), qui consiste à emprunter un chiffre de la gauche pour soustraire un chiffre plus grand d’un chiffre plus petit. Ou encore de la technique par compensation ou celle par compléments. Nous, humains, pouvons utiliser toutes ces méthodes avec nos doigts, nos crayons et nos papiers. Mais aucune n’est très pratique à effectuer pour des composants électroniques.

C’est pourquoi un ordinateur ne soustrait tout simplement pas.

Au lieu de soustraire, il est bien plus efficace d’additionner des chiffres négatifs. Alors au lieu de faire l’opération 42 - 3, par exemple, l’ordinateur préfère faire 42 + (-3). C’est une distinction subtile, mais très importante pour un ordinateur qui additionne à une vitesse fulgurante et qui ne veut pas avoir de circuits superflus pour d’autres opérations.

Pour effectuer l’opération 42 - 3 comme un ordinateur, il faut d’abord transformer le nombre positif, 3, en nombre négatif. Comme on l’a vu précédemment, l’ordinateur utilise la méthode du complément à deux :

  0000011 = 3
  1111100 -> on inverse les bits (complément à un)
+ 0000001 -> on ajoute 1 (complément à deux)
  1111101 = -3

Ensuite, on additionne 42 et -3 :

  1111     -> retenues
   0101010 = 42
+  1111101 = -3
(1)0100111 = 39 (on ignore la retenue à gauche, c'est un dépassement)

La multiplication

La table de multiplication binaire est, sans surprise, beaucoup plus facile à mémoriser que la table de multiplication décimale :

Malgré cette simplicité, l’ordinateur préfère quand même s’en passer et plutôt additionner. Pour un ordinateur, 42 x 3 c’est simplement 42 + 42 + 42, rien de plus simple !

   1 1 1   -> retenue
  00101010 ->   42
+ 00101010 -> + 42
+ 00101010 -> + 42
---------
  01111110 -> = 126

La division

Encore un coup, l’ordinateur refuse de faire des divisions à la façon humaine et s’entête avec l’addition.

Pour un ordinateur, l’opération 42/7, c’est soustraire 7 de 42 (enfin, plutôt additionner -7 et 42) jusqu’à tomber sur zéro ou un chiffre plus petit que 7, et compter le nombre de fois qu’il a fait l’opération avant de ne plus pouvoir.

42 + (-7) + (-7) + (-7) + (-7) + (-7) + (-7) = 0
       1  +   1  +   1  +   1  +   1  +   1  = 6

Ou, pour un nombre qui n’est pas divisible par 7 :

41 + (-7) + (-7) + (-7) + (-7) + (-7) = 6
       1  +   1  +   1  +   1  +   1  = 5

Comme on peut le constater, la simulation d’une division est plus compliquée pour un ordinateur que les autres opérations mathématiques. C’est en effet un processus plus lent, et si l’on souhaite optimiser un programme au maximum pour la vitesse, il faudra si possible éviter la division en faveur de la multiplication.

Conclusion

Du fait de sa nature électronique, un ordinateur ne connaît en effet que le binaire, et ne peut qu’additionner. Ce fonctionnement, pourtant très simple à petite échelle, peut faire des miracles : éditer un texte, afficher une image, simuler des mondes virtuels entier. Il suffit d’avoir des milliers de petits composants électroniques, de faire des milliards d’opérations chaque seconde.

C’est un peu comme les neurones des organismes vivants : soit il y a un signal bioélectrique, soit il n’y en a pas. Mais assez de neurones interconnectés engendrent de l’émotion, de l’imagination, du calcul, de la logique. Et peut-être même un cerveau qui peut concevoir des machines qui peuvent compter et calculer en binaire…

Sources et lectures supplémentaires

• Charles Petzold, 1999, Code: The Hidden Language of Computer Hardware and Software
• Greg Perry, 2002, Absolute Beginner’s Guide to Programming, 3rd Edition, Binary Arithmetic [InformIT]
• Wikipédia, Notation positionnelle [Wikipédia]
• Wikipédia, Système Binaire [Wikipédia]
• The Organic Chemistry Tutor, Binary Addition and Subtraction With Negative Numbers, 2’s Complements & Signed Magnitude [YouTube]
• In One Lesson, How a CPU Works [YouTube]