Colle 3 - Représentation binaire

Les fonctions sont à écrire en OCaml. Chaque question de programmation est suivie de tests qui doivent passer sans erreur.

L'objet de cette colle est la manipulation de représentations binaires d'entiers naturels. Si \(n \in \N^*\), on appelle représentation binaire de \(n\) l'expression notée \(\left(b_{N-1} b_{N-2} \ldots b_{1} b_{0}\right)_{2}\) où les entiers \(b_{i}\) prennent leurs valeurs dans l'ensemble \(\{0,1\}\), excepté \(b_{N-1}\) qui vaut \(1\). Cette expression se déduit de la décomposition binaire de l'entier \(n\) sous la forme :

\[ n=\sum_{i=0}^{N-1} b_{i} \times 2^{i} \qquad (E) \]

Les entiers \(b_{i}\) sont appelés bits de \(n\). \(b_{N-1}\) est appelé bit de poids fort ; \(b_{0}\) est appelé bit de poids faible. \(N\) est le nombre de bits de la représentation binaire de \(n\).

On admettra que \(0\) se représente sur \(0\) bit par convention.

Question 1. Si \(n\) est un entier naturel, combien de bits sa représentation binaire comporte-t-elle ?

Corrigé

Si \(n > 0\), on a \(2^{N-1} \le n < 2^N\) d'après \((E)\) car \(b_{N-1} = 1\). Ainsi \(N - 1 \le \log_2 n < N\), c'est-à-dire \(N = \lfloor \log_2 n \rfloor + 1\). Par exemple, \(16 = (10000)_2\) s'écrit sur \(5\) bits.

Question 2. Écrire une fonction nb_bits : int -> int qui calcule ce nombre à l'aide des seules opérations arithmétiques \(+,-, *, /\).

Corrigé 
let rec nb_bits n =
    if n = 0
    then 0
    else 1 + nb_bits (n / 2)

Tests :

assert(nb_bits 5 = 3);
assert(nb_bits 0 = 0);
assert(nb_bits 1 = 1);
assert(nb_bits 16 = 5)

Question 3. Écrire une fonction nat2bin : int -> int array qui renvoie le plus petit tableau associé à la représentation binaire d'un entier naturel, son bit de poids fort étant le dernier élément du tableau, son bit de poids faible le premier élément du tableau. Ainsi, le nombre précédent s'écrit [|b0;b1;...;bN-1|].

Corrigé 
let nat2bin n =
    let nb = nb_bits n in
    let a = Array.make nb 0 in
    let x = ref n in
    for i = 0 to nb-1 do
        a.(i) <- !x mod 2;
        x := !x / 2
    done;
    a

Tests :

assert(nat2bin 5 = [|1;0;1|]);
assert(nat2bin 0 = [||]);
assert(nat2bin 1 = [|1|]);
assert(nat2bin 6 = [|0;1;1|])

Question 4. La relation \((E)\) peut être mise sous la forme équivalente suivante.

\[ n=b_{0}+2 \times\left(b_{1}+2 \times\left(b_{2}+\cdots+2 \times\left(b_{N-2}+2 \times b_{N-1}\right) \ldots\right)\right) \]

En quoi cette forme est-elle plus avantageuse, en termes de nombre d'opérations élémentaires, que la forme \((E)\) ? Justifier votre réponse.

Corrigé

Avec la forme \((E)\), si on calcule chaque puissance \(2^i\) indépendamment avec \(i-1\) multiplications, on effectue \(\sum_{i=1}^{N-1} i = O(N^2)\) multiplications. Même en calculant les puissances successivement (\(2^{i+1} = 2 \times 2^i\)), il faut deux multiplications et une addition par bit.

La seconde forme, dite de Horner, se calcule de l'intérieur vers l'extérieur avec exactement une multiplication et une addition par bit, soit \(N-1\) multiplications et \(N-1\) additions, sans calcul de puissance.

Question 5. En déduire une fonction bin2nat : int array -> int qui renvoie l'entier dont le tableau argument est la représentation binaire.

Corrigé 
let bin2nat a =
    let nb = Array.length a in
    let n = ref 0 in
    for i = 0 to nb-1 do
        n := 2 * !n + a.(nb-i-1)
    done;
    !n

