Manipulation des bits

Présentation

Le langage C définit six opérateurs permettant de manipuler les bits :

• l’opérateur « et » : & ;
• l’opérateur « ou inclusif » : | ;
• l’opérateur « ou exclusif » : ^ ;
• l’opérateur de négation ou de complément : ~ ;
• l’opérateur de décalage à droite : >> ;
• l’opérateur de décalage à gauche : <<.

Les opérateurs « et », « ou inclusif » et « ou exclusif »

Chacun de ces trois opérateurs attend deux opérandes entiers et produit un nouvel entier en appliquant une table de vérité à chaque paire de bits formée à partir des bits des deux nombres de départs. Plus précisément :

• L’opérateur « et » (&) donnera 1 si les deux bits de la paire sont à 1 ;
• L’opérateur « ou inclusif » (|) donnera 1 si au moins un des deux bits de la paire est à 1 ;
• L’opérateur « ou exclusif » (^) donnera 1 si un seul des deux bits de la paire est à 1.

Ceci est résumé dans le tableau ci-dessous, donnant le résultat des trois opérateurs pour chaque paire de bits possible.

L’exemple ci-dessous utilise ces trois opérateurs. Comme vous le voyez, les bits des deux opérandes sont pris un à un pour former des paires et chacune d’elle se voit appliquer la table de vérité correspondante afin de produire un nouveau nombre entier.

#include <stdio.h>


int main(void)
{
    int a = 0x63; /* 0x63 == 99 == 0110 0011 */
    int b = 0x2A; /* 0x2A == 42 == 0010 1010 */

    /* 0110 0011 & 0010 1010 == 0010 0010 == 0x22 == 34 */
    printf("%2X\n", a & b);
    /* 0110 0011 | 0010 1010 == 0110 1011 == 0x6B == 107 */
    printf("%2X\n", a | b);
    /* 0110 0011 ^ 0010 1010 == 0100 1001 == 0x49 == 73 */
    printf("%2X\n", a ^ b);
    return 0;
}

22
6B
49

L’opérateur de négation ou de complément

L’opérateur de négation a un fonctionnement assez simple : il inverse les bits de son opérande (les uns deviennent des zéros et les zéros des uns).

#include <stdio.h>


int
main(void)
{
    unsigned a = 0x7F; /* 0111 1111 */

    /* ~0111 1111 == 1000 0000 */
    printf("%2X\n", ~a);
    return 0;
}

FFFFFF80

Ainsi, les exemples suivants sont susceptibles de produire des valeurs incorrectes (à supposer que la taille du type int soit de quatre octets sans bits de bourrages).

/* Invalide en cas de représentation en complément à deux ou signe et magnitude */
int a = ~0x7FFFFFFF;
/* Idem */
int b = 0x00000000 | 0x80000000;
/* Invalide en cas de représentation en complément à un */
int c = ~0;
/* Idem */
int d = 0x11110000 ^ 0x00001111;

Les opérateurs de décalage

Les opérateurs de décalage, comme leur nom l’indique, décalent la valeur des bits d’un objet d’une certaine quantité, soit vers la gauche (c’est-à-dire vers le bit de poids fort), soit vers la droite (autrement dit, vers le bit de poids faible). Ils attendent deux opérandes : le nombre dont les bits doivent être décalés et la grandeur du décalage.

L’opérateur de décalage à gauche

L’opérateur de décalage à gauche translate la valeur des bits vers le bit de poids fort. Les bits de poids faibles perdant leur valeur durant l’opération sont mis à zéro. Techniquement, l’opération de décalage à gauche revient à calculer la valeur de l’expression a × 2^y.

#include <stdio.h>


int
main(void)
{
    /* 0000 0001 << 2 == 0000 0100 */
    int a = 1 << 2;
    /* 0010 1010 << 2 == 1010 1000 */
    int b = 42 << 2;

    printf("a = %d, b = %d\n", a, b);
    return 0;
}

a = 4, b = 168

L’opérateur de décalage à droite

