TP 1 : Implémentation d'ensemble par représentation binaire (bit field)

On rappelle qu'un unsigned est un entier non-signé (positif). Ils sont stockés sur $4$ octets, soit $4\times 8 = 32$ bits :

In [3]:

unsigned x = 18;
sizeof(x) // 4 octets

unsigned x = 18; sizeof(x) // 4 octets

Out[3]:

4

On rappelle qu'un unsigned est stocké en mémoire en base 2. Ainsi, $10$ est stocké comme $1010_2$.
Dans ce TP, on utilise la représentation binaire des entiers positifs pour coder des ensembles : à chaque entier écrit en base 2 on associe l'ensemble dont les éléments sont les positions des bits égaux à 1.
Par exemple, $1010_2$ a deux bits égaux à $1$, en positions $1$ et $3$ (la position 0 étant celle du chiffre des unités, tout à droite). Donc l'entier $1010_2$, c'est-à-dire $10$, représente l'ensemble $\{1, 3\}$.
Comme un unsigned est stocké sur $32$ bits, cette méthode permet donc de coder n'importe quel sous-ensemble de $\{0, ..., 31\}$ sous forme d'un unsigned.
Pour les questions suivantes, on pourra utiliser &, |, <<, ~ (voir 1er cours de C).

Petites questions¶

Exercice

1. Par quel entier est codé l'ensemble $\{0, 3, 4\}$?
2. Quel est l'ensemble codé par l'entier $26$ ?
3. Écrire une fonction singleton telle que singleton(i) renvoie l'entier représentant $\{i\}$, c'est-à-dire $2^i$ ($= 1\underbrace{0...0}_i {}_2$).

Solution

In [15]:

// 1. $\{0, 3, 4\}$ est codé par $\boxed{11001_2 = 2^4 + 2^3 + 2^0 = 16 + 8 + 1 = 25}$  

// 2. $26 = 11010_2$ donc représente l'ensemble $\boxed{\{1, 3, 4\}}$  

// 3.
unsigned singleton(unsigned i) {
    return 1<<i; // 2**i
}
// on aurait pu calculer 2**i par exponentiation rapide par exemple, mais 1 << i est plus rapide (O(1))

// 1. $\{0, 3, 4\}$ est codé par $\boxed{11001_2 = 2^4 + 2^3 + 2^0 = 16 + 8 + 1 = 25}$ // 2. $26 = 11010_2$ donc représente l'ensemble $\boxed{\{1, 3, 4\}}$ // 3. unsigned singleton(unsigned i) { return 1<

Union, intersection, appartenance¶

Exercice

1. Écrire une fonction union2 telle que, si s1 et s2 sont deux entiers représentants des ensembles, union2(s1, s2) renvoie un entier représentant leur union.
2. Faire de même pour l'intersection de deux ensembles.
3. Écrire une fonction has telle que has(s, e) détermine si l'entier e appartient à l'ensemble représenté par l'entier s.

Solution

In [16]:

// 1. l'union de deux ensembles correspond au "ou"
unsigned union2(unsigned s1, unsigned s2) {
    return s1 | s2;
}

// 2. l'intersection correspond au "et"
unsigned inter(unsigned s1, unsigned s2) {
    return s1 & s2;
}

// 3. on teste si l'intersection de s et du singleton {e} est non-vide 
// (c'est-à-dire différent de 0, car 0 représente l'ensemble vide)
bool has(unsigned s, unsigned e) {
    return inter(s, singleton(e)) != 0;
}
// on aurait aussi pu regarder si inter(s, singleton(e)) == singleton(e)

// 1. l'union de deux ensembles correspond au "ou" unsigned union2(unsigned s1, unsigned s2) { return s1 | s2; } // 2. l'intersection correspond au "et" unsigned inter(unsigned s1, unsigned s2) { return s1 & s2; } // 3. on teste si l'intersection de s et du singleton {e} est non-vide // (c'est-à-dire différent de 0, car 0 représente l'ensemble vide) bool has(unsigned s, unsigned e) { return inter(s, singleton(e)) != 0; } // on aurait aussi pu regarder si inter(s, singleton(e)) == singleton(e)

Algorithme de Kernighan¶

Exercice

1. Si $n = 1011100_2$, que vaut $n$ & $(n - 1)$ ? Quel est le lien entre l'écriture de $n$ et celle de $n$ & $(n - 1)$ ?
2. En s'inspirant de la question précédente, écrire une fonction card telle que card(n) renvoie le nombre de 1 dans l'écriture binaire de n. Cette fonction sera linéaire en le nombre de 1 dans l'écriture binaire de n. (Remarque : card renvoie donc le cardinal (taille) de l'ensemble codé par l'entier en argument)
3. Un des intérêts de cette représentation binaire des ensembles est qu'il est facile d'énumérer tous les sous-ensembles de $\{0, ..., p\}$, en faisant une boucle for sur les entiers de $0$ à $2^p - 1$. Calculer ainsi la somme des cardinaux des sous-ensembles de $\{0, ..., p\}$, pour différentes valeurs de $p$.
   Bonus : trouver une formule mathématique pour cette somme.

Solution

In [7]:

// 1. n vaut 1011000 en base 2. On a remplacé le 1 le plus à droite par 0 (ceci est valable dans le cas général).

// 2. On peut appliquer l'opération n & (n - 1) jusqu'à obtenir 0. 
// Comme on enlève un 1 à chaque fois, le nombre d'étapes nécessaires est le nombre de 1 dans n en base 2.
unsigned card(unsigned n) {
    unsigned res = 0;
    while(n != 0) {
        n = n & (n - 1); // ou n &= n - 1;
        res++;
    }
    return res;
}

// 
unsigned n = 0;
for(int s = 0; s < 1<<8; s++) { // pour tout s < 2**32
    n += card(s);
}
n

// 1. n vaut 1011000 en base 2. On a remplacé le 1 le plus à droite par 0 (ceci est valable dans le cas général). // 2. On peut appliquer l'opération n & (n - 1) jusqu'à obtenir 0. // Comme on enlève un 1 à chaque fois, le nombre d'étapes nécessaires est le nombre de 1 dans n en base 2. unsigned card(unsigned n) { unsigned res = 0; while(n != 0) { n = n & (n - 1); // ou n &= n - 1; res++; } return res; } // unsigned n = 0; for(int s = 0; s < 1<<8; s++) { // pour tout s < 2**32 n += card(s); } n

Out[7]:

1024

Bit de poids faible¶

Exercice

1. Si x est un entier positif, que permet d'obtenir l'instruction x & (~x + 1) ? On pourra essayer sur des exemples.
2. En déduire une fonction min permettant de renvoyer le minimum d'un ensemble codé par un entier.
3. Montrer qu'on pourrait utiliser x & -x au lieu de x & (~x + 1) (c'est-à-dire que les deux instructions donnent la même chose), en sachant que -x est stocké par complément à 2 (voir cours à ce sujet).

Solution

1. Si $x = 110100_2$ alors ~$x = 001011_2$ donc ~$x + 1$ = $001100_2$ et $x$ & (~$x + 1$) = $\boxed{000100_2}$. On remarque qu'on obtient le bit de poids faible (le 1 le plus à droite dans la représentation binaire). En terme d'ensemble, on obtient donc un singleton contenant le minimum.

Solution

In [14]:

// 2. 
unsigned min(unsigned s) {
    return s & (~s + 1);
}

// 2. unsigned min(unsigned s) { return s & (~s + 1); }