Tests :

assert(bin2nat [|1;0;1|] = 5);
assert(bin2nat [||] = 0);
assert(bin2nat [|1|] = 1);
assert(bin2nat [|0;1;1|] = 6)

On définit les opérateurs binaires \(\wedge\) (et) et \(\oplus\) (ou exclusif) sur 1 bit par les règles suivantes :

\(a\) \(b\) \(a \wedge b\) \(a \oplus b\)
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

Question 6. Écrire deux fonctions bit_and et bit_xor de même signature int -> int -> int associées à ces opérateurs.

Corrigé 
let bit_and x y =
    if x = 1 && y = 1 then 1 else 0

let bit_xor x y =
    if x <> y then 1 else 0

Tests :

assert(bit_and 0 0 = 0);
assert(bit_and 1 0 = 0);
assert(bit_and 0 1 = 0);
assert(bit_and 1 1 = 1);
assert(bit_xor 0 0 = 0);
assert(bit_xor 1 0 = 1);
assert(bit_xor 0 1 = 1);
assert(bit_xor 1 1 = 0)

Si \(x\) et \(y\) sont deux entiers naturels non nuls, on note \(\left(x_{n_{x}-1} \ldots x_{1} x_{0}\right)_{2}\) et \(\left(y_{n_{y}-1} \ldots y_{1} y_{0}\right)_{2}\) leurs représentations binaires sur respectivement \(n_{x}\) et \(n_{y}\) bits. On pose \(n_{\max }=\max \left(n_{x}, n_{y}\right)\) et on complète la plus courte des deux représentations par des bits nuls : \(x_i = 0\) pour \(i \ge n_x\) et \(y_i = 0\) pour \(i \ge n_y\).

On définit deux fonctions \(f_{\wedge}, f_{\oplus}\) telles que \(f_{\wedge}(x, y)\) et \(f_{\oplus}(x, y)\) sont respectivement les représentations binaires de deux entiers \(p\) et \(r\), avec pour tout entier \(i \in \range{0}{n_{\max}-1}\) :

\[ p_{i}=x_{i} \wedge y_{i} \qquad r_{i}=x_{i} \oplus y_{i} \]

Ainsi, pour \(i \ge \min(n_x, n_y)\), on a \(p_i = 0\) et \(r_i = z_i\) où \(z_i\) désigne le bit d'indice \(i\) du plus long des deux tableaux.

Question 7. Écrire une fonction : bin_func : (int -> int -> int) -> int array -> int array -> int array qui reçoit une fonction func comme bit_and ou bit_xor, deux tableaux associés aux représentations binaires de deux entiers et qui renvoie le tableau de taille \(n_{\max}\) obtenu en appliquant func à chaque bit des deux tableaux arguments. Ce tableau peut se terminer par des bits nuls : ce n'est alors pas le plus petit tableau représentant le résultat.