L’opérateur de décalage à droite translate la valeur des bits vers le bit de poids faible. Dans le cas où le premier opérande est un entier non signé ou un entier signé positif, les bits de poids forts perdant leur valeur durant l’opération sont mis à zéro. Si en revanche il s’agit d’un nombre signé négatif, les bits perdant leur valeur se voient mis à zéro ou un suivant la machine cible. Techniquement, l’opération de décalage à droite revient à calculer la valeur de l’expression a / 2^y.

#include <stdio.h>


int
main(void)
{
    /* 0001 0000 >> 2 == 0000 0100 */
    int a = 16 >> 2;
    /* 0010 1010 >> 2 == 0000 1010 */
    int b = 42 >> 2;

    printf("a = %d, b = %d\n", a, b);
    return 0;
}

a = 4, b = 10

Opérateurs combinés

Enfin, sachez que, comme pour les opérations arithmétiques usuelles, les opérateurs de manipulation des bits disposent d’opérateurs combinés réalisant une affectation et une opération.

Les masques

Une des utilisations fréquentes des opérateurs de manipulation des bits est l’emploi de masques. Un masque est un ensemble de bits appliqué à un second ensemble de même taille lors d’une opération de manipulation des bits (plus précisément, uniquement les opérations &, | et ^) en vue soit de sélectionner un sous-ensemble, soit de modifier un sous-ensemble.

Modifier la valeur d’un bit

Mise à zéro

Cette définition doit probablement vous paraître quelque peu abstraite, aussi, prenons un exemple.

unsigned short n;

Nous disposons d’une variable n de type unsigned short (que nous supposerons composées de deux octets pour nos exemples) et souhaiterions mettre le bit de poids fort à zéro.

Une solution consiste à appliquer les opérateurs de manipulation des bits afin d’obtenir la valeur voulue. Étant donné que nous désirons mettre un bit à zéro, nous pouvons déjà abandonner l’opérateur | au vu de sa table de vérité. Également, l’opérateur ^ ne convient pas tout à fait puisqu’il inverserait la valeur du bit au lieu de la mettre à zéro. Il nous reste donc l’opérateur &.

Avec cet opérateur, il nous est possible d’utiliser une valeur qui nous donnera le bon résultat. Cette valeur, de même taille que celle de la variable n, est précisément un masque qui va « cacher », « masquer » une partie de la valeur.

#include <stdio.h>
#include <stdlib.h>


int main(void)
{
	unsigned short n;

	if (scanf("%hx", &n) != 1)
	{
		perror("scanf");
		return EXIT_FAILURE;
	}

	printf("%X\n", n & 0x7FFF);
	return 0;
}

8FFF
FFF

7F
7F

Comme vous le voyez, l’opérateur & peut être utilisé pour sélectionner une partie de la valeur de n en mettant à un les bits que nous souhaitons garder (en l’occurrence tous sauf le bit de poids fort) et les autres à zéro.

Mise à un

À l’inverse, les opérateurs de manipulation des bits peuvent être employés pour mettre un ou plusieurs bits à un. Dans ce cas, c’est l’opérateur & qui ne convient pas au vu de sa table de vérité.

Si nous reprenons notre exemple précédent et que nous souhaitons modifier la valeur de la variable n de sorte de mettre à un le bit de signe, nous pouvons procéder comme suit.

#include <stdio.h>
#include <stdlib.h>


int main(void)
{
	unsigned short n;

	if (scanf("%hx", &n) != 1)
	{
		perror("scanf");
		return EXIT_FAILURE;
	}

	printf("%X\n", n | 0x8000);
	return 0;
}

FFF
8FFF

7F
807F

Comme vous le voyez, l’opérateur | peut être utilisé de la même manière dans ce cas ci à l’aide d’un masque dont les bits qui doivent être mis à un sont… à un.

Les champs de bits

Mise en situation

Une autre utilisation des opérateurs de manipulation des bits est le compactage de données entières.

Imaginons que nous souhaitions stocker la date courante sous la forme de trois entiers : l’année, le mois et le jour. La première solution qui vous viendra à l’esprit sera probablement de recourir à une structure, par exemple comme celle ci-dessous, ce qui est un bon réflexe.

struct date {
	unsigned char jour;
	unsigned char mois;
	unsigned short annee;
};

