La représentation des types

Les entiers non signés

La représentation des entiers non signés étant la plus simple, nous allons commencer par celle-ci.

Dans un entier non signé, les différents bits correspondent à une puissance de deux. Plus précisément, le premier correspond à 2⁰, le second à 2¹, le troisième à 2² et ainsi de suite jusqu’au dernier bit composant le type utilisé. Pour calculer la valeur d’un entier non signé, il suffit donc d’additionner les puissances de deux correspondant aux bits à 1.

Pour illustrer notre propos, voici un tableau comprenant la représentation de plusieurs nombres au sein d’un objet de type unsigned char (ici sur un octet).

Les entiers signés

Les choses se compliquent un peu avec les entiers signés. En effet, il nous faut représenter une information supplémentaire : le signe de la valeur.

La représentation en signe et magnitude

La première solution qui vous est peut-être venue à l’esprit serait de réserver un bit, par exemple le dernier, pour représenter le signe. Ainsi, la représentation est identique à celle des entiers non signés si ce n’est que le dernier bit est réservé pour le signe (ce qui diminue donc en conséquence la valeur maximale représentable). Cette méthode est appelée représentation en signe et magnitude.

Cependant, si la représentation en signe et magnitude paraît simple, elle n’est en vérité pas facile à mettre en œuvre au sein d’un processeur car elle implique plusieurs vérifications (notamment au niveau du signe) qui se traduisent par des circuits supplémentaires et un surcoût en calcul. De plus, elle laisse deux représentations possibles pour le zéro (0000 0000 et 1000 0000), ce qui est gênant pour l’évaluation des conditions.

La représentation en complément à un

Dès lors, comment pourrions-nous faire pour simplifier nos calculs en évitant des vérifications liées au signe ? Eh bien, sachant que le maximum représentable dans notre exemple est 255 (soit 1111 1111), il nous est possible de représenter chaque nombre négatif comme la différence entre le maximum et sa valeur absolue. Par exemple -1 sera représenté par 255 - 1, soit 254 (1111 1110). Cette représentation est appelée représentation en complément à un.

Ainsi, si nous additionnons 1 et -1, nous n’avons pas de vérifications à faire et obtenons le maximum, 255. Toutefois, ceci implique, comme pour la représentation en signe et magnitude, qu’il existe deux représentations pour le zéro : 0000 0000 et 1111 1111.

Par ailleurs, il subsiste un second problème : dans le cas où deux nombres négatifs sont additionnés, le résultat obtenu n’est pas valide. En effet, -1 + -1 nous donne 1111 1110 + 1111 1110 soit 1 1111 1100 ; autrement dit, comme nous travaillons sur huit bits pour nos exemples, -3… Mince !

Pour résoudre ce problème, il nous faut reporter la dernière retenue (soit ici le dernier bit que nous avons ignoré) au début (ce qui revient à ajouter un) ce qui nous permet d’obtenir 1111 1101, soit -2.

La représentation en complément à deux

Ainsi est apparue une troisième représentation : celle en complément à deux. Celle-ci conserve les qualités de la représentation en complément à un, mais lui corrige certains défauts. En fait, elle représente les nombres négatifs de la même manière que la représentation en complément à un, si ce n’est que la soustraction s’effectue entre le maximum augmenté de un (soit 256 dans notre cas) et non le maximum.

Ainsi, par exemple, la représentation en complément à deux de -1 est 256 - 1, soit 255 (1111 1111).

Cette fois ci, l’objectif recherché est atteint !

En effet, si nous additionnons 1 et -1 (soit 0000 0001 et 1111 1111) et que nous ignorons la retenue, nous obtenons bien zéro. De plus, il n’y a plus de cas particulier de retenue à déplacer comme en complément à un, puisque, par exemple, la somme -1 + -2, soit 1111 1111 + 1111 1110 donne 1 1111 1101, autrement dit -3 sans la retenue. Enfin, nous n’avons plus qu’une seule représentation pour le zéro.

Les bits de bourrage

Il est important de préciser que tous les bits composant un type entier ne sont pas forcément utilisés pour représenter la valeur qui y est stockée. Nous l’avons vu avec le bit de signe, qui ne correspond pas à une valeur. La norme prévoit également qu’il peut exister des bits de bourrage, et ce aussi bien pour les entiers signés que pour les entiers non signés à l’exception du type char. Ceux-ci peuvent par exemple être employés pour maintenir d’autres informations (par exemple : le type de la donnée stockée, ou encore un bit de parité pour vérifier l’intégrité de celle-ci).

