Reprendre le premier programme du chapitre (celui qui calcule total…

La trace, pour $n=7$. On part de reste = 7 et etapes = 0. Le test $\text{reste}>1$ est évalué avant chaque tour.

La boucle fait donc deux tours et etapes vaut $2$.

Prédiction pour $n=100$. Chaque tour divise par deux : $100\to 50\to 25\to 12\to 6\to 3\to 1$. Six tours.

Vérification.

def etapes_de(n):
    """Nombre de divisions par 2 pour ramener n >= 1 a 1."""
    reste = n
    etapes = 0
    while reste > 1:
        reste = reste // 2
        etapes = etapes + 1
    return etapes

print(etapes_de(7), etapes_de(100))    # 2 6

Le lien avec le chapitre 1. Diviser par deux, c'est effacer le bit de poids faible. Partir d'un nombre de $k$ bits et arriver à $1$ (un seul bit) demande donc $k-1$ effacements :

for n in range(1, 100000):
    assert etapes_de(n) == nb_bits(n) - 1

Les $99999$ cas passent. Contrôle : $7=111_2$ a trois bits, et $3-1=2$ ; $100=1100100_2$ en a sept, et $7-1=6$.

Piège de la trace : placer la mise à jour de etapes avant celle de reste ne change rien ici, mais écrire le test après le corps — c'est-à-dire une boucle « répéter jusqu'à » — donnerait un tour de plus pour $n=1$.