Binaire, hex, et représentation des nombres

Aujourd'hui on se rapproche un peu de la machine pour avoir une idée de ce qui se passe quand on manipule des nombres en programmation.

Il y a beaucoup à dire sur le sujet mais j'ai essayé de rester concis en donnant des pistes à ceux qui voudraient creuser.

Système de numération et base

Dans un système de numération de type positionnel, la valeur d'un chiffre dépend de son symbole et de sa position dans un nombre. L'ordre de grandeur de chaque position correspond aux puissances de sa base.

On illustre ça en base 10 avec le raisonnement du développement décimal :

245610 = 2·103 + 4·102 + 5·101 + 6·100

Les anglo-saxons parlent d'expansion et le principe s'applique à n'importe quelle base, ci-dessous en base 2 :

11012 = 1·23 + 1·22 + 0·21 + 1·20

Les algorithmes de conversions entre bases se fondent sur ce principe.

Binaire

En informatique on utilise la base 2 : le binaire.

La donnée de base est le bit (binary unit). Sa valeur logique est 0 ou 1. Sa valeur physique peut être un voltage.

Toute information peut être représentée par un groupement comportant un nombre fixe de bits. On parle de chaînes binaires ou de mots. Sans nombre fixe, l'ordinateur ne saurait pas où commence ni où se termine une information.

Une chaîne de 8 bits est appelée un octet. L'octet est utilisé en tant qu'unité de taille en informatique.

En programmation on écrit (souvent) les chaînes binaires de droite à gauche :

• le bit le plus à droite est le bit de poids faible (least significant bit, LSB)
• le bit le plus à gauche est le bit de poids fort (most significant bit, MSB)

Avec n bits, on a 2n possibilités de valeurs différentes (2 car un bit ne peut prendre que deux valeurs 0 ou 1), et puisque le 0 est inclus la plus grande valeur sera 2n - 1.

Hexadécimal

Pour simplifier la lecture pour les humains, le système hexadécimal (base 16) est aussi utilisé.

C'est un système multiple de la base binaire (16 est multiple de 2).

Une chaîne de 8 bits peut être séparée en deux chaînes de 4 bits.

Une chaîne de 4 bits peut prendre 24 soit 16 valeurs différentes.

Donc en base 16 :

• 1 chiffre hexadécimal correspond à 4 bits
• 2 chiffres hexadécimaux correspondent à 1 octet (c.f. hexdump -C) c.q.f.d.

Ça facilite les conversions.

Pour aller de l'hexadécimal vers le binaire, il suffit de remplacer un chiffre hexadécimal par son groupe de 4 bits équivalent. Ça se fait facilement de tête soit en connaissant la table de correspondance, soit en utilisant les puissances de 2 (convertir de 0 à 15 vers le binaire avec des puissances de 2 est très facile).

La conversion dans l'autre sens fonctionne par groupes de 4, la somme des puissances de 2 de chaque groupe correspond à un symbole hexadécimal :

0000 0100 1010 1111 = 04AF = 0x4AF (0x est la convention du langage C pour décrire de l'hexadécimal, c'est # en CSS)

Représentation des entiers naturels

Les entiers sont représentés avec des chaînes de bits de longueur fixe. Je vais me baser ici sur 64 bits car c'est la norme dans la plupart des architectures actuelles.

La valeur des nombres représentés par chaque chaîne de bit peut être interprétée de façon arbitraire.

Pour représenter des entiers non signés (positifs), on dispose de 264 possibilités différentes au maximum.

En pratique, on a besoin de nombres négatifs.

Les entiers signés ou relatifs (négatifs et positifs) sont souvent représentés avec la technique du complément à deux.

Cette représentation est pratique car elle permet aux opérations de soustraction de réutiliser les circuits d'addition du processeur.

Le principe est basé sur l'arithmétique modulaire et la méthode de soustraction par complément.

Pour faire une analogie avec une horloge de 12h : soustraire 4h revient à ajouter 8h (8h = 12h - 4h, 8 est le complément à 12 de 4), on ne s'occupe pas de la retenue quand on passe un tour. On considère que 8 représente -2. En arithmétique modulo n, on soustrait 𝒙 en ajoutant n - 𝒙.

Une retenue dans une opération symbolise le passage d'un tour. Le système fonctionne très bien tant que la somme est représentable (tant qu'elle tient sur 64 bits). Sinon, c'est le dépassement d'entier qui peut se produire lors d'opérations sur deux nombres de même signe.

La moitié des 2⁶⁴ possibilités de combinaisons de bits différentes est utilisée pour représenter les nombres positifs, l'autre moitié pour représenter les nombres négatifs :

• les valeurs positives sont représentées comme attendu en partant de l'équivalent binaire de 0, leur bit de poids fort commence toujours par 0
• les valeurs négatives sont représentées par leur complément à 2⁶⁴, leur bit de poids fort commence toujours par 1

