La notation binaire

Le nombre est une abstraction. Si l'on souhaite nommer les nombres, en conserver des traces ou les manipuler (calcul), il est indispensable d'en donner des représentations, aussi adaptées que possible aux utilisations que l'on vise.

Avant d'aborder la notation binaire, nous allons survoler deux représentations couramment utilisées. Nous allons ainsi (re)découvrir les simplifications d'usage qu'elles nous apportent, dans notre vie courante.

Nous limiterons notre étude aux à l'ensemble des entiers naturels ({0,1,2,3,4,...}). Dans l'exposé qui suit, un nombre désigné par le terme générique "nombre" doit donc être compris comme un entier naturel.

Un nombre peut avoir plusieurs représentations. La plus immédiate, est la représentation par des bâtons (traits verticaux). On l'utilise quotidiennement, par exemple pour compter le nombre de personnes de présentant à un guichet. On trace un bâton sur une feuille pour chaque événement que l'on souhaite comptabiliser.

L'avantage de cette représentation vient de ce qu'elle est auto-additive, c'est-à-dire qu'en inscrivant n bâtons à la suite de p bâtons, on écrit directement le résultat de l'addition "p + n".

Exemple :

• en notation bâton, le nombre cinq se note < | | | | | >,
• le nombre trois se note < | | | >,

• en posant côte à côte les notations du nombre cinq et du nombre trois on obtient < | | | | | | | | > qui est exactement la notation du nombre huit (trois plus cinq). Cela nous paraît tellement évident qu'on ne s'en rend plus compte.

Les inconvénients de cette notation sont nombreux. Les plus criants sont les manques de compacité et de lisibilité, dès l'instant où l'on souhaite manipuler des grands nombres.

Dans la majorité des cas, on préfèrera adopter le système de numération décimal. Il fait appel à un registre plus large de symboles élémentaires, permettant ainsi une notation plus compacte. Le système est dit décimal parce qu'il utilise dix symboles élémentaires, notés conventionnellement : "0", "1", "2", "3", "4", "5", "6", "7", "8", "9". Dans ce système, la représentation d'un nombre s'obtient par combinaison ordonnée des symboles élémentaires, suivant une règle rigoureuse appelée "numération de position à base constante". Cette formule résume deux notions :

• l'emplacement d'un symbole dans le mot – représentant un nombre – détermine sa signification,
• la règle d'interprétation est la même pour tous les symboles.

En numération décimale, une unité de chaque ordre vaut toujours dix unités de l'ordre précédent.

Les avantages de ce système sont nombreux. Outre sa compacité, la numération en base dix maintient un lien avec l'outil naturel de représentation et de calcul fourni par les doigts des deux mains. La pratique de l'arithmétique élémentaire, par manipulation des représentations des nombres, s'en trouve également simplifiée ; même s'il faut des années pour en maîtriser les ressorts.

Lorsque nous multiplions un nombre par dix, nous avons pris l'habitude d'ajouter un zéro à droite. De la même manière, lorsque nous divisions un nombre (divisible) par dix, nous avons pris l'habitude de supprimer le zéro de droite. Ces deux exemples de la vie courante nous permettent de distinguer ce qui est du ressort du nombre (théorique), de ce qui touche à la technique de calcul (pratique). En effet, du point de vue de l'arithmétique (théorie), le résultat de la multiplication d'un nombre par un autre nombre existe (!) et il est unique. Mais l'arithmétique ne dit pas comment "poser" et effectuer l'opération (pratique). Cela suppose la mise en œuvre d'un système de représentation sur la base duquel nous pourrons définir un jeu de manipulations. Or, notre manière usuelle d'effectuer la multiplication ou la division par dix, dépend fondamentalement de la représentation en base dix. La facilité de calcul qui en résulte est donc une propriété du système de numération et non une propriété du nombre.

En creusant la question, on découvre que la base dix possède des propriétés un peu moins "évidentes". Ainsi, calculer le cinquième ou la moitié d'un nombre y est relativement facile. Prenons deux exemples.

Un nombre écrit en base dix sera divisible par cinq s'il se termine par 0₍₁₀₎ ou par 5₍₁₀₎. On détecte immédiatement et à coup sûr si un nombre, aussi grand soit-il, est divisible par cinq. C'est une information précieuse, mais il reste encore à "faire" le calcul.

