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 estn
- sinon, la réponse vient de
n // 2
et den % 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 den
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 den
.