Les entiers de taille fixe

Face à ces incertitudes quant à la représentation des entiers, la norme C99 a introduit de nouveaux types entiers : les entiers de taille fixe. À la différence des autres types entiers, leur représentation est plus stricte :

1. Ces types ne comprennent pas de bits de bourrage ;
2. Comme leur nom l’indique, leur taille est un nombre de bits fixe ;
3. La représentation en complément à deux est utilisée pour les nombres négatifs.

Ces types sont définis dans l’en-tête <stdint.h> et sont les suivants.

Pour le reste, ces types s’utilisent comme les autres types entiers, si ce n’est qu’ils n’ont pas d’indicateur de conversion spécifique. À la place, il est nécessaire de recourir à des macroconstantes qui sont remplacées par une chaîne de caractères comportant le bon indicateur de conversion. Ces dernières sont définies dans l’en-tête <inttypes.h> et sont les suivantes.

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>


int
main(void)
{
    int16_t n = INT16_MIN;
    uint64_t m = UINT64_MAX;

    printf("n = %" PRId16 ", m = %" PRIu64 "\n", n, m);
    return 0;
}

n = -32768, m = 18446744073709551615

La représentation des types flottants amène deux difficultés supplémentaires :

• la gestion de nombres réels, c’est-à-dire potentiellement composés d’une partie entière et d’une suite de décimales ;
• la possibilité de stocker des nombres de différents ordres de grandeur, entre 10^-37 et 10³⁷.

Première approche

Avec des entiers

Une première solution consisterait à garantir une précision à 10^-37 en utilisant deux nombres entiers : un, signé, pour la partie entière et un, non signé, pour stocker la suite de décimales.

Cependant, si cette approche a le mérite d’être simple, elle a le désavantage d’utiliser beaucoup de mémoire. En effet, pour stocker un entier de l’ordre de 10³⁷, il serait nécessaire d’utiliser un peu moins de 128 bits, soit 16 octets (et donc environ 32 octets pour la représentation globale). Un tel coût est inconcevable, même à l’époque actuelle.

Une autre limite provient de la difficulté d’effectuer des calculs sur les nombres flottants avec une telle représentation : il faudrait tenir compte du passage des décimales vers la partie entière et inversement.

Avec des puissances de deux négatives

Une autre représentation possible consiste à attribuer des puissances de deux négatives à une partie des bits. Les calculs sur les nombres flottants obtenus de cette manière sont similaires à ceux sur les nombres entiers. Le tableau ci-dessous illustre ce concept en divisant un octet en deux : quatre bits pour la partie entière et quatre bits pour la partie fractionnaire.

Toutefois, notre problème de capacité persiste : il nous faudra toujours une grande quantité de mémoire pour pouvoir stocker des nombres d’ordre de grandeur aussi différents.

Une histoire de virgule flottante

Par conséquent, la solution qui a été retenue historiquement consiste à réserver quelques bits qui contiendront la valeur d’un exposant. Celui-ci sera ensuite utilisé pour déterminer à quelles puissances de deux correspondent les bits restants. Ainsi, la virgule séparant la partie entière de sa suite décimales est dite « flottante », car sa position est ajustée par l’exposant. Toutefois, comme nous allons le voir, ce gain en mémoire ne se réalise pas sans sacrifice : la précision des calculs va en pâtir.

Le tableau suivant utilise deux octets : un pour stocker un exposant sur sept bits avec un bit de signe ; un autre pour stocker la valeur du nombre. L’exposant est lui aussi signé et est représenté en signe et magnitude (par souci de facilité). Par ailleurs, cet exposant est attribué au premier bit du deuxième octet ; les autres correspondent à une puissance de deux chaque fois inférieure d’une unité.

Les quatre premiers exemples n’amènent normalement pas de commentaires particuliers ; néanmoins, les deux derniers illustrent deux problèmes posés par les nombres flottants.

Les approximations

Les nombres réels mettent en évidence la difficulté (voir l’impossibilité) de représenter une suite de décimales à l’aide d’une somme de puissances de deux. En effet, le plus souvent, les valeurs ne peuvent être qu’approchées et obtenues suite à des arrondis. Dans le cas de 0,00001, la somme 2^-24 + 2^-23 + 2^-22 + 2^-20 + 2^-19 + 2^-17 donne en vérité 0,000010907649993896484375 qui, une fois arrondie, donnera bien 0,00001.

