Combien de bits pour écrire un entier ?

Avec k bits, on peut écrire 2ᵏ suites différentes de 0 et de 1, donc les 2ᵏ entiers de 0 à 2ᵏ − 1. Par exemple, sur 8 bits (un octet), on écrit les entiers de 0 à 255 : il y en a 256.

Le nombre de bits nécessaires pour écrire un entier naturel n (n ⩾ 1) est donc le plus petit k tel que n < 2ᵏ. Si 2ᵏ⁻¹ ⩽ n < 2ᵏ, l'écriture binaire de n a exactement k bits, et son bit de gauche, de poids 2ᵏ⁻¹, vaut 1.

def nb_bits(n):
    k = 1
    while 2 ** k <= n:
        k = k + 1
    return k

print(nb_bits(13), nb_bits(255), nb_bits(256))
print(bin(13), bin(255), bin(256))

4 8 9
0b1101 0b11111111 0b100000000

13 tient sur 4 bits (8 ⩽ 13 < 16), 255 sur 8 bits, mais 256 = 2⁸ en demande 9 : un 1 suivi de huit 0.

Python le calcule directement avec la méthode bit_length() des entiers :

print((13).bit_length(), (255).bit_length(), (256).bit_length())

4 8 9

Somme. Deux entiers de k bits sont chacun au plus 2ᵏ − 1 ; leur somme est au plus 2ᵏ⁺¹ − 2, strictement inférieure à 2ᵏ⁺¹ : elle tient sur k + 1 bits.

Produit. Leur produit est strictement inférieur à 2ᵏ × 2ᵏ = 2²ᵏ : il tient sur 2k bits. Pour k ≥ 2, le maximum de 2k bits est atteint avec deux nombres dont tous les bits valent 1. Pour k = 1, le produit maximal 1 × 1 tient sur un seul bit :

a = 255
b = 255
print(a + b, (a + b).bit_length())
print(a * b, (a * b).bit_length())

510 9
65025 16

Tailles courantes. Les processeurs et beaucoup de langages manipulent des entiers de 8, 16, 32 ou 64 bits. Le plus grand entier naturel de chaque taille vaut 2ᵏ − 1 :

for k in [8, 16, 32, 64]:
    print(k, 2 ** k - 1)

8 255
16 65535
32 4294967295
64 18446744073709551615

En Python, les entiers n'ont pas de taille fixe : ils grandissent autant que nécessaire.

n = 2 ** 100
print(n)
print(n.bit_length())

1267650600228229401496703205376
101

1. Combien de bits faut-il, au minimum, pour écrire 1 000 en base 2 ? On encadre 1 000 entre deux puissances de 2 consécutives : 2⁹ = 512 ⩽ 1 000 < 2¹⁰ = 1 024. Il faut 10 bits.

print((1000).bit_length())
print(2 ** 9, 2 ** 10)

10
512 1024

2. Quel est le plus grand entier naturel qui s'écrit avec 12 bits ? Tous les bits valent 1 : 1 + 2 + 4 + … + 2¹¹ = 2¹² − 1 = 4 096 − 1 = 4 095.

3. Deux entiers s'écrivent chacun avec au plus 7 bits. Combien de bits faut-il, au maximum, pour leur produit ? Chacun est inférieur à 2⁷, donc le produit est inférieur à 2¹⁴ : 14 bits au plus. Le cas 127 × 127 montre que ce maximum est atteint :

print(127 * 127, (127 * 127).bit_length())

16129 14

Chaque fois que n atteint une puissance de 2, il faut un bit de plus.