Corrigé 
let bin_func func ax ay : int array =
    let nx = Array.length ax in
    let ny = Array.length ay in
    (* bit d'indice i de a, de longueur n, complété par des 0 *)
    let bit a n i = if i < n then a.(i) else 0 in
    Array.init (max nx ny) (fun i -> func (bit ax nx i) (bit ay ny i))

Tests :

assert(bin_func bit_and [|1;0;1|] [|0;1|] = [|0;0;0|]);
assert(bin_func bit_xor [|1;0;1|] [|0;1|] = [|1;1;1|])

Question 8. En déduire deux fonctions bin_and et bin_xor de signature int -> int -> int qui reçoivent deux entiers naturels et qui renvoient l'entier naturel associé à l'appel de bin_func avec les fonctions bit_and et bit_xor et des fonctions qui vous semblent utiles.

Corrigé 
let bin_and x y =
    bin2nat (bin_func bit_and (nat2bin x) (nat2bin y))

let bin_xor x y =
    bin2nat (bin_func bit_xor (nat2bin x) (nat2bin y))

Tests :

assert(bin_and 5 7 = 5);
assert(bin_xor 5 7 = 2);
assert(bin_and 1664 1337 = 1024);
assert(bin_xor 1664 1337 = 953);
assert(bin_and 6 203 = 2);
assert(bin_xor 6 203 = 205);
assert(bin_and 16 15 = 0)

Remarque

On retrouve ainsi les opérateurs land et lxor d'OCaml : par exemple 16 land 15 vaut 0.

Question 9. x et y étant deux variables de type int, quel effet le script suivant a-t-il sur le contenu de ces deux variables ? Justifier votre réponse.

let x = bin_xor x y
let y = bin_xor x y
let x = bin_xor x y
Corrigé

Il échange les valeurs de x et y. Notons \(a\) et \(b\) les valeurs initiales. L'opération \(\oplus\) est, bit à bit, associative, commutative, d'élément neutre \(0\) et vérifie \(u \oplus u = 0\). Après la première ligne, x vaut \(a \oplus b\). Après la deuxième, y vaut \((a \oplus b) \oplus b = a \oplus (b \oplus b) = a\). Après la troisième, x vaut \((a \oplus b) \oplus a = b\).

En toute rigueur, en OCaml, chaque let définit une nouvelle variable qui masque la précédente : ce sont les noms x et y qui désignent, à la fin, les valeurs échangées.

On définit les deux fonctions g : int -> int et h : int -> int suivantes.

let g x0 =
    let c = ref 0 in
    let x = ref x0 in
    while !x > 0 do
        c := !c + bin_and !x 1;
        x := !x / 2
    done;
    !c

let h x0 =
    let c = ref 0 in
    let x = ref x0 in
    while !x > 0 do
        x := bin_and !x (!x-1);
        c := !c + 1
    done;
    !c

Question 10. Justifier que la boucle présente dans chaque fonction n'est pas une boucle infinie.

Corrigé

Dans les deux cas, !x est un entier naturel et c'est un variant : il décroît strictement à chaque tour de boucle.

  • Dans g, si \(x > 0\), alors \(\lfloor x/2 \rfloor < x\).
  • Dans h, si \(x > 0\), notons \(i\) l'indice du bit à \(1\) de poids le plus faible de \(x\) : \(x = (\ldots 1 0 \ldots 0)_2\) avec \(i\) zéros à droite. Alors \(x - 1 = (\ldots 0 1 \ldots 1)_2\) : les bits d'indice \(> i\) sont inchangés, le bit \(i\) passe à \(0\) et les bits d'indice \(< i\) passent à \(1\). Ainsi \(x \wedge (x-1)\) est \(x\) dont on a mis le bit \(i\) à \(0\), donc \(x \wedge (x-1) = x - 2^i < x\).

Une suite strictement décroissante d'entiers naturels étant finie, les deux boucles terminent.

Question 11. Que calculent ces fonctions ? Justifier votre réponse.

Corrigé

Les deux fonctions calculent le nombre de bits à \(1\) dans la représentation binaire de x0.

  • Dans g, bin_and !x 1 vaut le bit de poids faible de !x, et diviser par \(2\) décale la représentation binaire d'un cran vers la droite. On ajoute donc successivement à c chacun des bits de x0.
  • Dans h, d'après la question précédente, chaque tour de boucle met à \(0\) exactement un bit à \(1\) de !x. La boucle s'arrête quand !x vaut \(0\), donc après autant de tours que x0 a de bits à \(1\), et c compte ces tours.

Question 12. L'une d'entre elles est-elle temporellement plus efficace que l'autre si on admet que toutes les opérations élémentaires (y compris bin_and) ont un même coût temporel ? Si oui, laquelle et pourquoi ?

Corrigé

Chaque tour de boucle effectue un nombre constant d'opérations dans les deux cas. g effectue \(N\) tours, où \(N = \lfloor \log_2 x_0 \rfloor + 1\) est le nombre de bits de x0, alors que h effectue autant de tours que de bits à \(1\), ce qui est inférieur ou égal à \(N\). h est donc plus efficace, nettement quand x0 comporte peu de bits à \(1\) : par exemple, pour \(x_0 = 2^{20}\), g fait \(21\) tours et h un seul. Les deux sont équivalentes quand tous les bits valent \(1\).