Utilisateur:Baelde/Système binaire

Usage informatique

En langage Python ou en JavaScript, les exemples de calculs seront donnés en ligne de commande Python, ou bien en JavaScript sous forme de pseudo-adresses qui débutent par le protocole 'javascript:', à taper ou à coller dans la barre d’adresse du navigateur. Ce protocole fonctionne sur les navigateurs les plus répandus de la planète. Et on peut sous-entendre document.write(…) dans la plupart des barres d’adresses.

Cette rubrique accorde moins de place à Python qu’à JavaScript, pas du tout parce qu’un langage est moins intéressant qu’un autre. Sans installer quoi que ce soit sur leurs machines, des lecteurs très nombreux de Wikipédia peuvent demander sans délai à leur ordinateur d’effectuer les calculs proposés en JavaScript, et inventer d’autres calculs, parce que leurs navigateurs sont déjà pourvus d’un interpréteur de JavaScript.

Quand un nombre donné peut s’écrire exactement dans un système de numération donné, on peut allonger son écriture par un nombre quelconque de zéros. Par exemple, 10,00 et 10 représentent le même nombre dix dans le système décimal habituel. Mais quand on réduit au minimum le nombre des chiffres des écritures numériques, alors il correspond à chaque nombre une seule écriture mathématique minimale, et un seul codage minimal du nombre dans un langage informatique donné. Quant aux valeurs des bits d’un nombre entier en JavaScript, il y a trente-deux bits pour un entier dans le domaine des opérations bit à bit, alors une succession de 32 chiffres binaires 0 ou 1 représentera les bits d’un entier donné.

Exemples en JavaScript

Les exemples de calculs JavaScript sont donnés sous forme de pseudo-adresses, c’est-à-dire du texte brut à taper ou à copier-coller dans la barre d’adresse du navigateur. Sans retour à la ligne, car taper Entrée revient à valider le contenu de la barre d’adresse. Bien sûr, JavaScript doit être activé dans le navigateur pour qu’il produise une nouvelle page HTML, affichant le résultat du calcul demandé.

Décimal, hexadécimal et binaire

Quand on valide la pseudo-adresse ci-dessous, le navigateur donne l’écriture binaire mathématique du nombre dix, avec le minimum de chiffres, quatre chiffres : 1010. Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider :

javascript: document.write((10.00).toString(2)); 

Le chiffre 2 ci-dessus inscrit entre parenthèses est interprété dans le système décimal par le navigateur. Ce 2 représente le nombre deux, que la méthode nommée toString prend en argument. L’ordre est ainsi donné à l’interpréteur de JavaScript de convertir en base deux le nombre entier dix, codé avec deux zéros après la virgule.

L’interpréteur renvoie la chaîne '1010', parce que : $\scriptstyle {\ 10\ =\ 1\,\times \,2^{3}\ +\ 0\,\times \,2^{2}\ +\ 1\,\times \,2^{1}\ +\ 0\,\times \,2^{0}.}$

