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

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

La somme. $a+b\ge 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\ge 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\ge 2^{11}$ compte tout autant : c'est elle qui interdit au produit de descendre à $30$ bits.