Toutefois, nous gaspillons finalement de la mémoire avec ce système. En effet, techniquement, nous aurions besoin de 12 bits pour stocker l’année (afin d’avoir un peu de marge jusque l’an 4095 ), 4 pour le mois et 5 pour le jour, ce qui nous fait un total de 21 bits contre 32 pour notre structure (à supposer que le type short fasse deux octets et le type char un octet), sans compter les multiplets de bourrage (revoyez le chapitre sur les structures si cela ne vous dit rien ).

Ceci n’est pas gênant dans la plupart des cas, mais cela peut le devenir si la mémoire disponible vient à manquer ou si cette structure est amenée à être créée un grand nombre de fois.

Avec les opérateurs de manipulation des bits, il nous est possible de stocker ces trois champs dans un tableau de trois unsigned char afin d’économiser de la place.

#include <stdio.h>
#include <stdlib.h>


static void modifie_jour(unsigned char *date, unsigned jour)
{
	/* Nous stockons le jour (cinq bits). */
	date[0] |= jour;
}


static void modifie_mois(unsigned char *date, unsigned mois)
{
	/* Nous ajoutons les trois premiers bits du mois après ceux du jour. */
	date[0] |= (mois & 0x07) << 5;
	/* Puis le bit restant dans le second octet. */
	date[1] |= (mois >> 3);
}


static void modifie_annee(unsigned char *date, unsigned annee)
{
	/* Nous ajoutons sept bits de l'année après le dernier bit du mois. */
	date[1] |= (annee & 0x7F) << 1;
	/* Et ensuite les cinq restants. */
	date[2] |= (annee) >> 7;
}


static unsigned calcule_jour(unsigned char *date)
{
	return date[0] & 0x1F;
}


static unsigned calcule_mois(unsigned char *date)
{
	return (date[0] >> 5) | ((date[1] & 0x1) << 3);
}


static unsigned calcule_annee(unsigned char *date)
{
	return (date[1] >> 1) | (date[2] << 7);
}


int
main(void)
{ 
	unsigned char date[3] = { 0 }; /* Initialisation à zéro. */
	unsigned jour, mois, annee;

	printf("Entrez une date au format jj/mm/aaaa : ");

	if (scanf("%u/%u/%u", &jour, &mois, &annee) != 3) {
		perror("fscanf");
		return EXIT_FAILURE;
	}

	modifie_jour(date, jour);
	modifie_mois(date, mois);
	modifie_annee(date, annee);
	printf("Le %u/%u/%u\n", calcule_jour(date), calcule_mois(date), calcule_annee(date));
	return 0;
}

Entrez une date au format jj/mm/aaaa : 31/12/2042
Le 31/12/2042

Cet exemple amène quelques explications.
Une fois les trois valeurs récupérées, il nous faut les compacter dans le tableau d'unsigned char :

1. Pour le jour, c’est assez simple, nous incorporons ses cinq bits à l’aide de l’opérateur | (les trois éléments du tableau étant à zéro au début, cela ne pose pas de problème).
2. Pour le mois, seuls trois bits étant encore disponibles, il va nous falloir répartir ceux-ci sur deux éléments du tableau. Tout d’abord, nous sélectionnons les trois premiers bits à l’aide du masque 0x07, nous les décalons ensuite de cinq bits vers la gauche (afin de ne pas écraser les cinq bits du jour) et, enfin, nous les ajoutons à l’aide de l’opérateur |. Le dernier bit est lui stocké dans le second élément et est sélectionné à l’aide d’un décalage vers la droite afin d’éliminer les trois premiers bits (qui ont déjà été traité).
3. Pour l’année, nous utilisons la même technique que pour le mois : nous sélectionnons les sept premiers bits à l’aide du masque 0x7F, les décalons d’un bit vers la gauche en vue de ne pas écraser le bit du mois et les intégrons avec l’opérateur |. Les cinq bits restants sont ensuite insérés en recourant préalablement à un décalage de sept bit vers la droite.

Présentation

Comme vous le voyez, si nous gagnons effectivement de la place en mémoire, nous y perdons en temps de calcul et, plus important, notre code est nettement plus complexe. C’est la raison pour laquelle cette méthode n’est employée que dans le cas de contraintes particulières.

