:: Enseignements :: ESIPE :: E3INFO :: 2012-2013 :: Programmation C ::

Manipulation de bits et ensembles

Dans ce TD, nous implémenterons les opérations sur la manipulation de bits, puis nous verrons leur application pour les opérations sur les ensembles.

Exercice 1 - Manipulation de bits

Écrire les fonctions de base suivantes :
- teste_bit qui permet de savoir la valeur d'un des bits d'un octet (unsigned char); elle renvoie 0 ou 1.
- allume_bit qui positionne un bit donné d'un octet à 1.
- eteint_bit qui positionne un bit donné d'un octet à 0.

Exercice 2 - Ensembles

Un ensemble de nombres entiers peut être représenté comme un tableau de bits. Chaque indice i du tableau correspond au nombre i ; la valeur dans le tableau à cet indice est 1 si le nombre appartient à l'ensemble, elle est 0 sinon.

En pratique, en C, on doit utiliser un tableau de unsigned char (ou octet). Chaque octet contient 8 bits, donc potentiellement 8 nombres.

Par exemple, si l'on suppose qu'un ensemble est représenté par un tableau de 2 octets, il pourra contenir les nombres compris entre 0 et 15. Pour l'ensemble {3,5,10}: le premier octet contiendra les nombres 3 et 5 et aura pour valeur 40 (2³+2⁵=00101000); le deuxième octet contiendra le nombre 10 et aura pour valeur 4 (00000100). Attention, les bits de poids faibles sont à droite.

Définir une constante MAX qui sera la taille unique des tableaux représentant les ensembles.
Ecrire les fonctions init_ensemble qui initialise un ensemble (l'ensemble est vide).
Ecrire une fonction ajoute qui ajoute un nombre dans un ensemble.
Ecrire une fonction affiche_ensemble qui affiche un ensemble.
Ecrire une fonction appartient qui indique si un nombre entier entier appartient à un ensemble.
Ecrire une fonction cardinal qui renvoie le nombre d'éléments d'un ensemble.
Ecrire une fonction unio qui fait l'union de deux ensembles (non, ce n'est pas une faute, il ne manque pas de n. Réfléchissez et vous comprendrez)
Ecrire une fonction intersection qui fait l'intersection de deux ensembles.
Ecrire une fonction complementation qui fait la complémentation d'un ensemble.