Les pertes de précision

Dans le cas où la valeur à représenter ne peut l’être entièrement avec le nombre de bits disponibles (autrement dit, le nombre de puissances de deux disponibles), la partie la moins significative sera abandonnée et, corrélativement, de la précision.

Ainsi, dans notre exemple, si nous souhaitons représenter le nombre 32769, nous avons besoin d’un exposant de 15 afin d’obtenir 32768. Toutefois, vu que nous ne possédons que de 8 bits pour représenter notre nombre, il nous est impossible d’attribuer l’exposant 0 à un des bits. Cette information est donc perdue et seule la valeur la plus significative (ici 32768) est conservée.

Formalisation

L’exemple simplifié que nous vous avons montré illustre dans les grandes lignes la représentation des nombres flottants. Cependant, vous vous en doutez, la réalité est un peu plus complexe. De manière plus générale, un nombre flottant est représenté à l’aide : d’un signe, d’un exposant et d’une mantisse qui est en fait la suite de puissances qui sera additionnée.

Par ailleurs, nous avons utilisé une suite de puissances de deux, mais il est parfaitement possible d’utiliser une autre base. Beaucoup de calculatrices utilisent par exemple des suites de puissances de dix et non de deux.

Cet extrait sera relativement court : la représentation des pointeurs est indéterminée. Sur la plupart des architectures, il s’agit en vérité d’entiers non signés, mais il n’y a absolument aucune garantie à ce sujet.

Jusqu’à présent, nous vous avons montré les représentations binaires en ordonnant les bits et les multiplets par puissance de deux décroissantes (de la plus grande puissance de deux à la plus petite). Cependant, s’il s’agit d’une représentation possible, elle n’est pas la seule. En vérité, l’ordre des multiplets et des bits peut varier d’une machine à l’autre.

Ordre des multiplets

Dans le cas où un type est composé de plus d’un multiplet (ce qui, à l’exception du type char, est pour ainsi dire toujours le cas), ceux-ci peuvent être agencés de différentes manières. L’ordre des multiplets d’une machine est appelé son boutisme (endianness en anglais).

Il en existe principalement deux : le gros-boutisme et le petit-boutisme.

Le gros-boutisme

Sur une architecture gros-boutiste, les multiplets sont ordonnés par poids décroissant.

Le poids d’un bit se détermine suivant la puissance de deux qu’il représente : plus elle est élevée, plus le bit a un poids important. Le bit représentant la puissance de deux la plus basse est appelé de bit de poids faible et celui correspondant à la puissance la plus grande est nommé bit de poids fort. Pour les multiplets, le raisonnement est identique : son poids est déterminé par celui des bits le composant.

Autrement dit, une machine gros-boutiste place les multiplets comprenant les puissances de deux les plus élevées en premier (nos exemples précédents utilisaient donc cette représentation).

Le petit-boutisme

Une architecture petit-boutiste fonctionne de manière inverse : les multiplets sont ordonnés par poids croissant.

Ainsi, si nous souhaitons stocker le nombre 1 dans une variable de type unsigned short (qui sera, pour notre exemple, d’une taille de deux octets), nous aurons les deux résultats suivants, selon le boutisme de la machine.

Ordre des bits

Cependant, ce serait trop simple si le problème en restait là…
Malheureusement, l’ordre des bits varie également d’une machine à l’autre et ce, indépendamment de l’ordre des multiplets. Comme pour les multiplets, il existe différentes possibilités, mais les plus courantes sont le gros-boutisme et le petit-boutisme. Ainsi, il est par exemple possible que la représentation des multiplets soit gros-boutiste, mais que celle des bits soit petit-boutiste (et inversement).

Applications

Connaître le boutisme d’une machine

Le plus souvent, il est possible de connaître le boutisme employé pour les multiplets à l’aide du code suivant. Ce dernier stocke la valeur 1 dans une variable de type unsigned short, et accède à son premier octet à l’aide d’un pointeur sur unsigned char. Si celui-ci est nul, c’est que la machine est gros-boutiste, sinon, c’est qu’elle est petit-boutiste.

#include <stdio.h>


