Compter les bits et le bit à 1 de plus faible poids
Utiliser popcount et l’astuce n & -n
Compter les bits et le bit à 1 de plus faible poids est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Compter les bits à 1
De nombreux problèmes demandent combien de bits valent 1 dans un nombre, ce qu’on appelle le nombre de bits à 1. Cela intervient dans la taille des sous-ensembles, les vérifications de parité et le calcul des scores. 🔢
Le comptage intégré de Python
La méthode entière la plus rapide pour compter les bits à 1 est bit_count(). Pas de boucle ni de complication : vous obtenez directement le nombre de bits à 1.
print((13).bit_count()) # 0b1101 has 3 onesCompter avec la représentation binaire et le comptage
Si vous oubliez bit_count, convertissez le nombre en texte binaire et comptez les bits à 1. C’est plus lent, mais clair et facile à retenir.
print(bin(13).count('1')) # 3Le bit à 1 de poids faible
Le bit à 1 de poids faible est le 1 le plus à droite d’un nombre. L’isoler est une opération essentielle pour les arbres de Fenwick et les astuces sur les sous-ensembles que vous verrez plus tard.
L’isoler avec n et -n
L’astuce célèbre n & -n ne conserve que le bit à 1 de poids faible. Les nombres négatifs en complément à deux rendent cela presque magique.
n = 12 # 0b1100
print(n & -n) # 4 = 0b100Pourquoi n et -n fonctionnent
La négation inverse tous les bits et ajoute 1, de sorte que tout ce qui se trouve sous le premier 1 s’inverse. L’opération AND ne laisse alors que ce seul bit.
Supprimer le bit à 1 de poids faible
Soustraire 1 effectue des emprunts à travers les zéros finaux, si bien que n & (n - 1) efface le bit à 1 de poids faible. Répétez l’opération pour retirer les bits à 1 un par un.
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000Le comptage de Brian Kernighan
Répétez la boucle tant que le nombre n’est pas nul, en effaçant le bit de poids faible à chaque fois. La boucle s’exécute une fois par bit à 1 : elle est donc rapide pour compter les bits à 1 dans un nombre peu dense.
c = 0
while n:
n &= n - 1
c += 1Vérifier s’il s’agit d’une puissance de deux
Une puissance de deux positive possède exactement un bit à 1, donc n & (n - 1) vaut 0. Une seule opération AND suffit pour le savoir instantanément.
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0La parité grâce au nombre de bits
La parité d’un nombre est simplement le nombre de bits à 1 modulo 2. Elle permet de répondre en une seule étape aux questions où il faut savoir si le nombre de bits à 1 est impair ou pair.
parity = (13).bit_count() & 1 # 1Choisir l’outil le plus rapide
Pour une vitesse maximale, utilisez bit_count ; pour parcourir les bits à 1, utilisez la boucle n & (n-1). Choisir le bon outil permet de respecter les limites de temps strictes. ⚡
Vérification rapide
Testez l’astuce du bit à 1 de poids faible.
Récapitulatif : compter les bits
Vous pouvez compter les bits à 1 avec bit_count, isoler le bit de poids faible avec n & -n et le supprimer avec n & (n-1). De puissantes opérations en une seule ligne. 🎉
Questions Fréquemment Posées
La leçon « Compter les bits et le bit à 1 de plus faible poids » est-elle gratuite ?
Oui — le texte complet de « Compter les bits et le bit à 1 de plus faible poids » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Compter les bits et le bit à 1 de plus faible poids » ?
Utiliser popcount et l’astuce n & -n Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Compter les bits et le bit à 1 de plus faible poids » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- AND, OR, XOR et décalages
- Définir, effacer et inverser un bit
- Compter les bits et le bit à 1 de plus faible poids
- Masques binaires comme petits ensembles