On dispose de nb bits (chapitre 1) et l'on propose une seconde…

import math

def nb_bits_formule(n):
    if n == 0:
        return 1
    return math.floor(math.log2(n)) + 1

desaccords = [n for n in range(0, 100000) if nb_bits(n) != nb_bits_formule(n)]
print(len(desaccords))            # 0

Aucun désaccord sur $100000$ valeurs. La conclusion tentante — « les deux fonctions sont correctes » — est fausse.

Le cas $n=2^{60}$.

gros = 2**60
print(nb_bits(gros), nb_bits_formule(gros))          # 61 61
print(nb_bits(gros - 1), nb_bits_formule(gros - 1))  # 60 61

Sur $2^{60}-1$, les deux fonctions divergent : $61$ contre $60$. C'est la version par boucle qui a raison — $2^{60}-1$ s'écrit avec soixante bits à $1$. La formule échoue parce que math.log2 convertit son argument en flottant : $2^{60}-1$ n'est pas représentable exactement en double précision, il est arrondi à $2^{60}$, dont le logarithme vaut exactement $60$ (chapitre 2).

Les deux leçons.

• Un test différentiel qui passe sur $100000$ cas ne prouve rien au-delà de ces cas. Le domaine testé, $0$ à $99999$, tenait tout entier dans la zone où les flottants sont exacts — le défaut était structurellement hors de portée.
• Quand deux implémentations divergent, il faut décider laquelle a raison par le raisonnement, pas par vote. Ici la définition — le nombre de bits de l'écriture binaire — tranche sans ambiguïté en faveur de la boucle.

La règle qui en découle : le domaine de test doit être choisi d'après les frontières du problème (ici : la limite d'exactitude des flottants, $2^{53}$), et non d'après ce qui s'exécute vite.