Comme le bit de poids fort est utilisé afin d'identifier un complément, on perd une place dans la fourchette des résultats qu'il est possible de représenter : [−264 − 1 ; 264 − 1 − 1]. Il y a plus de valeurs négatives que de valeurs positives.

Un développeur vous expliquera comment trouver le complément à 2 de la manière suivante :

1. Prenez la représentation binaire du nombre que vous voulez mettre au négatif
2. Inversez tous ses bits
3. Ajouter 1

Pourquoi inverser et ajouter 1 ? C'est une astuce pour éviter des calculs impliquant trop de retenues dans le calcul du complément. Par exemple, pour trouver le complément à 100 de 17, plutôt que de soustraire de 100 on peut soustraire de 99 puis ajouter 1 pour être certain de ne jamais avoir de retenue.

C'est pareil en binaire, plutôt que de soustraire de 2⁶⁴ dont la valeur binaire est 10000… (suivi de plein de 0), on retranche 1 pour soustraire de 1111… (suivi de plein de 1) et la soustraction depuis des 1 est facile : 1 - 1 = 0 et 1 - 0 = 1, ce qui revient à inverser les bits. On ajoute le 1 à la fin pour rétablir la balance.

Certains langages permettent de manipuler des nombres à précision arbitraire. Vous pouvez lire ici comment Python fait sa cuisine interne.

Représentation des réels

Une partie des réels contient une suite infinie de décimales.

Pour les représenter avec un nombre fixe de bits, on utilise les nombres flottants qui en donnent une approximation.

Parmi toutes les façons d'implémenter les nombres flottants, la norme IEEE 754 fait le consensus actuellement.

Elle définit plusieurs formats dont la double précision, format utilisé par JavaScript que je vais prendre en exemple ici.

Le principe de la norme est d'utiliser la notation scientifique en base 2 pour représenter les réels.

En double précision, des conteneurs de 64 bits sont utilisés et divisés en trois sections pour stocker la notation scientifique :

• S : 1 bit pour le signe (0 pour un nombre positif, 1 pour un nombre négatif)
• E : 11 bits pour l'exposant
• M : 52 bits pour la mantisse (ou significande) qui représente la précision

À cause du nombre fixe de bits, il y a deux restrictions :

• un nombre limité de chiffres dans la mantisse (252)
• un intervalle limité d'exposants [-1022 ; 1023] soit 2046 valeurs possibles (en fait avec 11 bits on a 2048 valeurs possibles mais certaines sont réservées pour les cas de sortie des limites des exposants ou les cas spéciaux 0, NaN etc.)

La valeur décimale d'un nombre IEEE stocké de cette façon est donné par la formule suivante :

(-1)S * 1,M * 2(E - décalage)

Dans cette formule :

• c'est les valeurs décimales du signe S, de la mantisse M et de l'exposant E qui sont utilisées
• dans 1,M, 1 est concaténé à la mantisse M car il n'est pas codé en machine (c'est le bit caché ou bit implicite)
• l'exposant est décalé car il est stocké sous forme d'un nombre non signé en machine

Fabien Sanglard utilise une autre approche pour expliquer la virgule flottante et propose de considérer :

• l'exposant comme une fenêtre entre deux puissances de 2 consécutives [0.25 ; 0,5] [0,5 ; 1] [1 ; 2] [2 ; 4] etc.
• la mantisse comme un décalage à l'intérieur de cette fenêtre

Avec la fenêtre et le décalage, on peut donner l'approximation d'un nombre. La fenêtre est une protection contre le dépassement. Une fois qu'un maximum est atteint dans une fenêtre, on la fait flotter pour représenter le nombre à l'intérieur de la prochaine fenêtre en contrepartie d'une petite perte de précision car la fenêtre d'après est deux fois plus large.

En suivant cette logique on peut représenter par exemple 0.3 en double précision :

• 0.3 est positif, donc S = 0
• 0.3 se trouve dans la fenêtre [2-2 ; 2-1] (soit [0.25 ; 0.5]) qui commence à 2-2, il faut trouver la valeur de notre exposant -2 après décalage : E - 1023 = -2, donc E = 1021
• il y a 252 possibilités de décalage pour placer 0.3 dans l'intervalle [0.25 ; 0.5], il faut trouver sa place dans l'intervalle : 0.3 - 0.25/0.5 - 0.25 = 0.2, donc M = 252 * 0.2 = 900 719 925 474 099

Vous pouvez vérifier ce calcul en allant voir sa représentation binaire et constater que l'approximation de 0.3 en machine vaut 0.299999999999999988898.

Pour finir, sachant qu'une puissance négative représente le nombre de décimales après 0, on peut se faire une idée de la quantité de nombres en virgules flottantes contenus dans l'intervalle [0 ; 1] !