Bien entendu, nous pourrions recourir à des fonctions ou à des macrofonctions pour simplifier la lecture du code, toutefois, nous ne ferions que reporter la difficulté de compréhension sur ces dernières. Heureusement, en vue de simplifier ce type d’écritures, le langage C met à notre disposition les champs de bits.

Un champ de bits est un membre de type _Bool, int ou unsigned int dont la taille en bits est précisée. Cette taille ne peut être supérieure à la taille en bits du type utilisé. L’exemple ci-dessous défini une structure composée de trois champs de bits, a, b et c de respectivement un, deux et trois bits.

struct champ_de_bits
{
    unsigned a : 1;
    unsigned b : 2;
    unsigned c : 3;
};

Ainsi, notre exemple précédent peut être réécrit comme ceci.

#include <stdio.h>
#include <stdlib.h>


struct date {
	unsigned jour : 5;
	unsigned mois : 4;
	unsigned annee : 12;
};


int
main(void)
{ 
	unsigned jour, mois, annee;

	printf("Entrez une date au format jj/mm/aaaa : ");

	if (scanf("%u/%u/%u", &jour, &mois, &annee) != 3) {
		perror("fscanf");
		return EXIT_FAILURE;
	}

	struct date date = { .jour = jour, .mois = mois, .annee = annee };

	printf("Le %u/%u/%u\n", date.jour, date.mois, date.annee);
	return 0;
}

Si vous avez poussé la curiosité jusqu’à vérifier la taille de cette structure, il y a de fortes chances pour que celle-ci équivaille à celle du type int. En fait, il s’agit de la méthode la plus courante pour conserver les champs de bits : ils sont stockés dans des suites de int. Dès lors, si vous souhaitez économiser de la place, faites en sorte que les données à stocker coïncident le plus possible avec la taille d’un ou plusieurs objets de type int.

Une autre utilisation régulière des opérateurs de manipulation des bits consiste en la gestion des drapeaux. Un drapeau correspond en fait à un bit qui est soit « levé », soit « baissé » dans l’objectif d’indiquer si une situation est vraie ou fausse.

Supposons que nous souhaitions fournir à une fonction un nombre et plusieurs de ses propriétés, par exemple s’il est pair, s’il s’agit d’une puissance de deux et s’il est premier. Nous pourrions bien entendu lui fournir quatre paramètres, mais cela fait finalement beaucoup pour simplement fournir un nombre et, foncièrement, trois bits.

À la place, il nous est possible d’employer un entier dont trois bits seront utilisés pour représenter chaque condition. Par exemple, le premier indiquera si le nombre est pair, le second s’il s’agit d’une puissance de deux et le troisième s’il est premier.

void traitement(int nombre, unsigned char drapeaux)
{
	if (drapeaux & 0x01) /* Si le nombre est pair */
	{
		/* ... */
	}
	if (drapeaux & 0x02) /* Si le nombre est une puissance de deux */
	{
		/*... */
	}
	if (drapeaux & 0x04) /* Si le nombre est premier */
	{
		/*... */
	}
}


int main(void)
{
	int nombre = 2;
	unsigned char drapeaux = 0x01 | 0x02; /* 0000 0011 */

	traitement(nombre, drapeaux);
	nombre = 17;
	drapeaux = 0x04; /* 0000 0100 */
	traitement(nombre, drapeaux);
	return 0;
}

Comme vous le voyez, nous utilisons l’opérateur | pour combiner plusieurs drapeaux et l’opérateur & pour déterminer si un drapeau est levé ou non.

Voilà qui est plus efficace, mais en somme assez peu lisible… En effet, il serait bon de préciser dans notre code à quoi correspond chaque drapeau. Pour ce faire, nous pouvons recourir au préprocesseur afin de clarifier un peu tout cela.

#define PAIR		(1 << 0)
#define PUISSANCE	(1 << 1)
#define PREMIER		(1 << 2)


