Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.
Types primitifs, représentation binaires, bitwises, booléens
Les activités #.dec (dec pour Découverte) consistent à étudier des présentations explicatives et à traiter tous les exercices de découverte proposés. Si vous ne répondez pas correctement à un exercice de découverte, revenez en arrière pour relire les explications et identifier la cause de votre erreur.
Les activités #.ent (ent pour Entrainement) consistent à traiter des exercices d’entraînement. Vous devez d’abord tenter de traiter ces exercices sans dévoiler d’indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de découverte ou d’entraînement précédemment traités.
Activité de découverte B.dec
B.dec1 : Base 2 et complément à 2
Prérequis
| Base 2 |
|---|
La représentation en base 2 d’un entier naturel \(x\) est une décomposition de \(x\) en puissances de 2 :
\(x = 2^{n-1} \cdot x_{n-1} + … + 2^0 \cdot x_0 = \sum_{i=0}^{n-1} 2^i \cdot x_i\).
Exemple : L’entier dont la représentation en base 10 est 19, c’est à dire \(1 \cdot 10^1 + 9 \cdot 10^0\), a pour représentation en base 2 10011, c’est à dire \(1 \cdot 2^4 + 0 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0\).
Avec \(n\) bits, on peut représenter en base 2 les entiers compris entre \(0\) et \(2^n – 1\). Par exemple, avec 4 bits on peut représenter les entiers dont les représentations en base 2 sont comprises entre 0000 et 1111 et dont les représentations en base 10 sont comprises entre 0 et 15.
Objectif
| Représenter des entiers relatifs en binaire. |
|---|
On doit représenter des entiers positifs, négatifs ou nuls par des mots binaires.
Moyen
| Complément à 2 |
|---|
La base 2 permet de représenter des entiers naturels, c’est à dire positifs ou nuls. Le codage en complément à deux permet de représenter aussi des entiers négatifs ou positifs avec des mots binaires. Plus présisément, avec \(n\) bits on peut représenter les entiers compris dans l’intervalle…
\[-2^{n-1} .. 2^{n-1}-1
\]
…En utilisant le principe suivant :
- Si \(x \geq 0\) alors la représentation en complément à 2 de \(x\) est identique à sa représentation en base 2.
- Si \(x < 0\) alors la représentation en complément à 2 de \(x\) est le représentation en base 2 de \(2^n+x\).
Exemple : Avec 4 bits, on peut représenter en complément à 2 les entiers compris entre -8 et 7.
- 3 se représente 0011, comme 3 en base 2.
- -3 se représente 1101, comme 16-3 = 13 en base 2.
- -1 se représente 1111, comme 16-1 = 15 en base 2.
Bonus
Calcul rapide de l’opposé
Il existe un moyen rapide de calculer la représentation en complément à 2 de l’opposé d’un nombre : on conserve tous les bits en partant de la droite jusqu’au premier 1 inclus et on complémente les autres.
Exemple :
La représentation en complément à 2 sur 4 bits de l’entier 6 est 0110. (Elle est identique à sa représentation en base 2 puisqu’il s’agit d’un entier positif.)
Pour obtenir la représentation de -6, on le décompose en deux parties : 01 et 10. La coupure se situe à gauche du bit à 1 en le plus à droite. On complémente la partie de gauche. On obtient 1010. Si on recommence l’opération, on obtient à nouveau la représentation de 6.

