Le poids de Hamming d'un entier est son nombre de bits à

def poids_lent(n):
    k = 0
    while n > 0:
        k = k + n % 2
        n = n // 2
    return k

def poids_kernighan(n):
    """Nombre de bits à 1 : n & (n-1) efface le 1 le plus à droite."""
    k = 0
    while n > 0:
        n = n & (n - 1)
        k = k + 1
    return k

for n in range(0, 5000):
    assert poids_lent(n) == poids_kernighan(n)

Pourquoi n & (n - 1) efface le dernier $1$. Si $n$ se termine par $1\underset{j}{\underbrace{0\dots 0}}$, alors $n-1$ se termine par $0\underset{j}{\underbrace{1\dots 1}}$ et coïncide avec $n$ sur tous les bits de poids supérieur. Le & conserve donc les bits de poids fort et annule le bloc final : exactement un $1$ a disparu.

Le coût. La première version fait un tour par bit, soit $\lfloor {\log }_{2}n\rfloor +1$ tours. La seconde fait un tour par bit à $1$. Sur $n=2^{40}$, qui n'a qu'un seul bit à $1$ : $41$ tours contre $1$.

Contrôle : poids_kernighan(214) rend $5$, ce qui correspond à $\text{11010110}$ — cinq uns.

Prolongement : le coût de la seconde version dépend de la valeur de l'entrée, pas seulement de sa taille. Dans le pire cas (tous les bits à $1$) elle ne gagne rien ; c'est la distinction entre coût au pire et coût en moyenne, que le programme de terminale formalise.