Les lois de l'arithmétique nous apprennent que diviser un nombre quelconque par cinq, est équivalent à multiplier ce nombre par deux puis à diviser le résultat par dix.

Il en ressort qu'il existe deux méthodes différentes d'effectuer le même calcul. Quelles sont les conséquences pratiques de cette équivalence théorique ? En termes de difficulté, on serait tenté de dire qu'il est plus simple de calculer une seule opération (division par cinq) plutôt que deux (multiplication par deux et division par dix). Pourtant, si nous calculons en base dix, nous savons que la division par dix ne demande aucun effort. La difficulté de la deuxième méthode se ramène donc à celle d'une multiplication par deux, c'est-à-dire d'une simple addition…

Est-il plus simple de faire une addition ou une division par cinq ? Il n'y a malheureusement pas de réponse universelle à cette question. À de rares exceptions près, on admettra qu'ajouter un nombre à lui-même est plus facile qu'effectuer une division par cinq. La représentation des nombres en base dix est donc assez bien adaptée pour traiter les divisions par cinq.

En base dix, il existe une grande analogie entre la division par deux et la division par cinq. Ainsi, un nombre sera divisible par deux s'il se termine par un chiffre désignant un nombre divisible par deux. De même que précédemment, la division par deux pourrait être remplacée par une multiplication par cinq suivie d'une division par dix.

En pratique, cette propriété ne sera pas exploitée car la division par deux possède, de son côté, des telles propriétés qu'on la préférera à toute autre solution. En l'occurrence, la technique courante de calcul de la division par deux (chiffre par chiffre, de gauche à droite) ne génère que des retenues égales à un ou à zéro, facilement manipulables. De plus, en base dix, la reconnaissance immédiate des multiples de deux se combine à une table de division – par deux – limitée à dix formules indispensables.

Nous sommes tellement habitués à manipuler des nombres dans leur représentation décimale, que nous ne savons plus si les astuces que nous utilisons découlent de :

• propriétés spécifiques à la base dix,
• propriétés des systèmes de numération de base constante,
• propriétés formelles de l'arithmétique.

Par exemple, tout système de numération de position à base constante se prête naturellement à la multiplication et à la division par sa base. Ainsi, en base trois mille quatre cent vingt-sept, le résultat de la multiplication par trois mille quatre cent vingt-sept s'écrit simplement en "plaçant" à droite le symbole représentant le nombre zéro. Et le résultat de la division par trois mille quatre cent vingt-sept s'écrit en supprimant le zéro le plus à droite. Cette base "tordue" ne présente qu'un intérêt démonstratif.

À travers l'histoire, les sociétés humaines ont forgé des systèmes adaptés aux rapports sociaux, politiques, techniques et économiques qu'elles ont portés. Le système à base douze a rencontré un vif succès en raison des facilités qu'il offre pour la divisibilité par deux, trois et quatre. Plus récemment, le développement de l'informatique a été l'élément moteur dans la diffusion du système à base deux (ou système binaire).

Comme pour le système décimal, le choix du système binaire s'est appuyé sur des caractères physiques et des propriétés formelles. Dans le contexte d'émergence des premiers ordinateurs, les secondes ont supplanté les premiers. La propriété formelle fondamentale de la représentation binaire est d'offrir un cadre simple d'unification de l'arithmétique et de la logique. Au plan physique, l'expansion de la numérisation a renforcé la recherche de dispositifs concrets à états séparables, mesurables et contrôlables. En se limitant à deux états, il était possible d'accroître la fiabilité du dispositif d'ensemble.

En binaire, tout nombre est représenté par des combinaisons de deux symboles. Il est d'usage d'utiliser les chiffres "0" et "1". L'inconvénient de cette notation est qu'elle peut prêter à confusion avec la représentation décimale. En effet, deux nombres différents pourront avoir la même notation en décimal et en binaire. Par exemple, en notation binaire, "1001" représente le nombre neuf ! Lorsqu'il y a un risque d'ambiguïté sur le système de numération, on prend l'habitude de noter la base en indice :

