Aller au contenu

Nombre de bits égaux à 1⚓︎

Écriture binaire

L'écriture binaire d'un entier est composée de 0 et de 1.

Par exemple, en binaire, l'entier \(13\) s'écrit 0000_1101.

On peut dire qu'il y a trois 1 dans son écriture binaire.

Objectif et méthode

On souhaite une version récursive d'une fonction telle que nb_bits_1(n) renvoie le nombre de bits égaux à 1 dans l'écriture binaire de l'entier positif n.

Pour cela, on peut remarquer que :

  • si n < 2, alors la réponse est n
  • sinon, la réponse vient de n // 2 et de n % 2

Bits de 13

Si n = 13, alors nb_bits_1(n) est égale à

nb_bits_1(6) + 1

et on a obtenu

  • 6 ← 13 // 2
  • 1 ← 13 % 2

Exercice

Complétez le code ci-dessous, en ajoutant des tests unitaires

###

def nbpy-undbitspy-und1(n):bksl-nl ...bksl-nl bksl-nlbksl-nlassert nbpy-undbitspy-und1(13) == 3bksl-nlbksl-nl

Réponse
🐍 Script Python
def nb_bits_1(n):
    """Renvoie le poids des bits de l'entier positif n"""
    if n < 2:
        return n
    else:
        return nb_bits_1(n // 2) + (n % 2)

Un variante légèrement plus efficace est

🐍 Script Python
def nb_bits_1(n):
    """Renvoie le poids des bits de l'entier positif n"""
    if n < 2:
        return n
    else:
        q = n >> 1
        r = n & 1
        return nb_bits_1(q) + r

En effet

  • n >> 1 décale les bits de n de 1 rang vers la droite, ce qui revient à le diviser par deux. Cette opération est élémentaire pour le processeur, donc très rapide.
  • n & 1 opère un et-logique-bit-à-bit et renvoie très rapidement le bit de poids faible de n.