Nombre de bits de l'écriture binaire⚓︎
Un ordinateur manipule des nombres écrits en binaire : uniquement avec les chiffres « \(0\) » et « \(1\) ». Par exemple le nombre \(26\) s'écrit \(11010\) en binaire.
Chaque « \(0\) » et « \(1\) » d'une écriture binaire est appelé bit. Ainsi, le nombre \(26\) s'écrit en binaire sur \(5\) bits.
Pour savoir combien de bits sont nécessaires pour écrire en binaire un nombre entier strictement positif on compte le nombre de divisions euclidiennes par \(2\) nécessaires pour obtenir un quotient nul.
En partant de \(26\) on a :
- \(26 = 2 \times \mathbf{13} + 0\) ;
- \(13 = 2 \times \mathbf{6} + 1\) ;
- \(6 = 2 \times \mathbf{3} + 0\) ;
- \(3 = 2 \times \mathbf{1} + 1\) ;
- \(1 = 2 \times \mathbf{0} + 1\).
Comme on peut le voir, \(5\) divisions euclidiennes ont été nécessaires pour passer de \(26\) à \(0\) : \(26\) s'écrit donc sur \(5\) bits en binaire.
On rappelle que l'opérateur // permet d'obtenir le quotient de deux nombres : 13 // 2 est évalué à 6.
Écrire la fonction nb_bits qui prend en argument un nombre entier strictement positif et renvoie le nombre de bits nécessaires à son écriture en binaire.
Contrainte
On interdit d'utiliser la fonction bin !
Exemples
>>> nb_bits(1)
1
>>> nb_bits(2)
2
>>> nb_bits(3)
2
>>> nb_bits(4)
3
def nbpy-undbits(n):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert nbpy-undbits(1) == 1bksl-nlassert nbpy-undbits(2) == 2bksl-nlassert nbpy-undbits(3) == 2bksl-nlassert nbpy-undbits(4) == 3bksl-nlbksl-nldef nbpy-undbits(n):bksl-nl compteur = 0bksl-nl while n != 0:bksl-nl n = n // 2bksl-nl compteur = compteur + 1bksl-nl return compteurbksl-nlbksl-nl
A
Il s'agit donc de compter combien de divisions euclidiennes sont nécessaires avant que le quotient ne soit nul.
Traduite en Python cette condition devient : while n != 0:, on continue tant que \(n\) n'est pas nul.
Cet algorithme fonctionne donc pour tous les entiers strictement positifs. La version ci-dessous permet de le rendre fonctionnel pour tous les entiers positifs : \(0\) compris.
def nb_bits(n):
n = n // 2 # une division dès le départ et 0 // 2 vaut 0
compteur = 1 # on a donc 1 bit minimum quoi qu'il arrive
while n != 0:
n = n // 2
compteur = compteur + 1
return compteur
Notons enfin qu'il est aussi possible de résoudre ce problème en utilisant une fonction récursive (qui s'appelle elle-même) :
def nb_bits(n):
if n < 2:
return 1
else:
return 1 + nb_bits(n // 2)
Cette formulation traduit deux choses :
- il n'existe que deux nombres entiers positifs s'écrivant sur un seul bit : \(0\) et \(1\),
- l'écriture binaire de chaque autre nombre entier nécessite 1 bit de plus que celle de son quotient par \(2\).
Z