Cette égalité peut se vérifier ainsi, en utilisant le caractère * pour multiplier (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: document.write(1*2*2*2 + 1*2);

Quand une chaîne de caractères est du code JavaScript correct, la fonction eval décode la chaîne de JavaScript. Par exemple, le code suivant renvoie deux cent cinquante-cinq, la valeur finale de toto. Sa valeur initiale est une chaîne vide, à laquelle deux lettres f s’ajoutent successivement (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: toto = ""; toto = toto + "f"; toto += 'f'; toto = parseInt( toto, 16); document.write(toto); 

Convertir de base deux en base seize est facile, parce que 16 = 2⁴. Le système de numération de base seize, appelé système hexadécimal, est souvent utilisé en informatique à la place du système binaire. Chaque chiffre hexadécimal correspond à une séquence de quatre chiffres binaires. Par exemple en ajoutant toto.toString(2) à la fin de la précédente ligne de code, on obtient au type String (Chaîne en français) l’écriture binaire mathématique de l’objet numérique toto.

Dans de nombreux langages de script, les deux caractères "0x" annoncent une succession de chiffres hexadécimaux. Autrement dit, 0x ou 0X est le début d’une chaîne de chiffres du système de base seize, système où le premier chiffre est zéro, et les six derniers chiffres sont les lettres de l’alphabet de A à F, lettres majuscules ou minuscules, peu importe. Dans l’ordre alphabétique, les six derniers chiffres représentent les entiers successifs de dix à quinze. Par exemple, 255 et 256 peuvent se coder 0xFF et 0x100. JavaScript est un langage très gentil, le code 0X (code hexadécimal minimum de zéro) renvoie zéro.

Les deux valeurs possibles d’un objet booléen sont true et false (vrai et faux en français). Par exemple, la pseudo-adresse qui suit renvoie l’objet de valeur true, parce que les deux nombres ont la même valeur cent soixante de part et d’autre de l’opérateur de comparaison == (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: str = '10100000'; document.write(parseInt(str, 2) == 0xA0); 

L’écriture binaire 1010 ou le chiffre A en base 16 représente le nombre dix. La chaîne str est de longueur 8 : six zéros et deux '1'. On peut le vérifier en ajoutant le code str.length en fin de ligne.

Pour contrôler le fonctionnement d’une boucle, on peut demander à la machine d’afficher une boîte d’alerte à chaque étape du calcul, pour un petit nombre de passages dans la boucle. Par exemple à l’exécution du code ci-dessous, il faudra valider deux fois la boîte d’alerte avant que le navigateur inscrive 255 dans la page. La boucle instaurée par while ("tant que" en français) s’exécute tant que la variable vn est inférieure ou égale à nf (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: nf = 2; vn = 0; x = "0x"; while((vn += 1) <= nf ){ alert( x += "F") } x = eval(x); document.write(x); 

Si en base n l’écriture mathématique d’un entier x répète k fois le même chiffre le plus lourd, représentant n – 1, alors l’entier x + 1, égal à n^k, a une écriture mathématique de longueur k + 1 dans la même base n. Le premier chiffre est 1, il est suivi de k zéros. Dans la ligne ci-dessous, qui traite le cas où $\scriptstyle {n\ =\ 2,\ k\ =\ 31,}$ les écritures binaires 0111 et 1111 sont traduites par un 7 et un F hexadécimaux (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: nf = 7; vn = 0; x = '0x7'; while((vn += 1) <= nf ){ x += 'F'} x = eval(x); document.write(x + 1 == Math.pow(2, 31)); 

Informatique et mathématiques sont deux domaines différents. En voici une preuve. Le code suivant calcule d’abord une chaîne, l’écriture hexadécimale d’un nombre. Son chiffre F des unités représente quinze, qui est impair (non divisible par deux). Or, l’écriture décimale renvoyée se termine par zéro, chiffre pair (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: nf = 14; vn = 0; x = "0x"; while((vn += 1) <= nf ){ x += "F"} x = eval(x).toString(10); document.write(x); 

Aucun objet numérique JavaScript ne peut représenter exactement ce nombre entier codé 0xFFFFFFFFFFFFFF, avec quatorze chiffres F hexadécimaux, parce que l’interpréteur de JavaScript arrondit les entiers hors d’un certain intervalle.

Logique bit à bit

La droite Δ d’équation x = – 0,5 partage le domaine des opérations bit à bit en deux moitiés, contenant chacune 2³¹ nombres entiers. L’opérateur ~ transforme un entier n donné en –n –1. La symétrie d’axe Δ donne une image mentale de cette inversion des bits.

Moins performant que le langage Python, JavaScript effectue sur trente-deux bits ses opérations exactes bit à bit. Mentalement ou par écrit, les bits qui représentent un nombre entier se traduiront donc désormais par une liste ordonnée de 32 chiffres 0 ou 1.

Avant d’expliquer l’inversion des bits, et la représentation d’un entier négatif sur des bits, disons un mot de la « négation » d’un objet booléen. Codé ! en JavaScript, l’opérateur NON inverse la valeur true ou false (vrai ou faux) d’un tel objet. Par exemple, cinq n’est pas strictement supérieur à cinq, alors (5 > 5) renvoie false. Ci-dessous la négation renvoie true (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: document.write(!(5 > 5)); 

Les chaînes de 32 chiffres 0 ou 1 constituent un ensemble de 2³² chaînes différentes. La moitié d’entre elles ont un zéro à l’extrême gauche, au rang numéroté 31 – le chiffre des unités est au rang zéro –. Une telle écriture représente un entier positif ou nul. On l’obtient en prolongeant l’écriture mathématique binaire du nombre par des zéros à gauche, jusqu’à obtenir 32 chiffres au total. Ces chiffres ont les valeurs des 32 bits qui représentent l’entier positif. Par exemple, trente-deux bits nuls représentent le nombre zéro. Le plus grand entier du domaine des 32 bits est représenté au rang 31 par un bit nul, suivi de 31 bits de valeur 1.

Le code suivant renvoie le nombre des chiffres binaires du plus grand entier du domaine des 32 bits. En JavaScript, « pow » est l’abréviation du mot anglais power qui signifie puissance (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: x = Math.pow(2, 31) -1; x = x.toString(2); document.write(x.length); 

En supprimant la dernière instruction, on obtient la chaîne x sans aucun zéro.

Comment les 32 bits représentent un entier strictement négatif ? Pour le savoir, il suffit de connaître la relation entre l’inversion du signe d’un entier et l’inversion de ses bits. En inversant les valeurs des 32 bits d’un entier p, l’opérateur ~ le transforme en –p –1. L’image donne un moyen mnémotechnique de retenir la transformation, et les deux valeurs extrêmes du domaine des 32 bits. On appelle bit du signe d’un entier son bit le plus lourd, de rang 31, qu’on imagine comme le chiffre d’extrême gauche. Il vaut 1 si l’entier est strictement négatif, sinon il est nul.

Le code ci-dessous renvoie l’écriture binaire mathématique de – 4, nombre entier négatif dont les trente bits les plus lourds valent 1, et les deux plus légers sont nuls (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: document.write((~ parseInt('0011', 2)).toString(2)); 

La méthode x.indexOf(s) d’une chaîne x, prenant ici une chaîne s en argument, renvoie le rang dans x du premier caractère de la première occurrence de s dans x, ou bien renvoie -1 si x ne contient pas de sous-chaîne s. Dans la première instruction de la ligne suivante, les opérateurs d’inversion du signe et des bits agissent l’un après l’autre. La valeur finale de x est une chaîne de 31 chiffres 1, sans 0. La ligne de code renvoie donc –1 (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: x = ~ - Math.pow(2, 31); x = x.toString(2); document.write(x.indexOf('0')); 

Avant de parler des opérateurs ET et OU bit à bit, désignés respectivement par & et |, parlons d’abord des opérateurs logiques objet à objet, désignés respectivement par && et ||. Ces opérateurs ET et OU s’appellent aussi « conjonction » et « disjonction » logiques. Étant donnés A et B deux objets booléens JavaScript, les objets A && B et A || B sont booléens. L’objet A && B vaut true si et seulement si A et B valent true tous les deux. L’objet A || B vaut false si et seulement si A et B sont de valeur false tous les deux.

Par exemple, puisque cinq est supérieur ou égal à cinq, la pseudo-adresse ci-dessous produit true (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: document.write((5 > 5) || (5 == 5)); 

Un nombre ne représente pas nécessairement une quantité. Par exemple, si chaque objet d’une liste est booléen, de valeur true ou false, et si la longueur de la liste ne dépasse jamais 32, alors les bits d’une variable entière peuvent jouer le rôle des objets booléens. Dans un nombre entier, lire ou écrire la valeur d’un bit ou d’un ensemble de bits de rangs donnés se fera par les opérateurs logiques ET et OU bit à bit.

Par exemple, le reste de la division euclidienne d’un entier p par 8 peut se coder p % 8 . Parce que 8 = 2³, transformer p en ce reste revient à annuler tous ses bits, sauf ses trois bits les plus légers, qui sont conservés. Ce reste est codé ci-dessous sans %, mais avec l’opérateur &. La valeur de p doit rester un entier codé sur 32 bits, elle peut être négative (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: filtre = 7; p = 949; document.write(p & filtre); 

En remplaçant la valeur 7 de filtre par 0xFF, par exemple, on obtient le reste de la division euclidienne par 2⁸. En donnant à la variable filtre la valeur codée (avec 32 bits de valeur 1) ~ 0, l’entier p & filtre est égal à p (disons que cette valeur de filtre « laisse tout passer).

Par exemple deux dixièmes

Dans le système de numération binaire ou hexadécimal, deux dixièmes ou un cinquième a un développement périodique infini. Sa représentation binaire en machine est approximative.

Il suffit d’un seul chiffre décimal après la virgule pour qu’une machine informatique, ordinateur ou calculette, risque d’arrondir le nombre décimal, et d’en donner une représentation inexacte. Par exemple, la première ligne de JavaScript ci-dessous renvoie 0.2, mais sans nous renseigner sur l’état des bits qui représentent deux dixièmes. Le soupçon d’une représentation binaire approximative peut venir des deux pseudo-adresses d’après (Copier-coller et valider successivement chaque ligne dans la barre d'adresse) :

javascript: document.write(2/10);
javascript: document.write(2/10 -1 +1);
javascript: document.write((0.2).toString(16)); 

Le langage JavaScript n’est pas en cause. Quand on effectue sur papier la division de un par cinq en base 16, on commence par écrire le chiffre 0 au quotient, car 1 × 5 > 1. Sous le chiffre des unités du dividende, on inscrit le reste 1. Puis au quotient on inscrit une virgule, et on abaisse du dividende 1,0 le premier chiffre zéro. Alors on lit seize au dividende : en base seize ₍₁₆₎10 est égal à ₍₁₀₎16. En réponse à la question en seize combien de fois cinq, on pose le chiffre hexadécimal 3 juste après la virgule au quotient, et on inscrit 1 au reste, parce que trois fois cinq plus un est égal à seize. Inutile d’abaisser un deuxième zéro après la virgule du dividende, parce que la même question se répèterait : en seize combien de fois cinq. Donc le reste ne sera jamais nul, aucun quotient hexadécimal ne sera exact. Le 3 hexadécimal se répète à l’infini dans l’écriture des quotients approximatifs par défaut (trop petits), de plus en plus proches de 0,2 quand le nombre des 3 hexadécimaux augmente après la virgule, sans jamais être égal à 0,2.

Dans la même division sur papier de un par cinq en base deux, la séquence binaire 0011 se répète à l’infini au lieu du 3 hexadécimal. L’image montre cette division de un par cinq posée en base deux, avec des chiffres 2 entre parenthèses et en indice, indiquant des écritures en base deux. Le cinquième zéro après la virgule du dividende n’est pas abaissé, parce que la question en deux combien de fois cinq s’est déjà posée. La séquence binaire périodique 0011 est soulignée en rouge au quotient.

Dans la pseudo-adresse qui suit, les variables nm et dm sont des écritures hexadécimales du code qui commence par '0x'. Comptés par la variable ct, des chiffres hexadécimaux s’ajoutent à '0x' jusqu’au calcul de la fraction nm +'/ '+ dm par eval. Dans la boucle instaurée par while, le compteur ct augmente d’une unité à chaque étape, jusqu’à valoir mx + 1 à la sortie de la boucle. La chaîne nm +'/ '+ dm vaut alors '0x3333/ 0x10000', avec quatre 3 hexadécimaux au numérateur, et quatre zéros hexadécimaux au dénominateur. Il s’agit du calcul de ₍₁₆₎0,3333 en base seize, avec quatre chiffres après la virgule (Copier-coller cette ligne dans la barre d'adresse, et taper Entrée pour valider) :

javascript: ct = 0; mx = 4; nm = '0x'; dm = nm +'1'; while(( ct += 1) <= mx){ nm += '3'; dm += '0'}; document.write(eval(nm +'/ '+ dm)); 

La variable mx peut prendre d’autres valeurs entières. Par exemple en la faisant varier de 0 à 3, les calculs renvoient zéro, ₍₁₆₎0,3, ₍₁₆₎0,33, ₍₁₆₎0,333. Si après la virgule le nombre mx de chiffres hexadécimaux 3 est suffisamment grand, l’écran affiche 0,2, certes. Ce résultat est mathématiquement inexact, preuve en est la division sur papier de un par cinq en base 16 ou en base 2. En multipliant par trois la somme d’un nombre fini de puissances 1, 2, 3, et ainsi de suite, du nombre un seizième, on ne peut obtenir deux dixièmes que par un arrondi.

En JavaScript comme dans tout langage de programmation, on peut créer son propre type d’objet, et créer les opérations souhaitées sur les objets qu’on invente. Par exemple, une fonction personnelle pourrait se nommer Decimal, qui construirait nos objets décimaux personnels à partir d’écritures décimales du type String (type Chaîne). En Python, les programmeurs sont dispensés de cette tâche laborieuse grâce au module decimal. Cependant, un ensemble de bits n’est jamais extensible à l’infini, alors qu’en mathématiques une écriture décimale peut être aussi longue qu’on veut. Impossible d’avoir des représentations exactes de tous les nombres décimaux.

Un peu de Python

Très apprécié dans le monde scientifique, Python donne une représentation exacte de n’importe quel entier. Avant la version 3, le type de l’objet entier Python est int (mot réservé en Python, abréviation de « integer », signifiant « entier ») si la valeur de l’entier n’occupe pas plus de trente-deux bits. Sinon son type est long. Depuis la version 3, la conversion automatique d’un mode de calcul à l’autre existe toujours, et les calculs effectués sur plus de 32 bits restent plus lents. Mais le type renvoyé à l’utilisateur est int dans les deux cas, quelle que soit la valeur du nombre entier.

Exemple avant la version 3 :

>>> type( 2**31
... #  dans 2 puissance 31, le bit de signe est nul ;
... #  il est suivi du bit 1 le plus lourd de la
... #  valeur absolue, où les 31 autres bits sont nuls
... )
<type 'long'>
>>>

En version 3 et versions ultérieures :

>>> type( 2**31
... )  #  2 puissance 31, sur plus de 32 bits
<class 'int'>
>>>