:: Enseignements :: ESIPE :: E3INFO :: 2008-2009 :: 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

Ecrire les fonctions de base suivantes :
- teste_bit qui permet de savoir la valeur d'un des bits d'un octet (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.
Ecrire les fonctions suivantes :
- compte qui reçoit un octet et compte le nombre de bits égaux à 1.
- est_palindrome qui renvoie 1 ou 0 selon que l'entier passé en paramètre a une représentation binaire palindromique ou non.

Exercice 2 - Ensembles

Un ensemble de nombres entiers peut être répré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 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 (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' élements d'un ensemble.
Ecrire une fonction unio qui fait l'union de deux ensembles.
Ecrire une fonction intersection qui fait l'intersection de deux ensembles.
Ecrire une fonction complementation qui fait la complémentation d'un ensemble.
Ecrire une fonction difference qui fait la différence entre deux ensembles.
Bonus: Ecrire une fonction diff_sym qui calcule la différence symétrique entre deux ensembles.

Exercice 3 - Bonus

Ecrire les fonctions de conversion suivantes :

str2bin qui reçoit une chaîne de caractères de longueur maximum 8. Elle vérifie que cette chaîne n'est composée que de 0 ou de 1, puis renvoie l'entier dont la représentation binaire correspond à la chaîne saisie.
bin2str qui reçoit un octet et renvoie une chaîne de caractères le représentant dans sa forme binaire.
Modifier bin2str pour qu'elle ne retourne que les bits significatifs. Exemple : l'octet 00101001 peut s'écrire 101001.