Big et little endian
Dans un ordinateur, toute l'information est sous forme de bits qui sont regroupés en octets. Il faut donc qu'il y ait un codage de cette information. Ce codage dépend bien sûr du type des données. Cette partie décrit les codages les plus utilisés pour les types de base, c'est-à-dire les entiers, les nombres flottants et les caractères.
Les entiers positifs sont toujours codés en base 2. Une suite bk-1,…,b0 de k bits représente l'entier n donné par la formule suivante.
n = ∑i=0k-1 bi2i.
Avec k bits, on peut donc représenter tous les entiers de l'intervalle 0 … 2k-1. Le nombre de bits utilisés pour coder les entiers dépend de la machine. C'est encore très souvent 32 bits mais l'apparition des micro-processeurs 64 bits rend le codage 64 bits de plus en plus fréquent.
Cette caractéristique décrit dans quelle ordre sont placés les octets qui représentent un entier. Dans le mode big endian les octets de poids fort sont placés en tête et occupent donc des emplacements mémoire avec des adresses plus petites. Dans le mode little endian, les octets de poids faibles sont au contraire placés en tête. Dans le cas d'entiers de 32 bits, il existe encore des modes mixtes. Cette terminologie provient du livre Les voyages de Gulliver de J. Swift.
Big et little endian
Le mode big endian accélère les opérations qui nécessitent de regarder en premier les bits de poids forts comme la recherche du signe, la comparaison de deux entiers et la division. Au contraire le mode little endian favorise les opérations qui commencent par les bits de poids faible comme l'addition et la multiplication.
| Big endian | Mixed endian | Little endian |
|---|---|---|
| Motorola 68xx, 680x0 IBM Hewlett-Packard SPARC |
Motorola PowerPC Silicon Graphics MIPS |
Intel DEC VAX |
Il s'agit d'une représentation surtout utilisée dans les premiers temps de l'informatique. La représentation BCD d'un entier n est obtenue de la manière suivante. L'entier n est écrit en décimal puis chaque chiffre décimal entre 0 et 9 est ensuite codé sur 4 bits. Il faut donc (k+1)/2 octets pour coder un nombre ayant k chiffres décimaux. Le seul intérêt de cette représentation est de faciliter l'affichage en base 10 de l'entier. Certains processeurs possédaient quelques instructions spécifiques pour traiter, en particulier pour l'addition, les entiers codés en BCD.
Il existe plusieurs façons de coder les entiers signés. La représentation avec un bit de signe est la plus simple mais elle a trop d'inconvénients pour être utilisée en pratique. La représentation biaisée est uniquement utilisée pour le codage des exposants des flottants. La représentation en complément à 2 est utilisée par tous les ordinateurs car elle facilite de nombreuses opérations.
Dans cette représentation, le bit de poids fort indique le signe du nombre avec la convention 0 pour positif et 1 pour négatif. Les bits restants sont utilisés pour coder la valeur absolue du nombre comme un nombre positif. Cette représentation semble la plus naturelle mais elle n'est pas utilisée en pratique car elle souffre de nombreux défauts dont le principal est de compliquer les additions et soustractions. En effet, pour additionner deux nombres codés de cette façon, il est nécessaire de faire une addition ou une soustraction suivant que ces deux nombres sont du même signe ou de signes différents.
Avec k bits, cette représentation permet de représenter tous les entiers de de l'intervalle -2k-1+1 … 2k-1-1. L'entier 0 a alors deux codages.
Représentation avec bit de signe sur 3 bits
Cette représentation est utilisée pour le codage des exposants des nombres flottants. Avec k bits, cette représentation permet de représenter tous les entiers de l'intervalle -2k-1 … 2k-1-1. Chaque entier n de cet intervalle est codé par le codage de n + 2k-1 comme un entier positif.
Représentation biaisée (avec un biais de 4) sur 3 bits
Cette représentation est la plus importante car c'est elle qui est utilisée dans les ordinateurs. Malgré son apparente complexité, elle simplifie de nombreuses opérations sur les entiers.
Avec k bits, cette représentation permet de représenter tous les entiers de de l'intervalle -2k-1 … 2k-1-1. Les entiers de 0 à 2k-1-1 sont codés comme les nombres positifs. Le bit de poids fort de leur représentation est donc toujours 0. Un nombre négatif n de l'intervalle -2k-1 … -1 est représenté par le codage de n+2k (qui appartient à l'intervalle 2k-1 …2k-1) sur k bits.
Dans la représentation en complément à 2, les représentations dont le bit de poids fort est 0 sont utilisées par les nombres positifs. Au contraire, les représentations dont le bit de poids fort est 1 sont utilisées par les nombres négatifs. Le bit de poids fort se comporte donc comme un bit de signe. Ceci facilite le test de signe d'un entier signé.
Représentation en complément à 2 sur 3 bits
Étant donné un entier n positif ou négatif représenté en complément à 2, l'algorithme suivant permet de calculer la représentation en complément à 2 de son opposé -n. Ceci est bien sûr possible pour toutes les valeurs de l'intervalle -2k-1 … 2k-1-1 sauf pour -2k-1 dont l'opposé n'est plus dans l'intervalle.
L'algorithme est le suivant. Soit n' la représentation en complément à 2 de n. L'algorithme comporte les deux étapes suivantes qui utilisent des opérations présentes dans tous les micro-processeurs et facilement réalisables avec des portes logiques.
Pour expliquer cette algorithme, on remarque que le complément bit à bit de m donne la différence entre le nombre écrit avec que des 1 et n', c'est-à-dire la valeur 2k-n'-1. Le résultat de l'algorithme est donc 2k-n'. Le tableau ci-dessous permet de vérifier que quel que soit le signe de n, l'algorithme donne le bon résultat. Soit n un entier positif ou négatif et soit n' son codage en complément à 2.
| Nombre n | Codage n' de n | Résultat | Nombre codé |
|---|---|---|---|
| 0 ≤ n ≤ 2k-1-1 | n' = n | 2k-n' = -n | -n |
| -2k-1+1 ≤ n ≤ -1 | n' = n+2k | 2k-n' | -n |
| n = -2k-1 | n' = 2k-1 | n' = 2k-1 | n |
Un des grands avantages de la représentation en complément à 2 est de faciliter les additions et soustractions. En effet, l'addition de deux nombres m et n se fait simplement en additionnant leur représentations m' et n'.
Le tableau ci-dessous récapitule les différents cas de l'addition suivant les signes des opérandes. Soient m et n deux entiers signés représentés sur k bits. On distingue donc les trois cas : le cas m et n positifs, le cas m positif et n négatif et le cas m et n négatifs. Le quatrième cas est omis du tableau car il est symétrique du cas m positif et n négatif. Pour chacun des cas, on donne les codages respectifs m' et n' de m et n, puis on distingue à nouveau deux sous-cas suivant la valeur de la somme m'+n'. Le résultat de l'addition de m' et n' n'est pas nécessairement m'+n' puisque m'+n' peut être supérieur à 2k et ne pas s'écrire sur k bits. Le résultat de cette addition est m'+n' si 0 ≤ m'+n' ≤ 2k-1 et m'+n'-2k si 2k ≤ m'+n' ≤ 2k+1-1. Les deux quantités Ck et Ck-1 données dans une des colonnes sont les deux retenues (carry) calculées par un additionneur pour les k et k-1 bits des deux nombres.
| Nombre m | Codage m' | Nombre n | Codage n' | Cas | Résultat | Nombre codé | Ck Ck-1 | Commentaire |
|---|---|---|---|---|---|---|---|---|
| m positif 0 ≤ m ≤ 2k-1-1 |
m' = m | n positif 0 ≤ n ≤ 2k-1-1 |
n' = n | 0 ≤ m'+n' ≤ 2k-1-1 | m'+n' | m+n | 0 0 | Résultat positif |
| 2k-1 ≤ m'+n' ≤ 2k-2 | m'+n' | m+n-2k | 0 1 | Débordement car m+n ≥ 2k-1 | ||||
| m positif 0 ≤ m ≤ 2k-1-1 |
m' = m | n négatif -2k-1 ≤ n &le -1 |
n' = n + 2k | 2k-1 ≤ m'+n' ≤ 2k-1 | m'+n' | m+n | 0 0 | Résultat négatif car |m| < |n| |
| 2k ≤ m'+n' ≤ 2k+2k-1-1 | m'+n'-2k | m+n | 1 1 | Résultat positif car |m| > |n| | ||||
| m négatif -2k-1 ≤ m &le -1 |
m' = m + 2k | n négatif -2k-1 ≤ n &le -1 |
n' = n + 2k | 2k ≤ m'+n' ≤ 2k+2k-1-1 | m'+n'-2k | m+n+2k | 1 0 | Débordement car m+n < -2k-1 |
| 2k+2k-1 ≤ m'+n' ≤ 2k+1-1 | m'+n'-2k | m+n | 1 1 | Résultat négatif |
On se place avec k = 3 bits. Les nombres représentables en compléments à deux sont donc les entiers de -4 à 3. La table ci-dessous donne pour chaque paire de représentation, la somme et sa valeur. Les valeurs des deux retenues C2 et C3 sont codées par la couleur du fond. Les couleurs jaune et rouge correspondent aux débordements, c'est-à-dire à C2 ⊕ C3 = 1.
| C2 = 0 | C2 = 1 | ||
|---|---|---|---|
| C3 = 0 | C3 = 1 | C3 = 0 | C3 = 1 |
| + | 100 -4 |
101 -3 |
110 -2 |
111 -1 |
000 0 |
001 1 |
010 2 |
011 3 |
|---|---|---|---|---|---|---|---|---|
| 100 -4 |
000 0 |
001 1 |
010 2 |
011 3 |
100 -4 |
101 -3 |
110 -2 |
111 -1 |
| 101 -3 |
001 1 |
010 2 |
011 3 |
100 -4 |
101 -3 |
110 -2 |
111 -1 |
000 0 |
| 110 -2 |
010 2 |
011 3 |
100 -4 |
101 -3 |
110 -2 |
111 -1 |
000 0 |
001 1 |
| 111 -1 |
011 3 |
100 -4 |
101 -3 |
110 -2 |
111 -1 |
000 0 |
001 1 |
010 2 |
| 000 0 |
100 -4 |
101 -3 |
110 -2 |
111 -1 |
000 0 |
001 1 |
010 2 |
011 3 |
| 001 1 |
101 -3 |
110 -2 |
111 -1 |
000 0 |
001 1 |
010 2 |
011 3 |
100 -4 |
| 010 2 |
110 -2 |
111 -1 |
000 0 |
001 1 |
010 2 |
011 3 |
100 -4 |
101 -3 |
| 011 3 |
111 -1 |
000 0 |
001 1 |
010 2 |
011 3 |
100 -4 |
101 -3 |
110 -2 |
Avec toutes les représentations étudiées, un nombre signés ou non qui peut être représenté sur k bit peut encore être représenté avec k+h bits pour tout h ≥ 0. On étudie ici comme calculer cette représentation sur k+h bits pour la représentation des nombres non signés et pour la représentation en complément à 2 des nombres signés.
Soit un nombre n positif ayant bk-1…b0 comme représentation non signée sur k bits. La représentation non signée de n sur k+h bits est simplement la représentation 0…0bk-1…b0 obtenue en ajoutant h chiffres 0 devant la représentation à k bits.
Extension non signée de k bits à k+h bits d'un entier
Soit un nombre n positif ou négatif ayant bk-1…b0 comme représentation en complément à 2 sur k bits. Si n est positif, la représentation en complément à 2 de n sur k+h bits est la représentation 0…0bk-1…b0 obtenue en ajoutant h chiffres 0 devant la représentation à k bits. Si n est négatif, la représentation en complément à 2 de n sur k+h bits est la représentation 1…1bk-1…b0 obtenue en ajoutant h chiffres 1 devant la représentation à k bits. Dans les deux cas, la représentation de n sur k+h est bk-1bk-1…bk-1bk-2…b1b0 obtenue en ajoutant h copies du bit de poids fort bk-1 devant la représentation sur k bits.
Extension signée de k bits à k+h bits d'un entier
| Représentation | Avantages | Inconvénients |
|---|---|---|
| avec bit de signe | représentation naturelle intervalle symétrique changement de signe facile |
2 représentations pour 0 comparaison difficile addition difficile |
| biaisée | comparaison facile véritable différence |
représentation de 0 intervalle non symétrique addition difficile |
| en complément à 2 | représentation de 0 bit de signe comparaison facile addition et soustraction semblables |
intervalle non symétrique |
La norme IEEE 754
définit des codages des nombres en virgule flottante sur un format de 32
bits appelé simple précision (déclaré par float en C), un
format de 64 bits appelé double précision (déclaré double
en C) et un format de 80 bits appelé précision étendue (déclaré
long double en C). Elle définit aussi les opérations
arithmétiques usuelles (+,-,×,/,√) et les arrondis à effectuer
pour ces opérations. Par contre, elle ne normalise pas les fonctions
mathématiques comme
Le codage d'un nombre est inspiré de la notation scientifique comme -1.5 × 10+3. Chaque nombre est décomposé en trois parties : signe, exposant et mantisse. Le signe est codé par le bit de poids fort. Ensuite un certain nombre de bits sont consacrés à l'exposant et le reste à la mantisse. La table ci-dessous donne le nombre de bits de chacun des éléments dans les différents formats.
| Encodage | Signe s | Exposant e | Mantisse m | Valeur d'un nombre | |
|---|---|---|---|---|---|
| Simple précision | 32 bits | 1 bit | 8 bits 1≤e≤254 | 23 bits | (-1)s× 1.m ×2e-127 |
| Double précision | 64 bits | 1 bit | 11 bits 1≤e≤2046 | 52 bits | (-1)s× 1.m ×2e-1023 |
| Précision étendue | 80 bits | 1 bit | 15 bits 1≤e≤32766 | 64 bits | (-1)s× 1.m ×2e-16383 |
Dans la table ci-dessus, la formule 1.m doit être interprétée de la façon suivante. Si les bits de la mantisse sont b1b2…bn, on a
1.m = 1 + b1/2 + b2/22 + b3/23 + … + bn/2n
Soit l'exemple en simple précision 101111110101100…0 (0xbf580000 en hexadécimal). Il se décompose en le signe s = 1, l'exposant e = 01111110 = (126)10 et la mantisse m = 1010100…0. La valeur de 1.m = 1+1/2+1/8+1/16 = 1,6875. La valeur du nombre est donc -1,6875 × 2-1 = -0,84375.
Les fonctions C suivantes permettent de considérer un flottant comme un entier et inversement afin par exemple d'afficher le codage hexadécimal d'un flottant. Il n'est pas possible d'utiliser les cast directement sur les valeurs car cela effectuerait une conversion. On utilise au contraire un cast sur les pointeurs.
// On suppose sizeof(int) == sizeof(float)
int float2int(float f) {
int* p = (int*) &f;
return *p;
}
float int2float(int n) {
float* p = (float*) &n;
return *p;
}
int main(void) {
// Float --> hexa
printf("%08x\n", float2int(-0.84375));
// Hexa --> float
printf("%g\n", int2float(0xbf580000));
}
Si le nombre de bits consacrés à l'exposant est k, la valeur de l'exposant e vérifie 0 < e < 2k-1. Les valeurs 0 et 2k-1 sont réservées pour des valeurs spéciales.
La norme prévoit quatre types d'arrondi : vers 0, vers +∞, vers -∞ ou au plus près. En théorie, l'utilisateur a le choix de l'arrondi mais aucun des langages de programmation actuels ne permet de le choisir effectivement.
Les valeurs spéciales qui peuvent être représentées sont données par la table ci-dessous dans le cas de la simple précision.
| Signe | Exposant | Mantisse | Valeur | Commentaire |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | unique représentation de 0 |
| s | 0 | m ≠ 0 | (-1)s× 0.m ×2-126 | nombres dénormalisés |
| 0 | 255 | 0 | +∞ | résultat de 1/0 |
| 1 | 255 | 0 | -∞ | résultat de -1/0 |
| 0 | 255 | m ≠ 0 | NaN | Not a Number : résultat de 0/0 ou √-1 |
Dans le cas de la simple précision, les valeurs maximales sont ± (2-2-23)×2127 ≅ 2128. La plus petite valeur positive représentable est 2-23× 2-126 = 2-149 (nombre dénormalisé).
Le codage ASCII affecte un code sur 7 bits aux principaux caractères mais pas aux caractères accentués. Il existe des extensions plus ou moins standards pour coder les caractères accentués sur un octet comme le codage ISO Latin 1.
Le codage Unicode permet de manipuler tous les caractères possibles. Il affecte en effet un code 32 bits à tous les caractères de toutes les langues. Il faut cependant faire attention au fait que les codes ne sont pas manipulés explicitement pour éviter que chaque caractère occupe 4 octets. On utilise un format de codage dont le plus répandu est le format UTF-8.