void traitement(int nombre, unsigned char drapeaux)
{
	if (drapeaux & PAIR) /* Si le nombre est pair */
	{
		/* ... */
	}
	if (drapeaux & PUISSANCE) /* Si le nombre est une puissance de deux */
	{
		/*... */
	}
	if (drapeaux & PREMIER) /* Si le nombre est premier */
	{
		/*... */
	}
}


int main(void)
{
	int nombre = 2;
	unsigned char drapeaux = PAIR | PUISSANCE; /* 0000 0011 */

	traitement(nombre, drapeaux);
	nombre = 17;
	drapeaux = PREMIER; /* 0000 0100 */
	traitement(nombre, drapeaux);
	return 0;
}

Voici qui est mieux.

Pour terminer, remarquez qu’il s’agit d’un bon cas d’utilisation des champs de bits, chacun d’entre eux représentant alors un drapeau.

struct propriete
{
	unsigned pair : 1;
	unsigned puissance : 1;
	unsigned premier : 1;
};


void traitement(int nombre, struct propriete prop)
{
	if (prop.pair) /* Si le nombre est pair */
	{
		/* ... */
	}
	if (prop.puissance) /* Si le nombre est une puissance de deux */
	{
		/*... */
	}
	if (prop.premier) /* Si le nombre est premier */
	{
		/*... */
	}
}


int main(void)
{
	int nombre = 2;
	struct propriete prop = { .pair = 1, .puissance = 1 };

	traitement(nombre, prop);
	return 0;
}

Obtenir la valeur maximale d’un type non signé

Maintenant que nous connaissons la représentation des nombres non signés ainsi que les opérateurs de manipulation des bits, vous devriez pouvoir trouver comment obtenir la plus grande valeur représentable par le type unsigned int.

Indice

Solution

#include <stdio.h>


int main(void)
{
    printf("%u\n", ~0U);
    return 0;
}

Afficher la représentation en base deux d’un entier

Vous le savez, il n’existe pas de format de la fonction printf() qui permet d’afficher la représentation binaire d’un nombre. Pourtant, cela pourrait s’avérer bien pratique dans certains cas, même si la représentation hexadécimale est disponible.

Dans ce second exercice, votre tâche sera de réaliser une fonction capable d’afficher la représentation binaire d’un unsigned int en gros-boutiste.

Indice

Solution

#include <stdio.h>


void affiche_bin(unsigned n)
{
    unsigned mask = ~(~0U >> 1);
    unsigned i = 0;

    while (mask > 0)
    {
    	if (i != 0 && i % 4 == 0)
    		putchar(' ');

    	putchar((n & mask) ? '1' : '0');
    	mask >>= 1;
    	++i;
    }

    putchar('\n');
}


int main(void)
{
    affiche_bin(1);
    affiche_bin(42);
    return 0;
}

0000 0000 0000 0000 0000 0000 0000 0001
0000 0000 0000 0000 0000 0000 0010 1010

Déterminer si un nombre est une puissance de deux

Vous le savez : les puissances de deux ont la particularité de n’avoir qu’un seul bit à un, tous les autres étant à zéro. Toutefois, elles ont une autre propriété : si l’on soustrait un à une puissance de deux $n$, tous les bits précédent celui de la puissance seront mis à un (par exemple 0000 1000 - 1 == 0000 0111). En particulier, on remarque que $n$ et $n-1$ n’ont aucun bit à 1 en commun. Réciproquement, si $n$ n’est pas une puissance de 2, alors le bit à 1 le plus fort est aussi à 1 dans $n-1$. par exemple 0000 1010 - 1 == 0000 1001).

Sachant cela, il nous est possible de créer une fonction très simple déterminant si un nombre est une puissance de 2 ou non.

#include <stdio.h>


int puissance_de_deux(unsigned int n)
{
    return n != 0 && (n & (n - 1)) == 0;
}


int main(void)
{
    if (puissance_de_deux(256))
        printf("256 est une puissance de deux\n");
    else
        printf("256 n'est pas une puissance de deux\n");

    if (puissance_de_deux(48))
        printf("48 est une puissance de deux\n");
    else
        printf("48 n'est pas une puissance de deux\n");

    return 0;
}

256 est une puissance de deux
48 n'est pas une puissance de deux