int main(void)
{
    unsigned short n = 1;
    unsigned char *p = (unsigned char *)&n;

    if (*p != 0)
        printf("Je suis petit-boutiste.\n");
    else
        printf("Je suis gros-boutiste.\n");

    return 0;
}

Le boutisme des constantes octales et hexadécimales

Suivant ce qui vient de vous être présenté, peut-être vous êtes vous posé la question suivante : si les boutismes varient d’une machine à l’autre, alors que vaut finalement la constante 0x01 ? En effet, suivant les boutismes employés, celle-ci peut valoir 1 ou 16.

Heureusement, cette question est réglée par la norme¹ : le boutisme ne change rien à l’écriture des constantes octales et hexadécimales, elle est toujours réalisée suivant la convention classique des chiffres de poids fort en premier. Ainsi, la constante 0x01 vaut 1 et la constante 0x8000 vaut 32768 (en non signé).

De même, les indicateurs de conversion x, X et o affichent toujours leurs résultats suivant cette écriture.

 printf("%02x\n", 1);

 01

Pour terminer ce chapitre, il nous reste à vous présenter quatre fonctions que nous avions passées sous silence lors de notre présentation de l’en-tête <string.h> : memset(), memcpy(), memmove() et memcmp(). Bien qu’elles soient définies dans cet en-tête, ces fonctions ne sont pas véritablement liées aux chaînes de caractères et opèrent en vérité sur les multiplets composant les objets. De telles modifications impliquant la représentation des types, nous avons attendu ce chapitre pour vous en parler.

La fonction memset

void *memset(void *obj, int val, size_t taille);

La fonction memset() initialise les taille premiers multiplets de l’objet référencé par obj avec la valeur val (qui est convertie vers le type unsigned char). Cette fonction est très utile pour (ré)initialiser les différents éléments d’un aggrégat sans devoir recourir à une boucle.

#include <stdio.h>
#include <string.h>


int main(void)
{
	int tab[] = { 10, 20, 30, 40, 50 };

	memset(tab, 0, sizeof tab);

	for (size_t i = 0; i < sizeof tab / sizeof tab[0]; ++i)
		printf("%zu : %d\n", i, tab[i]);

	return 0;
}

0 : 0
1 : 0
2 : 0
3 : 0
4 : 0

Les fonctions memcpy et memmove

void *memcpy(void *destination, void *source, size_t taille);
void *memmove(void *destination, void *source, size_t taille);

Les fonctions memcpy() et memmove() copient toutes deux les taille premiers multiplets de l’objet pointé par source vers les premiers multiplets de l’objet référencé par destination. La différence entre ces deux fonctions est que memcpy() ne doit être utilisée qu’avec deux objets qui ne se chevauchent pas (autrement dit, les deux pointeurs ne doivent pas accéder ou modifier une même zone mémoire ou une partie d’une même zone mémoire) alors que memmove() ne souffre pas de cette restriction.

#include <stdio.h>
#include <string.h>


int main(void)
{
	int n = 10;
	int m;

	memcpy(&m , &n, sizeof n);
	printf("m = n = %d\n", m);

	memmove(&n, ((unsigned char *)&n) + 1, sizeof n - 1);
	printf("n = %d\n", n);
	return 0;
}

m = n = 10
n = 0

L’utilisation de memmove() amène quelques précisions : nous copions ici les trois derniers multiplets de l’objet n vers ses trois premiers multiplets. Étant donné que notre machine est petit-boutiste, les trois derniers multiplets sont à zéro et la variable n a donc pour valeur finale zéro.

La fonction memcmp

int memcmp(void *obj1, void *obj2, size_t taille);

La fonction memcmp() compare les multiplets des objets référencés par obj1 et obj2. Si tous leurs multiplets sont égaux, elle retourne zéro. Dans le cas contraire, elle s’arrête à la première paire de multiplets qui diffère et retourne un nombre négatif ou positif suivant que la valeur du multiplet comparé de obj1 est inférieure ou supérieure à celle du multiplet comparé de obj2 (pour la comparaison, les deux valeurs sont converties en unsigned char).

#include <stdio.h>
#include <string.h>


int main(void)
{
	int n = 10;
	int m = 10;
	int o = 20;

	if (memcmp(&n, &m, sizeof n) == 0)
		printf("n et m sont égaux\n");

	if (memcmp(&n, &o, sizeof n) != 0)
		printf("n et o ne sont pas égaux\n");

	return 0;
}

n et m sont égaux
n et o ne sont pas égaux