Traduire la fonction nb bits du chapitre 1 en pseudo-code, puis dire…

Le pseudo-code. Le pseudo-code n'est pas un langage : c'est du français structuré, écrit pour être lu par un humain et traduisible dans n'importe quel langage.

fonction NB_BITS(n) :
    si n = 0 alors
        renvoyer 1
    k <- 0
    tant que n > 0 faire
        n <- n div 2
        k <- k + 1
    renvoyer k

Les constructions employées. Quatre des six : l'affectation ($k\leftarrow 0$, $n\leftarrow n\mathrm{div}2$), la séquence (l'ordre des lignes), la conditionnelle (le cas $n=0$), la boucle non bornée (le « tant que »). Ni boucle bornée, ni appel de fonction — sinon la fonction elle-même.

Pourquoi la boucle est non bornée ici, alors qu'on sait compter ses tours. Question légitime : elle fait exactement $\text{nb\_bits}(n)$ tours. Mais ce nombre n'est pas connu avant d'entrer dans la boucle — c'est même précisément ce qu'on cherche à calculer. Le critère n'est pas « peut-on le savoir après coup », c'est « le sait-on avant ».

La terminaison. Le variant est $n$ lui-même : entier positif, il est divisé par $2$ à chaque tour, donc décroît strictement tant qu'il est $>0$. La boucle s'arrête.

Contrôle : le pseudo-code se retraduit ligne à ligne en la fonction Python du chapitre 1 — c'est le signe qu'il est au bon niveau de détail. Un pseudo-code qui ne se traduit pas est trop vague ; un pseudo-code qui ressemble à du Python n'apporte rien.