TP 3 : Représentation binaire

Dans ce TP, on ne manipule que des entiers positifs. On pourra donc utiliser le type unsigned au lieu de int.

Test du zéro¶

Exercice

Écrire une fonction is_zero telle que, si t est un tableau de n entiers, is_zero(t, n) renvoie un booléen indiquant si t contient que des 0 (c'est-à-dire s'il correspond à l'écriture de $0$ dans une certaine base).

Solution

In [4]:

bool is_zero(int* t, int n) {
    for(int i = 0; i < n; i++)
        if(t[i] != 0)
            return false;
    return true;
}

int t1[3] = {0, 1, 2};
printf("%d ", is_zero(t1, 3));
int t2[3] = {0, 0, 0};
printf("%d", is_zero(t2, 3));
bool is_zero(int* t, int n) {
    for(int i = 0; i < n; i++)
        if(t[i] != 0)
            return false;
    return true;
}

int t1[3] = {0, 1, 2};
printf("%d ", is_zero(t1, 3));
int t2[3] = {0, 0, 0};
printf("%d", is_zero(t2, 3));

0 1

Conversion d'une base b vers la base 10¶

Exercice

Écrire une fonction b_to_10 telle que, si b est une base de numérotation (un entier positif) et t est un tableau de taille size, b_to_10(t, size, b) renvoie l'entier dont l'écriture en base b correspond aux éléments de t. Le prototype de b_to_10 est donc :

unsigned b_to_10(unsigned* t, unsigned size, unsigned b);

Par exemple, comme $10100_2 = 2^4 + 2^2 = 16 + 4 = 20$, l'appel suivant de b_to_10 doit renvoyer $20$ :

unsigned t[] = {0, 0, 1, 0, 1};
b_to_10(t, 5, 2); // renvoie 20

Remarque : On stocke les chiffres à l'envers dans le tableau, pour que les calculs soient (un peu) plus simples.
Remarque : On peut se passer des calculs de puissance.

Solution

In [7]:

// on stocke les puissances de b pour éviter de faire n calculs de puissance
unsigned b_to_10(unsigned* t, unsigned size, unsigned b) {
    unsigned somme = 0;
    unsigned puissance = 1; // stocke les puissances de b
    for(int i = 0; i < size; i++) {
        somme += t[i]*puissance; // puissance vaut b**i
        puissance *= b; // multiplie puissance par b
    }
    return somme;
}

unsigned t[] = {0, 0, 1, 0, 1};
b_to_10(t, 5, 2);
// on stocke les puissances de b pour éviter de faire n calculs de puissance
unsigned b_to_10(unsigned* t, unsigned size, unsigned b) {
    unsigned somme = 0;
    unsigned puissance = 1; // stocke les puissances de b
    for(int i = 0; i < size; i++) {
        somme += t[i]*puissance; // puissance vaut b**i
        puissance *= b; // multiplie puissance par b
    }
    return somme;
}

unsigned t[] = {0, 0, 1, 0, 1};
b_to_10(t, 5, 2);

Conversion de la base 10 vers une base b¶

On veut convertir un entier $n$, exprimé en base 10, vers une autre base $b$ et stocker les chiffres dans un tableau. Comme la taille des tableaux doit être déterminée à sa création, il faut connaître le nombre de chiffres de $n$ en base $b$.

Exercice

Montrer que le nombre de chiffres de $n$ en base $b$ est $\lfloor \log_b(n) \rfloor + 1$ (où $\lfloor ... \rfloor$ est la partie entière).
En déduire une fonction size_b telle que size_b(n, b) renvoie le nombre de chiffres de n en base b. On utilisera la fonction log (qui est le logarithme népérien).

Solution

Soit $p$ le nombre de chiffres de $n$ en base $b$. Le plus petit nombre à $p$ chiffres est $b^{p-1}$ ($ = 1\underbrace{0...0}_{p-1} {}_2$) et le plus grand nombre à $p$ chiffres est $b^p - 1$ ($ = \underbrace{1...1}_{p} {}_2$). Donc : $$b^{p - 1} \leq n < b^p$$ En passant au $\log_b$ (qui est une fonction strictement croissante donc préserve les inégalités) : $$(p - 1) \leq \log_b(n) < p$$ $$\Longrightarrow p \leq \log_b(n) + 1 < p + 1$$ $$\Longrightarrow \boxed{p = \lfloor \log_b(n) \rfloor + 1}$$

Solution

In [9]:

// 2.
unsigned size_b(unsigned n, unsigned b) {
    return log(n)/log(b) + 1;
}

size_b(20, 2)  // 20 = 10100_2 possède 5 chiffres en base 2
// 2.
unsigned size_b(unsigned n, unsigned b) {
    return log(n)/log(b) + 1;
}

size_b(20, 2)  // 20 = 10100_2 possède 5 chiffres en base 2

Out[9]:

Exercice

Écrire une fonction 10_to_b telle que, si b est une base et n un entier, 10_to_b(n, b) renvoie un tableau dont les éléments sont les chiffres (à l'envers) de n en base b.

unsigned* convert_10_to_b(unsigned n, unsigned b);

On rappelle que la méthode consiste à effectuer des divisions euclidiennes successives par b et lire les restes obtenus, à l'envers.

D'après les divisions de l'exemple ci-dessus : $98 = 1100010_2$.

Solution

In [26]:

unsigned* convert_10_to_b(unsigned n, unsigned b) {
    unsigned size = log(n)/log(b) + 1;
    unsigned* tab = (unsigned*)malloc(size*sizeof(unsigned));
    for(int i = 0; i < size; i++) {
        tab[i] = n % b;
        n /= b;
    }
    return tab;
}
unsigned* convert_10_to_b(unsigned n, unsigned b) {
    unsigned size = log(n)/log(b) + 1;
    unsigned* tab = (unsigned*)malloc(size*sizeof(unsigned));
    for(int i = 0; i < size; i++) {
        tab[i] = n % b;
        n /= b;
    }
    return tab;
}

Solution

In [27]:

unsigned* tab = convert_10_to_b(98, 2); // 98 = 1100010_2
for(int i = 0; i < 7; i++) {
    printf("%u", tab[i]);
}
unsigned* tab = convert_10_to_b(98, 2); // 98 = 1100010_2
for(int i = 0; i < 7; i++) {
    printf("%u", tab[i]);
}