Comme nous l'avons évoqué à plusieurs reprises, les systèmes de numération à base constante partagent certaines propriétés. En binaire, rien de plus facile que de multiplier un nombre par deux.

Si l'on décortique la représentation binaire d'un nombre, on voit s'établir un parallèle avec le système décimal. Dans ce dernier, en lisant les chiffres de droite à gauche, on voit "défiler" les unités, les dizaines, les centaines, les milliers, les millions, les milliards, etc. Ces grandeurs (ou ordres) désignent les puissances successives de dix. Mathématiquement on les notera, en base dix, respectivement : 10⁰, 10¹, 10², 10³, 10⁴, 10⁵, etc. Et le nombre 3927₍₁₀₎ est bien égal à :

En notation binaire, on vérifiera de manière analogue que le nombre 1001₍₂₎ (neuf) est bien égal à :

Poursuivons l'analogie avec la notation décimale en examinant les ordres successifs de la notation binaire :

On voit ainsi apparaître les puissances successives de deux, comme on voyait apparaître les puissances successives de dix. On constatera également que la technique de réalisation des opérations arithmétiques n'est pas modifiée par le changement de base.

Petite explication : sachant que "un plus un" vaut "deux", la retranscription en binaire donnera 1₍₂₎ + 1₍₂₎ = 10₍₂₎. Comme nous l'avons appris à l'école, lorsqu'on effectue la somme sur une colonne, on ne "pose" jamais un nombre à deux chiffres. Dans cette situation, on pose le chiffre des unités et on retient le chiffre d'ordre supérieur. Pour effectuer la somme "1₍₂₎ + 1₍₂₎", on pose 0₍₂₎ et on retient 1₍₂₎. Il en va de même pour "1₍₂₎ + 1₍₂₎ + 1₍₂₎" qui vaut trois (11₍₂₎), on pose 1₍₂₎ et on retient 1₍₂₎".

Avec le développement de la numérisation, le nombre d'états que l'on peut décrire avec un nombre donné de chiffres binaires (ou bit) est devenu un paramètre déterminant des applications informatiques. Or le nombre d'états est exactement égal au plus grand nombre représentable, augmenté d'une unité (on considère que le zéro "code", lui aussi, un état). Antérieurement à ce mouvement, le développement des ordinateurs a consacré le groupe de huit bit (ou octet) comme unité de base de représentation. C'est pourquoi de nombreux systèmes d'encodage dépendent de l'octet.

Pour l'encodage des caractères, la norme ASCII s'est contentée de sept bit, le huitième étant réservé au contrôle d'intégrité des textes lors des échanges. La norme ISO-8859-1, utilise les huit bits pour coder des caractères, multipliant par deux le nombre de symboles disponibles, mais continue à buter sur les limites de l'octet.

Le codage et la restitution des couleurs, sur les ordinateurs et les périphériques informatiques, subissent des contraintes du même ordre. Ainsi, parle-t-on d'image ou d'affichage en 256₍₁₀₎ couleurs (8₍₁₀₎ bit), en milliers de couleurs (16₍₁₀₎ bit soit 2₍₁₀₎ octet) ou en millions de couleurs (24₍₁₀₎ bits soit 3₍₁₀₎ octet). Un cas particulier, le codage en 16₍₁₀₎ couleurs (4₍₁₀₎ bit) n'est rien d'autre qu'un compactage de deux informations sur un seul octet. On considère alors que l'octet se compose de deux quartets (en anglais nibble).

L'octet devient ainsi l'unité de mesure de la quantité de bits nécessaires pour représenter une donnée numérique (texte numérique, image numérique, son numérique, etc.), ainsi que l'unité de mesure des capacités matérielles des équipements servant à stocker, traiter, transmettre ces données. À l'instar des autres unités de mesures – comme le mètre ou l'ampère – l'octet possède ses multiples : le kilo-octet, le mega-octet, le giga-octet, le tera-octet, etc. Il ne s'agit pourtant que d'une similitude. En effet, la révolution du système de "poids et mesures" a été de pair avec la quasi-généralisation du système décimal. Ainsi, un kilogramme vaut exactement mille grammes, une tonne vaut exactement mille kilo, une mega-tonne vaut exactement un million de tonnes… Le recours systématique à un facteur multiplicateur égal à mille découle directement du fait que : mille = 10³₍₁₀₎.

