Un entier s'écrit sur 12 bits, un entier sur 20 bits

Représenter les entiers · Combien de bits faut-il ? · niveau 3 (difficile)

Énoncé

Un entier $a$ s'écrit sur 12 bits, un entier $b$ sur 20 bits. Donner un encadrement du nombre de bits de $a + b$ , puis de $a \times b$ . Construire un exemple atteignant chacune des bornes du produit.

Corrigé

Traduire l'hypothèse. « $a$ s'écrit sur 12 bits » signifie $2^{11} \leq a < 2^{12}$ , et « $b$ sur 20 bits » signifie $2^{19} \leq b < 2^{20}$ .

La somme. $a + b \geq 2^{11} + 2^{19} > 2^{19}$ , donc $a + b$ demande au moins $20$ bits. Et $a + b < 2^{12} + 2^{20} < 2^{21}$ , donc au plus $21$ bits. Les deux valeurs sont atteintes : $2^{11} + 2^{19} = 526336$ s'écrit sur $20$ bits, tandis que $(2^{12} - 1) + (2^{20} - 1) = 1052670$ dépasse $2^{20} = 1048576$ et en demande $21$ .

Le produit. $a \times b \geq 2^{11} \times 2^{19} = 2^{30}$ , donc au moins $31$ bits ; et $a \times b < 2^{12} \times 2^{20} = 2^{32}$ , donc au plus $32$ bits. C'est bien le $p + q - 1$ ou $p + q$ de la proposition du cours.

Les exemples.

Borne basse : $a = 2^{11} = 2048$ et $b = 2^{19} = 524288$ donnent $ab = 2^{30}$ , qui s'écrit sur $31$ bits.
Borne haute : $a = 2^{12} - 1 = 4095$ et $b = 2^{20} - 1 = 1048575$ donnent $ab = 4293914625 > 2^{31}$ , qui s'écrit sur $32$ bits.

Contrôle machine : nb_bits(2**11 * 2**19) vaut $31$ et nb_bits(4095 * 1048575) vaut $32$ .

Piège : croire que « 12 bits » veut dire $a < 2^{12}$ seulement. La borne inférieure $a \geq 2^{11}$ compte tout autant : c'est elle qui interdit au produit de descendre à $30$ bits.