Déterminer le signe
Le signe d’un nombre est indiqué par le bit le plus à gauche de sa représentation en complément à 2. Si ce bit est 1 alors le nombre est négatif, sinon il est positif ou nul.
Exercice de découverte B.dec.x1
Donnez les représentations en complément à 2 sur 8 bits des entiers dont les représentations décimales sont -1, 7 et -2.
Pour -1, on part de le représentation en base 2 de 1 sur 8 bit, c’est à dire 0000 0001, puis on calcule l’opposé en complémentant tous les bits à gauche du bit à 1 le plus à droite, ce qui donne 1111 1111.
Pour 7, on conserve la représentation en base 2, soit 0000 0111.
Pour -2, en procédant de manière similaire à -1, on obtient 1111 1110.
Exercice de découverte B.dec.x2
Donnez les représentations en complément à 2 sur 8 bits des entiers dont les représentations en complément à 2 sur 4 bits sont 1011 et 0111.
Soit \(x\) le nombre dont la représentation en complément à 2 est 1011. Comme le bit le plus à gauche est 1, on sait que \(x\) est négatif. La représentation en base 2 de \(-x\) est 0101. Sur 8 bits, la représentation en base 2 de \(-x\) est obtenue en ajoutant quatre 0 à gauche, ce qui donne 0000 0101. Pour obtenir la représentation de \(x\) en complément à 2, il faut complémenter tous les bits à gauche du premier bit à 1 à partir de la droite. Le résultat est 1111 1011.
Il existe un raccourci pour étendre le nombre de bit d’une représentation en complément à 2 d’un nombre négatif. Il suffit d’ajouter des 1 à gauche. Ici on passe de 1011 à 1111 1011.
Le nombre représenté en complément à 2 par 0111 est positif, puisque le bit le plus à gauche est 0. Sa représentation en complément à 2 est le même que sa représentation en base 2, et c’est aussi valable sur 8 bit. La représentation de ce nombre sur 8 bit est obtenue en ajoutant des 0 à gauche. Le résultat est 0000 0111.
Exercice de découverte B.dec.x3
On considère le mot binaire 1110. Donnez l’entier \(x\) représenté par ce mot en base 2 et l’entier \(y\) représenté par ce mot en complément à 2.
Si 1110 est la représentation en base 2 de \(x\), alors \(x\) vaut 14.
Si 1110 est le représentation en complément à 2 de \(y\), alors \(y\) est négatif. Son opposé est représenté en base 2 par 0010. On a donc \(-y = 2\), d’où \(y=-2\).
B.dec2 : Représentation hexadécimale
Prérequis
| Aucun |
|---|
Objectif
| Représenter des mots binaires de manière condensée et lisible |
|---|
Il faut pouvoir retrouver facilement (de tête avec un peu d’entraînement) un mot binaire à partir de sa représentation condensée et réciproquement. La représentation en base 10 n’est pas adaptée car passer de la base 2 à la base 10, et réciproquement, nécessite des calculs.
Moyen
| Notation hexadécimale |
|---|
La représentation hexadécimale d’un mot binaire consiste à remplacer chaque groupe de 4 bits, appelé nibble, par un chiffre ou une lettre avec la correspondance suivante.
| nibble | hexa | nibble | hexa |
|---|---|---|---|
| 0000 | 0 | 1000 | 8 |
| 0001 | 1 | 1001 | 9 |
| 0010 | 2 | 1010 | A |
| 0011 | 3 | 1011 | B |
| 0100 | 4 | 1100 | C |
| 0101 | 5 | 1101 | D |
| 0110 | 6 | 1110 | E |
| 0111 | 7 | 1111 | F |
Par exemple, le mot binaire0100 1100 0111 1111 est représenté par 4C7F.
Le passage de binaire à hexadécimal est immédiat dans les deux sens. Le codage hexadécimal est couramment utilisé pour représenter des mots binaires de manière concise.
La représentation hexadécimale peut être aussi vue comme la représentation d’entiers naturels en base 16. Les lettres A à F représentent les valeurs 10 à 15.
Exercice de découverte B.dec.x4
Donnez la représentation hexadécimale du mot binaire 1101 1110 0111 0101.
DE75
Exercice de découverte B.dec.x5
Donnez le mot binaire dont la représentation hexadécimale est A31B.
1010 0011 0001 1011
Bonus
| Hexadécimal = Base 16 |
|---|
La notation hexadécimale d’un mot binaire \(m\) peut être vue comme une représentation en base 16 de l’entier dont \(m\) est la représentation en base 2. Les symboles 0 à 9 et A à F sont les chiffres de la base 16. Les symboles A à F ont une valeur de respectivement 10, 11, 12, 13, 14, et 15 unités.
Par exemple, AF34 peut se décomposer en puissances de 16 sous la forme \(10 \cdot 16^3 + 15 \cdot 16^2 + 3 \cdot 16^1 + 4 \cdot 16^0\). On peut réaliser des calculs directement en hexadécimal, mais l’intérêt reste limité.
B.dec3 : Types entiers, affichage hexa, sizeof
Prérequis
| Représentations en base 2, en complément à 2 et hexadécimale des entiers |
|---|
Objectif
| Optimiser la quantité de mémoire utilisée pour stocker des entiers. |
|---|
Certaines applications doivent traiter des millions, voire des milliards de valeurs numériques. Il serait un peu bête d’utiliser plus de mémoire que nécessaire pour représenter ces entiers. Dans certains systèmes embarqués ou objets connectés, par exemple, un gaspillage de mémoire peut augmenter de manière conséquente le coût du matériel.
Jusqu’à maintenant, nous avons utilisé le type int pour représenter les entiers. Ce type représente les entiers par des mots binaires dont la taille peut varier selon les architectures matérielles : 16 bits sur certains système embarqués avec des ressources mémoire et CPU limitées, 32 bits sur les ordinateurs que nous utilisons actuellement au quotidien (Mac, PC sous Windows ou Linux). Cette information, exprimée en nombre d’octets, peut être obtenue en utilisant l’instruction sizeof. Par exemple sizeof(int) vaut 4 sur les architecture 32 et 64 bits couramment utilisées de nos jours : les données de type int y sont représentées en mémoire par 4 octets, donc 32 bits.
Le type int étant signé, il permet de représenter des entiers positifs et des entiers négatifs. Ces entiers sont représentés en complément à 2. Dans la suite du cours, on fera toujours l’hypothèse de cette représentation sur 32 bits, sauf mention particulière. Les valeurs représentables par le type int sont donc comprises entre \(-2^{31} .. 2^{31}-1\), c’est à dire entre -2 147 483 648 et 2 147 483 647.
Les valeurs minimum et maximum du type int sont données par les constantes prédéfinies INT_MIN et INT_MAX déclarées dans le fichier d’entête limits.h.
Mais si on a besoin de représenter uniquement des valeurs positives, la moitié des mots binaires ne sont jamais utilisés. Et si on a besoin de représenter uniquement des valeurs représentables avec un seul octet, les trois quart de la mémoire utilisée est monopolisée inutilement.
Moyen
| Les types entiers signés et non signés de différentes capacités |
|---|
Type unsigned int
Il existe une version non signée du type int, le type unsigned int, noté aussi unsigned. Les entiers représentés par ce type sont tous positifs. Leurs valeurs sont comprises entre 0 et \(2^{32}-1\).
Types avec diverses tailles de représentation en mémoire
Il existe également des version signées et non signées de types représentant des entiers avec des représentations en mémoire plus petites et plus grandes que celle du type int. Par ordre de taille croissante des représentations en mémoire, nous avons char, short, int, long et long long, ainsi que les variantes non signées unsigned char, unsigned short, etc.
Si j’exécute le programme suivant sur ma machine…
int main()
{
printf("taille d'un char en octets : %ld\n", sizeof(char));
printf("taille d'un short en octets : %ld\n", sizeof(short));
printf("taille d'un int en octets : %ld\n", sizeof(int));
printf("taille d'un long en octets : %ld\n", sizeof(long));
printf("taille d'un long long en octets : %ld\n", sizeof(long long));
return 0;
}
…j’obtiens le résultat :
taille d'un char en octets : 1
taille d'un short en octets : 2
taille d'un int en octets : 4
taille d'un long en octets : 8
taille d'un long long en octets : 8
Observez d’abord le programme. le format d’affichage n’est pas %d mais %ld. Pourquoi ? Ce genre de détails, des éléments nouveaux dans les programmes qui vous sont présentés, doit attirer votre attention.
Le format %d affiche un entier en base 10 mais s’applique au type int et aux types entiers ayant une plus petite taille. Les valeurs de ces derniers sont promues en int, c’est à dire que leur représentation en mémoire est agrandie sans changement de leur valeur, avant affichage.
Mais pour afficher correctement une valeur de type long, il faut utiliser le format %ld (l pour long et d pour décimal, i.e., on demande un affichage en base 10). Or la valeur de retour de sizeof est de type long.
Maintenant, observons les résultats. On voit que chaque type a une représentation mémoire de taille différente sauf long long qui a la même taille que long. Mais sur d’autres architectures, on pourrait avoir une différence de taille entre ces deux types, de même que sur certaines architectures les int sont codés sur 2 octets comme les short.
Cette souplesse sur les représentations des entiers a permis au langage C de s’adapter aux progrès technologiques, mais peut poser problème en matière de portabilité, c’est à dire si on recompile un programme sur une architecture différente de celle d’origine. C’est pourquoi il existe aussi des types de tailles fixes, indépendantes de l’architecture et du système d’exploitation utilisés. Selon le nombre de bits de leurs représentations en mémoire, ces types sont nommés int8_t, int16_t, int32_t, etc. pour les versions signées, et uint8_t, uint16_t, etc. pour les versions non signées.
Il existe aussi un type nommé size_t dédiés aux entiers ayant vocation à représenter des tailles de données en mémoire. C’est le type de retour de sizeof. Dans les architectures 64 bits, ce type est équivalent à unsigned long.
Affichage hexadécimal des entiers
Tous les entiers peuvent être représentés dans le code source au format hexadécimal, et également affichés par printf dans ce format. Voici un exemple.
int main()
{
int a = 100;
int b = 0x100;
printf("a en décimal : %d, a en hexa : %x\n", a, a);
printf("b en décimal : %d, b en hexa : %x\n", b, b);
return 0;
}
On obtient l’affichage :
a en décimal : 100, a en hexa : 64
b en décimal : 256, b en hexa : 100
On peut donc représenter un même entier de plusieurs manières et l’afficher dans plusieurs formats.
Bonus
| Double usage du type char |
|---|
Le type char peut aussi être utilisé pour représenter des caractères imprimables, tels que 'a', 'D', '2', etc., représenter par leurs codes ASCII. Le langage C ne fait pas de différence entre les octets, les entiers codés sur 8 bits, et les caractères ASCII, qui peuvent tous être représentés par le type char. Voici un exemple.
int main()
{
char x = 'z';
char y = 69;
printf("x en décimal : %d, x en hexa : %x, x en caractère : %c\n", x, x, x);
printf("y en décimal : %d, y en hexa : %x, y en caractère : %c\n", y, y, y);
return 0;
}
L’affichage obtenu est :
x en décimal : 122, x en hexa : 7a, x en caractère : z
y en décimal : 69, y en hexa : 45, y en caractère : E
Exercice de découverte B.dec.x6
Donnez la ligne de code permettant d’afficher le caractère dont le code ASCII se note 41 en hexadécimal.
printf("%c\n", 0x41);
Exercice de découverte B.dec.x7
Donnez la ligne de code permettant d’afficher en hexadécimal le code ASCII du caractère ‘9’.
printf("%x\n", '9');
Exercice de découverte B.dec.x8
On exécute le programme suivant…
int main()
{
char c = 129;
printf("%d\n", c);
}
… et la valeur -127 est affichée à l’écran. Essayez d’expliquer pourquoi.
Les type char représente des entiers signés en complément à 2 sur 8 bits. Les valeurs représentables sont comprises entre -128 et 127. La valeur 129 n’est pas représentable. Le compilateur traduit 129 dans sa représentation en base 2, à savoir 1000 0001, et place cette valeur dans la zone mémoire où est stocké le contenu de la variable c. Or 1000 0001 est la représentation en complément à deux de l’entier négatif -127.
Si vous avez du mal à comprendre exactement ce qui ce passe, ce n’est pas grave pour l’instant. Ce que vous devez comprendre, c’est que :
- L’utilisation d’une valeur non représentable avec le type utilisé peut entraîner des comportements apparemment incohérents, et que
- Le compilateur C ne détecte pas toujours ce genre de situation.
B.dec4 : Opérations bitwises
Prérequis
| Types entiers et représentation des entiers |
|---|
Il est essentiel de comprendre que toutes les données manipulées par un ordinateur, donc en pratique les contenus de toutes les variables, sont représentés en mémoire par des mots binaires (constitué d’une suite d’octets). En particulier toute donnée, ou valeur, de type int peut être utilisée pour représenter un entier ou un mot binaire ou une valeur Booléenne. Quand on utilise la valeur dans des opérations arithmétiques, on la considère comme un entier. Mais certaines opérations que nous allons découvrir « voient » un entier comme un mot binaire. Plus précisément, ces opérations agissent sur le mot binaire représentant cet entier.
Objectif
| Lire les bits de la représentation binaire d’un entier |
|---|
Le langage C permet de représenter dans un code source des constantes entières notées en binaire. Par exemple on peut écrire…
unsigned int x = 0b111100001111;
…qui est strictement équivalent à :
unsigned int x = 0xF0F;
Par contre, aucun format d’affichage de printf ne permet d’affichage d’un entier en binaire. Nous allons donc développer une fonction permettant de le faire, ce qui permettra d’introduire de nouveaux opérateurs appelé bitwises.
Ces opérateurs permettent d’agir sur certains bits de mots binaires représentés par des valeurs de types entiers. Elle ne sont pas spécifiques au langage C. Par exemple, tous les opérateurs présentés ici sont supportés par le langage Java et bien d’autres.
Moyen
| Utiliser des opérateurs bitwises |
|---|
Les opérateurs bitwises sont le non bit à bit, noté ~, le et bit à bit, noté &, le ou bit à bit, noté |, le ou exclusif bit à bit, noté ^, le décalage à droite, noté >> et le décalage à gauche, noté <<.
Si on note, en commençant à droite, $…, b_2, b_1, b_0$ les bits d’un mot binaire représentant en mémoire un entier $b$ (et pareillement pour d’autres entiers a et c), alors les effets de ces opérateurs sont les suivants.
~aest l’entier obtenu en complémentant tous les bits de \(a\).a&best l’entier \(c\) tel que chaque \(c_i\) est le résultat d’un et logique entre \(a_i\) et \(b_i\).a|best l’entier \(c\) tel que chaque \(c_i\) est le résultat d’un ou logique entre \(a_i\) et \(b_i\).a^best l’entier \(c\) tel que chaque \(c_i\) est le résultat d’un ou exclusif entre \(a_i\) et \(b_i\).a >> nest l’entier obtenu en décalant de \(n\) positions à droite tous les bits de la représentation binaire de \(a\). Si le type de \(a\) est non signé ou si le type de \(a\) est signé et que la valeur de \(a\) est positive ou nulle, un bit 0 est introduit à gauche. Si le type de \(a\) est signé et que la valeur de \(a\) est négative, alors un bit 1 est introduit à gauche.a << nest l’entier obtenu en décalant de \(n\) positions à gauche tous les bits de la représentation binaire de \(a\) et en insérant un bit 0 à droite.
Voici quelques exemples sur des octets qui pourraient être représentés par des entiers de type unsigned char.
a : 0000 1111 a : 0000 1111
b : 0011 1100 b : 0011 1100 a : 0000 1111
----------------- ----------------- -----------------
a & b : 0000 1100 a | b : 0011 1111 ~a : 1111 0000
a : 0011 1100 a : 0011 1100
------------------ ------------------
a >> 3 : 0000 0111 a << 3 : 1110 0000
Nous allons, à titre d’exemple d’utilisation des ces opérateurs, définir une fonction qui affiche la représentation en base 2 d’un entier. Plus précisément, cette fonction a deux paramètres nommés valeur et nBits. Elle affiche les nbBits derniers bits de valeur.
Par exemple, printB2(17, 8) affichera 0001 0001, et printB2(0x17, 8 ) affichera 0001 0111.
Illustrons le principe utilisé dans le cas ou le paramètre nBits vaut 8. On crée un masque, qui est le mot binaire 1000 0000, c’est à dire avec un bit 1 dans le position du bit à afficher le plus à gauche, suivi de bits 0. Ensuite, tant que ce masque n’est pas égal à 0000 0000, on affiche le bit de valeur situé en face du bit à 1 du masque et on décale le masque d’une position vers la droite.
Voici une version incomplète qui montre l’initialisation du masque et la boucle qui fait évoluer sa valeur, mais sans entrer dans le détail d’affichage de cette valeur.
void printB2(int valeur, int nBits)
{
unsigned masque = 1 << (nBits-1);
while(masque > 0)
{
// Affichage du bit de valeur sélectionné
// par le masque.
masque = masque >> 1;
}
}
Essayez de bien comprendre le fonctionnement de cette partie du code avant de poursuivre. Vous pouvez par exemple l’exécuter à la main avec la valeur 5 et un affichage sur 4 bits, c’est à dire simuler l’exécution de printB2(5, 4). Vous pouvez vérifier votre prédiction en plaçant dans le corps de la boucle la ligne d’affichage printf("%x ", masque) et en testant sur machine l’exécution de la fonction. Vous pouvez aussi consulter la réponse cachée suivante.
Les valeurs successives du masque, en hexadécimal, sont 8, 4, 2, 1, puis la valeur 0, qui ne sera pas affichée. En binaire, ces valeurs sont 1000, 0100, 0010, 0001.
Il nous reste à compléter le code de manière à ce qu’il affiche, pour chaque valeur du masque, le bit échantillonné. Essayez de trouver une solution en utilisant l’opérateur &.
Pour déterminer la valeur du bit désigné par le masque, on peut réaliser l’opération masque & valeur. Si le bit lu vaut 0, le résultat est 0, sinon le résultat est différent de 0.
Voici le code complet de la fonction.
void printB2(int valeur, int nBits)
{
unsigned masque = 1 << (nBits-1);
while(masque > 0)
{
if(masque & valeur)
{
printf("1");
}
else
{
printf("0");
}
masque = masque >> 1;
}
}
Nouvel objectif
| Modifier certains bits dans un mot binaire sans changer les autres |
|---|
L’objectif précédent nécessitait de lire des bits dans un mot binaire représenté par une valeur de type entier. Mais il arrive qu’on souhaite modifier certains bits, par exemple quand on configure des ports d’entrées sortie de microcontrôleur, ou encore quand on gère des droit d’accès à des fichiers en programmation système sous UNIX.
Moyen
| Utilisation d’un masque et d’une opération bitwise |
|---|
Nous avons vu comment créer un masque et l’utiliser pour lire la valeur d’un bit particulier de la représentation binaire d’un entier (c’est à dire de sa représentation en mémoire). Nous allons maintenant découvrir comment modifier la valeur d’un bit.
Voici un premier exemple. Soit x une variable de type int. On souhaite mettre à 1 le bit de rang 5 dans la représentation binaire de l’entier situé x. Les rangs des bits sont numérotés à partir de 0 en partant de la droite. On peut obtenir ce résultat avec un masque et l’opérateur |.
int x = 0b00001111;
x = x | 0b00100000;
printB2(x,8); printf("\n");
On obtient l’affichage 00101111.
Incidemment, on découvre ici un moyen d’écrire un entier représenté en base 2 dans du code source en langage C. 0b000111 représente la même entier que 0b111 ou 7 ou 0x7, par exemple. (Par contre il n’existe pas de format d’affichage %b pour printf, c’est pourquoi nous avons défini une fonction printB2.)
Voici maintenant un autre exemple dans lequel on va mettre à 0 un bit de la représentation binaire d’un entier.
int x = 0b00001111;
x = x & (~ 0b00000010);
printB2(x,8); printf("\n");
On obtient l’affichage 00001101.
Le principe utilisé consiste à créer un masque dont tous les bits sont à 1 sauf celui dans la position où on souhaite placer la valeur 0 dans la donnée à modifier. On réalise alors un et bit à bit entre ce masque et la donnée à modifier.
Exercices de découverte
Exercice de découverte B.dec.x9
Le format %02x affiche un entier en représentation hexadécimal avec deux chiffres (et / ou lettres) en complétant au besoin avec des 0 à gauche. Par exemple, 9 sera affiché 09 et 2B sera affiché 2B. (On peut remplacer %02 par %03, %04, etc.)
Donnez les affichages réalisés par l’exécution des lignes de code suivantes.
printf("%02x\n", 0b111100 & 0b101);
printf("%02x\n", 0b111100 | 0b101);
printf("%02x\n", 0b111100 << 2);
printf("%02x\n", 0b111100 >> 3);
04
3d
f0
07
Exercice de découverte B.dec.x10
Soit une variable x de type unsigned int. Donnez une ligne de code permettant de mettre à 1 le bit de rang 7 de la représentation binaire du contenu de x. (Le bit de rang 7 est le 8ième en partant de la droite puisque par convention les bits sont numérotés à partir de 0.)
x = x | 0b10000000;
Exercice de découverte B.dec.x11
Donnez les affichages réalisés par l’exécution des lignes de code suivantes.
int x = 0b1111111111111111;
x = x & 0b1111011111111111;
printB2(x, 16); printf("\n");
printB2(x, 24); printf("\n");
1111011111111111
000000001111011111111111
B.dec5 : Bitwises versus Booléens
Prérequis
| Maîtriser la représentation des mots binaire par des entiers et des valeurs Booléennes vrai et faux par des entiers. |
|---|
Les entiers du langage C sont des données à usage multiple. Selon le contexte, une valeur de type int peut représenter un nombre entier, un mot binaire, un caractère imprimable, mais aussi une valeur Booléenne. Dans ce dernier cas, par convention, la valeur 0 représente faux alors que toute valeur autre que 0 représente vrai.
Objectif
| Exprimer des conditions complexes combinant plusieurs valeurs Booléennes. |
|---|
Les opérateurs bitwises ne sont pas adaptés à la réalisation d’opérations logiques sur des Booléens. L’exemple suivant permet de le constater.
int x = 1; int y = 2;
if(x & y) printf("YES\n"); else printf("NO\n");
Par convention, les entiers 1 et 2 représentent la valeur vrai. Un et logique entre les deux devrait donc avoir pour résultat la valeur vrai. Or quand on exécute les deux lignes de codes ci dessus, on obtient l’affichage NO, indiquant que 1 & 2 représente faux.
Essayez de trouver l’explication avant de la révéler.
D’un point de vue Booléen, 1 et 2 représentent tous les deux la valeur vrai et 1 && 2 a pour résultat vrai (représenté par l’entier 1). Mais d’un point de vue bitwise, 1 est représenté par le mot binaire ...0001 et 2 est représente par ...0010. Un et bitwise entre les deux a pour résultat 0, qui est interprété comme la valeur faux.
Moyen
| Pour réaliser des opérations logiques, aussi appelées Booléennes, il faut utiliser des opérateurs Booléens et non des opérateurs bitwises. |
|---|
Il est important de ne pas confondre les opérateurs bitwises et les opérateurs Booléens.
Les opérateurs bitwises agissent sur les bits des mots binaires représentant des entiers alors que les opérateurs Booléens considèrent chaque entier comme représentant une unique valeur Booléenne : la valeur 0 représente faux et toute autre valeur représente vrai.
Les opérateurs logiques suivants existent en version bitwise et en version Booléenne.
| bitwise | Booléen | |
|---|---|---|
| et | & | && |
| ou | | | || |
| non | ~ | ! |
Le résultat d’une opération Booléenne est 0 (pour faux) ou 1 (pour vrai), même si les opérandes peuvent avoir des valeurs différentes de 0 et 1 (pour mémoire, toute valeur différente de 0 sera interprétée comme vrai).
Ajoutons une ligne à l’exemple précédent.
int x = 1; int y = 2;
if(x & y) printf("YES\n"); else printf("NO\n");
if(x && y) printf("YES\n"); else printf("NO\n");
L’affichage à l’exécution est :
NO
YES
Bonus
| Opérateurs de comparaison et piège du = |
|---|
Les opérateurs de comparaisons ==, !=, <, >, >=, <= permettent de comparer des valeurs numériques, (entiers et flottants) et produise un résultat de type int représentant une valeur Booléenne. Par exemple, en exécutant la ligne suivante…
printf("%d\n", 2 != 27);
…on observe l’affichage 1 qui s’interprète comme la valeur Booléenne vrai.
Il faut prendre garde à ne pas utiliser = à la place de ==. Observons le code suivant :
int x = 0;
if(x = 17) printf("YES\n"); else printf("NO\n");
Si vous utilisez l’option de compilation -Wall ou utilisez un IDE bien configuré, vous devriez avoir un message d’avertissement à la compilation, mais cela n’empêche pas la production d’un code exécutable.
À l’exécution, on observe l’affichage YES, et ceci en raison du cumul de deux effets. Premièrement, l’instruction x = 17 ne fais pas une comparaison mais une affectation, donc x prend la valeur 17. Deuxièmement, en langage C, une affectation retourne la valeur assignée, donc x = 17 retourne la valeur 17, qui est interprétée comme le Booléen vrai.
Le langage C comporte de nombreux pièges comme celui-ci. Vous en éviterez beaucoup en prenant garde à tous les avertissements produit lors de la compilation de vos codes sources.
Exercice de découverte B.dec.x12
Une confusion entre le non bitwise ~ et le non Booléen ! peut-elle poser problème ? Si oui, donnez un exemple.
En effet, cela pose problème. Par exemple l’entier 1 représente le Booléen vrai. L’opération !1 a pour résultat 0, qui s’interprète comme le Booléen faux, tandis que ~ 1 a pour résultat l’entier représenté par le mot binaire dont tous les bits sauf le dernier sont à 1, qui s’interprète comme le Booléen vrai.
L’activité est terminée. Vous devez évaluer votre réussite de cette activité par une valeur entre 1 et 4.
- Vous n’avez presque rien compris et échoué à plus de la moitié des exercices de découverte.
- Vous estimez avoir compris une partie des explications et vous avez réussi au moins la moitié des exercices de découverte, mais certaines notions sont encore floues.
- Vous estimez avoir bien compris les explications et vous avez réussi presque tous les exercices de découverte, mais certaines notions abordées étaient nouvelles et vous penser avoir besoin d’un entrainement pour bien les assimiler et être en mesure de les utiliser en pratique.
- Vous connaissiez déjà tout ce qui a été présenté (sauf peut être quelques détails) et il ne sera pas nécessaire que vous reveniez sur ces notions.
Si votre score est 1 ou 2, vous devrez refaire cette activité rapidement, mais après au moins une nuit de sommeil, avant de passer aux activités suivantes. Si votre score est 3 ou 4, vous devez faire les activités suivantes et il ne sera pas nécessaire de revenir sur cette activité, à part pour rechercher des informations utiles pour d’autres activités.
Activité d’entrainement B.ent
Cette activité est essentielle. C’est grâce à elle que vous apprendrez vraiment à comprendre et utiliser les notions vues précédemment. Elle se décompose en plusieurs itérations : ent1, ent2, etc.
Vous devez réaliser au moins une itération et évaluer votre niveau de réussite par une valeur entre 1 et 4 selon les critères habituels. L’itération que vous avez traité le plus récemment est appelée itération courante. On appelle itération suivante celle qui suit l’itération courante, excepté si l’itération courante est la dernière disponible, auquel cas l’itération suivante est la première itération.
Si le résultat est 1, vous devrez traiter à nouveau l’activité de découverte précédente, en laissant passer au moins une nuit, avant de revenir à cette activité d’entrainement en réalisant à nouveau l’itération courante. Vous devez aussi essayer d’identifier les points de blocage et demander à votre enseignant de vous aider à les surmonter.
Si le résultat est 2, vous devrez d’abord comprendre ce qui vous a conduit à des erreurs et / ou ce qui vous a bloqué. Si vous avez des doutes, des difficultés, essayez de trouver les réponses dans les présentations et explication de l’activité de découverte précédente et demandez toute l’aide nécessaire à votre enseignant. Ensuite, vous devrez réaliser l’itération suivante de l’activité d’entraînement actuelle après un délai d’au moins deux jours et d’au plus une semaine.
Si le résultat est 3, vous devrez revenir traiter l’itération suivante après un délai de plusieurs semaines.
En traitant les exercices, vous devrez considérer que les paramètres des fonctions ont des valeurs correctes. Il ne vous est pas demandé de vérifier si certaines valeurs sont aberrantes au regard de ce que demande l’énoncé. Par exemple, si un paramètre doit être positif pour que le traitement demandé soit possible, vous considérerez que la fonction sera appelée avec une valeur positive de ce paramètre.
Vous pouvez utiliser un ordinateur pour tester vos solutions et les corriger en cas de comportement inattendu. C’est même recommandé, à condition de commencer par réfléchir avant de vous jeter sur le clavier. Si vous pensez avoir une solution différente de celle proposée, ce qui peut arriver souvent, vous ne devez en aucun cas rester dans le doute. Vous devez vérifier si votre solution est correcte ou non, soit en testant votre solution avec un ordinateur, soit en demandant à une personne enseignante.
Itération B.ent1
Exercice B.ent1.1
Sans utiliser d’ordinateur, donnez les affichages réalisés par chacune de ces lignes de code :
printf("%d ", 15 & 9);
printf("%x ", 0xA & 0x5);
printf("%d ", 0x80 | (3 << 2));
9 0 140
Exercice B.ent1.2
Vous devez réaliser une fonction uint16_t writeBit(uint16_t data, int pos, int val) qui produit l’entier obtenu en modifiant dans data le bit situé en position pos en lui donnant la valeur val. On suppose que pos est un entier compris entre 0 et 15 et que val vaut 0 ou 1. Le type uint16_t désigne des entier non signés représentés sur 16 bits. Si vous testez votre solution sur machine, ce qui est recommandé, il faudra inclure le fichier d’entête stdint.h pour pouvoir utiliser ce type.
Voici un exemple de fonction main permettant de tester votre solution.
int main()
{
uint16_t a = 0xFF00;
printB2(writeBit(a, 3, 1), 16); printf("\n");
printB2(writeBit(a, 9, 0), 16); printf("\n");
}
Pour vérifier que vous avez bien compris ce que doit faire la fonction writeBit, tentez de déterminer ce qui doit être affiché par l’exécution de ce programme. Vérifiez ensuite en regardant la réponse.
1111111100001000
1111110100000000
Si vous avez bien compris ce que doit faire la fonction writeBit, vous pouvez traiter l’exercice.
uint16_t writeBit(uint16_t data, int pos, int val)
{
uint16_t masque = 1 << pos;
if(val)
{// mettre un bit à 1
// À compléter
}
else
{// mettre un bit à 0
// À compléter
}
}
uint16_t writeBit(uint16_t data, int pos, int val)
{
uint16_t masque = 1 << pos;
if(val)
{// mettre un bit à 1
return data | masque;
}
else
{// mettre un bit à 0
return data & (~masque);
}
}
Si votre solution ne correspond pas exactement à celle-ci, vérifiez sur machine ou auprès d’une personne enseignante si elle est correcte.
Exercice B.ent1.3
Soit x une variable de type unsigned int. Donnez les lignes de code permettant de réaliser les calculs suivants en utilisant exclusivement des opérations bitwises, i.e., & ~ | ^ << >>. Le résultat doit être placé dans la variable x.
Q1. Diviser x par 8.
x = x >> 3;
Q2. Multiplier x par 4.
x = x << 2;
Q3. Calculer 4 x + 3.
x = (x << 2) | 3
Q4. Calculer x modulo 16.
x = x & 0b1111;
Pour bien comprendre cette solution, il faut comprendre que pour diviser par 16 il faut 4 décalages à droite. Les bits perdu lors d’un tels décalage représentent le reste de la division entière. On les récupère ici en mettant tous les autres à 0.
Itération B.ent2
Exercice d’entrainement B.ent2.1
Sans utiliser d’ordinateur, donnez les affichages réalisés par chacune de ces lignes de code :
printf("%d ", 16 | 1);
printf("%x ", 0xF0 & 0x1A);
printf("%d ", 0x0F | (0x800 >> 4));
17 10 143
Exercice d’entrainement B.ent2.2
Vous devez réaliser une fonction uint16_t rotateRight(uint16_t data) qui retourne l’entier dont la représentation binaire résulte d’une rotation à droite d’un mot binaire de 16 bits. Par « rotation à droite », on entend que tous les bits sauf le plus à droite sont décalés vers la droite et que le bit le plus à droite se retrouve complètement à gauche.
Par exemple, le programme de test suivant…
int main()
{
uint16_t a = 0xFF00;
uint16_t b = 0x00FF;
printf("%04x \n", rotateRight(a));
printf("%04x \n", rotateRight(b));
}
…devrait afficher :
7f80
807f
Si cela ne vous parait pas évident, représentez les données en base 2 et simulez à la main leurs rotations à droite et gauche.
1111 1111 0000 0000 -> 0111 1111 1000 0000
0000 0000 1111 1111 -> 1000 0000 0111 1111
Si vous avez bien compris en quoi consiste la rotation à droite, vous pouvez traiter l’exercice.
uint16_t rotateRight(uint16_t data)
{
int b0 = data & 1;
// À compléter
}
La variable b0 contient la valeur du bit le plus à droite. Vous pouvez obtenir le résultat recherché en combinant deux mots binaires :
- le mot obtenu en décalant
b0de 15 position à gauche, - le mot obtenu en décalant data d’une position à droite.
uint16_t rotateRight(uint16_t data)
{
int b0 = data & 1;
return (b0 << 15) | (data >> 1);
}
Des variantes sont possibles. En cas de doute, testez la votre.
Exercice d’entrainement B.ent2.3
Soit x une variable de type unsigned int. Donnez les lignes de code permettant de réaliser les calculs suivants en utilisant exclusivement des opérations bitwises, i.e., & ~ | ^ << >>. Le résultat doit être placé dans la variable x.
Q1. Multiplier x par 2.
x = x << 1;
Q2. Diviser x par 16.
x = x >> 4;
Q3. Calculer 2 x + 1.
x = (x << 1) | 1
Q4. Calculer 2 à la puissance x.
x = 1 << x;
Itération B.ent3
Exercice d’entrainement B.ent3.1
Sans utiliser d’ordinateur, donnez les affichages réalisés par chacune de ces lignes de code :
printf("%d ", 32 | 2);
printf("%x ", 0xF3 & (~ 1));
printf("%x ", 0xFF & (0xFF << 1));
34 f2 fe
Exercice d’entrainement B.ent3.2
On appelle nibbles (ou demi octet) les groupes de 4 bits d’un mots binaires. Ces groupes correspondent aussi aux symboles de la représentation hexadécimale d’un mot binaire. Par exemple, le mot binaire dont la représentation hexadécimale est 1234 (dans un code source C on l’écrirait 0x1234), et dont la représentation binaire est 0001 0010 0011 0100, possèdes 4 nibbles qui sont les mots binaires 0001 0010 0011 0100.
Vous devez réaliser une fonction uint16_t rotNibbLeft(uint16_t data) qui produit le mot binaire obtenu en réalisant une rotation à gauche des nibbles du mot binaire désigné par le paramètre data.
Pour bien vérifier que vous avez compris ce qui est demandé, essayez de déterminer l’affichage qui devra être produit par ce programme de test.
int main()
{
uint16_t data = 0x1234;
printf("%04X\n", rotNibbLeft(data));
return 0;
}
2341
Vous pouvez maintenant traiter l’exercice
uint16_t rotNibbLeft(uint16_t data)
{
uint16_t nibbleLeft = data & 0xF000;
// À compléter
}
La variable nibbleLeft est initialisée avec le nibble le plus à gauche de la donnée, c’est à dire celui qui devra se retrouver à droite dans le résultat. Il vous reste à construire le résultat à partir de ce nibble mis à la bonne place et du reste de data décalé de manière appropriée.
uint16_t rotNibbLeft(uint16_t data)
{
uint16_t nibbleLeft = data & 0xF000;
return (data << 4) | (nibbleLeft >> 12);
}
Comme toujours, si votre solution diffère quelque peu de celle donnée ici, testez là sur machine, et en cas de difficulté adressez vous à une personne enseignante, mais ne restez pas dans le doute.
Exercice d’entrainement B.ent3.3
Soit x une variable de type unsigned int. Donnez les lignes de code permettant de réaliser les calculs suivants en utilisant exclusivement des opérations bitwises, i.e., & ~ | ^ << >>. Le résultat doit être placé dans la variable x.
Q1. Multiplier x par 8.
x = x << 3;
Q2. Diviser x par 4.
x = x >> 2;
Q3. Calculer x modulo 2.
x = x & 1;
Soit x et y deux variables de type unsigned int.
Donnez, en fonction de la valeur de x, la valeur de y après l’exécution de la ligne suivante.
y = 3 << x;
\(3 \cdot 2^x\)
Activité de consolidation B.top
Réaliser cette activité consiste à traiter un des exercices de consolidation proposés. Si vous réalisez plusieurs fois cette activité, laissez passer au moins une semaine entre chaque itération et traitez à chaque fois un exercice différent.
Exercice de consolidation B.top1
Vous devez réaliser une fonction…
unsigned permute(unsigned data, unsigned pos1, unsigned pos2)
…qui retourne le mot binaire obtenu en échangeant les bits situés en positions pos1 et pos2 dans data.
Les positions des bits sont des entiers non signés. La position 0 correspond au bit le plus à droite, comme habituellement. Vous devez utiliser des opération bitwises et non des opérations arithmétiques. Vous ne devez pas utiliser de boucle.
Commencez par déterminer quels devraient être les affichages réalisés par l’exécution de la fonction main ci-dessous si la fonction permute est bien programmée.
int main()
{
printf("%04X\n",permute(0xFF00,3,11));
printf("%04X\n",permute(0x00FF,2,12));
printf("%04X\n",permute(0x0000,1,5));
printf("%04X\n",permute(0xFFFF,1,5));
return 0;
}
F708
10FB
0000
FFFF
Si vous avez bien compris ce que doit réaliser la fonction à programmer, vous pouvez continuer à traiter l’exercice.
Voici le début d’une solution.
unsigned permute(unsigned data, unsigned pos1, unsigned pos2)
{
unsigned masque1 = 1 << pos1;
unsigned masque2 = 1 << pos2;
// À compléter
}
On crée deux masques qui permettront de sélectionner les bits situés aux deux positions qui nous intéressent. On peut ensuite :
- Lire ces bits et conserver leurs valeurs dans des variables.
- Mettre à 0 les bits situés aux positions
pos1etpos2dansdata. - Créer un nouveau masque permettant, grâce à un ou bitwise avec
data, d’obtenir le résultat attendu.
Voici une version toujours incomplète, mais plus avancée de la fonction.
unsigned permute(unsigned data, unsigned pos1, unsigned pos2)
{
unsigned masque1 = 1 << pos1;
unsigned masque2 = 1 << pos2;
unsigned bit1 = (data & masque1) >> pos1;
unsigned bit2 = (data & masque2) >> pos2;
data = data & ~(masque1 | masque2); // Ligne A
// À compléter
}
Dans cette version, on a récupéré dans les variables bit1 et bit2 les valeurs des bits à échanger. Ces variables ont deux valeurs possibles, 0 ou 1, quelles que soient les positions des bits dans data.
La ligne A permet de mettre à 0 les bits situés aux positions pos1 et pos2. Il reste à construire et retourner le résultat final.
unsigned permute(unsigned data, unsigned pos1, unsigned pos2)
{
unsigned masque1 = 1 << pos1;
unsigned masque2 = 1 << pos2;
unsigned bit1 = (data & masque1) >> pos1;
unsigned bit2 = (data & masque2) >> pos2;
data = data & ~(masque1 | masque2);
return data | (bit1 << pos2) | (bit2 << pos1);
}
Cette solution n’est pas la seule possible. Si vous en avez une autre, faites des vérifications poussées de son fonctionnement.
Exercice de consolidation B.top2
Vous devez réaliser une fonction…
int seek(uint32_t data, uint32_t pattern, int n)
… qui recherche une suite de bits, constituée des n derniers bits de pattern, dans un mot binaire appelé data. La valeur de retour doit être la position de la suite de bits recherchée dans data. D’une manière plus générale, la position est le nombre de décalages à gauche à réaliser pour faire coïncider la suite de bits recherchée avec une suite identique dans data. Dans le cas où la suite recherchée n’apparaît pas dans data, la valeur de retour doit être -1.
Par exemple, l’exécution des lignes de code suivantes…
uint32_t data = 0b10101111000011001100;
uint32_t pattern = 0b1110;
printf("%d\n", seek(data, pattern, 4));
…doit produire l’affichage 11 parce qu’il faut décaler les bits de pattern de 11 positions pourplacer la séquence recherchée en face d’une séquence identique dans data.
10101111000011001100
1110...........
Quelle est la valeur affichée par l’exécution des lignes de code suivantes ?
uint32_t data = 0b10101111000011001100;
uint32_t pattern = 0b11101;
printf("%d\n", seek(data, pattern, 5));
La valeur affichée doit être -1 car la séquence recherchée n’apparait nulle part dans data.
Si vous avez bien compris ce qui est attendu, vous pouvez traiter l’exercice.
int seek(uint32_t data, uint32_t pattern, int n)
{
uint32_t masque = ~((~0) << n); // Ligne A
pattern = pattern & masque; // Ligne B
// À compléter
}
La ligne A crée un masque dont les n derniers bits sont à 1 et les autres à 0. Ce masque représente la position possible la plus à droite de la séquence de bits recherchée. Par exemple, si n vaut 5 alors le masque est ...00000011111.
La ligne B met à 0 les bits de pattern n’appartenant pas à la séquence recherchée.
Il reste à décaler les bits de masque et de pattern jusqu’à ce que les bits de pattern coïncident avec les bits de data sélectionnés par le masque.
int seek(uint32_t data, uint32_t pattern, int n)
{
uint32_t masque = ~((~0) << n);
pattern = pattern & masque;
for(int i=0; i < 32-n; i++)
{
if( /* À compléter */ )
{
return i;
}
// À compléter
}
return -1;
}
Dans cette version encore incomplète apparait la boucle permettant d’explorer toutes les positions possibles de la séquence recherchée.
int seek(uint32_t data, uint32_t pattern, int n)
{
uint32_t masque = ~((~0) << n);
pattern = pattern & masque;
for(int i=0; i<32-n; i++)
{
if((data & masque) == pattern)
{
return i;
}
masque = masque << 1;
pattern = pattern << 1;
}
return -1;
}
Voici une solution. Mais il existe un grand nombre d’autres implémentations possibles. Vérifiez votre solution de manière approfondie avec différentes données de test. Si vous n’avez pas trouvé une solution correcte, décortiquez celle proposée en vous intéressant au rôle de chaque bloc et en simulant à la main son fonctionnement.
Vous pourrez retenter de faire cet exercice sans aide dans au moins une semaine.