Or l'octet tire sa signification de la représentation binaire. Afin de préserver la cohérence du système de représentation, il est souhaitable de tout exprimer dans la même base. L'astuce consiste à trouver une puissance de deux qui soit voisine du nombre mille. Ainsi, on conserve simultanément l'intégrité de système binaire et l'appréhension intuitive des ordres de grandeurs héritée de notre manipulation quotidienne du système décimal. Le problème est résolu en posant la convention suivante : le "kilo binaire" vaut 2¹⁰_(10), soit 1024₍₁₀₎. Il est donc un peu plus "lourd" que le "kilo décimal". Un kilo-octet "pèse" donc 1024₍₁₀₎ octets, un mega-octet "pèse" 1 048 576₍₁₀₎ octets, etc. L'objectif est rempli puisque l'approximation est de 3% pour le kilo, 5% pour le mega, et 7% pour le giga. Autrement dit, l'ordre de grandeur de l'approximation est compatible avec l'erreur sur l'ordre de grandeur que l'on commet intuitivement.

Comment s'écrit le nombre 3427₍₁₀₎ en base deux ? Avec un peu d'entraînement, un stylo et un post-it, on décompose rapidement ce nombre en puissance de deux :

Mais cette technique n'est applicable que pour des nombres relativement petits, puisqu'elle suppose de connaître par cœur les puissances de deux encadrant le nombre à convertir. Heureusement, il existe une méthode systématique permettant de convertir n'importe quel nombre. Son avantage est de n'exiger d'autre savoir-faire que la division par deux, en système décimal. Son inconvénient est sa lourdeur.

Elle consiste en des divisions successives par deux, jusqu'à ce que le quotient soit nul. Les restes des divisions (toujours égaux à 0 ou 1) sont les bits de la représentation binaire, de droite à gauche, des unités vers les ordres supérieurs. Expérimentons cette méthode à travers un exemple simple : la conversion de 142₍₁₀₎ en binaire.

Le manque de compacité de la représentation binaire a conduit, dans certains cas, à adopter d'autres bases avec lesquelles la conversion depuis et vers la base deux est simple. Pour notre plus grand malheur, l'exemple précédent montre que la base dix n'est pas un bon candidat… En revanche, la base seize (notation hexadécimale), présente trois propriétés intéressantes.

Seize étant une puissance de deux (2⁴₍₁₀₎), il en découle que tout nombre écrit en binaire peut être immédiatement décomposé en puissances de seize. Par exemple, on écrira que 10001110₍₂₎ est égale à : 1110₍₂₎ fois 16⁰₍₁₀₎ plus 1000₍₂₎ fois 16¹₍₁₀₎. On l'exprime implicitement lorsqu'on écrit : 1000 1110. Nous faisons la même chose, en décimal, lorsque nous séparons visuellement les milliers, millions et milliards, qui sont des puissances de dix (3,6,9).

Parmi toutes les puissances de deux, seize est (avec 256₍₁₀₎) la seule qui fournisse une décomposition en octets. Ce groupage est intéressant car l'octet (et ses multilples) est une unité de codage souvent utilisée. Certes, un octet étant composé de deux quartets, deux chiffres hexadécimaux seront nécessaires pour représenter ce qui est représentable sur huit bits. L'utilisation de la base 256₍₁₀₎ aurait permis une correspondance parfaite. Mais elle pose un problème majeur que résout la base seize…

Un système de numération ne sert à rien s'il ne permet pas une manipulation aisée des nombres. En notation hexadécimale, il suffit – par définition – de seize symboles de base (alphabet ou chiffres) pour écrire n'importe quel nombre. C'est là un avantage décisif sur la base 256₍₁₀₎ qui demanderait un alphabet de 256₍₁₀₎ chiffres !

Les symboles hexadécimaux usuels sont les suivants :

En reprenant les deux nombres 3427₍₁₀₎ et 142₍₁₀₎,

Il suffit donc de mémoriser une table de trente deux éléments pour assurer la conversion instantanée de la base seize à la base deux, ou inversement.