Masques binaires comme petits ensembles
Représenter des sous-ensembles par des entiers
Masques binaires comme petits ensembles est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Un entier comme ensemble
Un seul entier peut représenter tout un ensemble : si le bit i vaut 1, l’élément i en fait partie. Cela permet de regrouper des sous-ensembles dans une valeur minuscule et rapide. 🎒
L’ensemble vide et l’ensemble complet
Le nombre 0 représente l’ensemble vide, tandis qu’une valeur dont les n bits de poids faible valent tous 1 signifie que chaque élément est présent.
empty = 0
full = (1 << 4) - 1 # 0b1111, four elementsAjouter un élément
Pour ajouter l’élément i à l’ensemble, mettez son bit à 1 avec OR. C’est exactement l’opération qui consiste à mettre un bit à 1, interprétée ici comme une union avec un élément.
s = 0
s |= (1 << 2) # add element 2Supprimer un élément
Pour supprimer l’élément i, appliquez AND avec le bit inversé. L’élément quitte l’ensemble et tous les autres restent en place. Il s’agit de la différence entre ensembles, appliquée à un élément.
s &= ~(1 << 2) # remove element 2Tester l’appartenance
Vérifiez si l’élément i appartient à l’ensemble en appliquant AND à son bit. Un résultat différent de zéro signifie qu’il est membre de l’ensemble.
if s & (1 << 2):
print('2 is in the set')Union et intersection
Appliquez OR à deux masques pour obtenir leur union ; appliquez AND pour obtenir leur intersection. Les opérations sur des ensembles entiers deviennent ainsi chacune une seule instruction machine.
union = a | b
inter = a & bLa taille de l’ensemble est le nombre de bits à 1
Le nombre d’éléments d’un masque de bits est simplement son nombre de bits à 1. Utilisez bit_count pour obtenir sa taille instantanément.
size = mask.bit_count()Parcourir tous les sous-ensembles
Pour n éléments, les entiers de 0 à 2 puissance n moins 1 énumèrent tous les sous-ensembles. Une simple boucle sur un intervalle suffit à tous les parcourir.
for mask in range(1 << n):
pass # mask is one subsetParcourir rapidement les sous-masques
Pour parcourir uniquement les sous-ensembles d’un masque donné, utilisez la boucle classique des sous-masques. Elle parcourt chaque sous-ensemble dans l’ordre décroissant.
sub = mask
while sub:
sub = (sub - 1) & maskLa programmation dynamique avec masques de bits
Les masques de bits servent d’état dans de nombreux problèmes de DP, comme celui du voyageur de commerce, où le masque indique les nœuds déjà visités.
Garder n petit
Avec 2 puissance n sous-ensembles, cette astuce ne reste pratique que pour de petites valeurs de n, généralement jusqu’à environ 20. Au-delà, le nombre de possibilités explose. ⚠️
Vérification rapide
Une dernière question sur les ensembles représentés par des masques.
Récapitulatif : les ensembles avec des masques de bits
Vous pouvez stocker un ensemble dans un seul entier, ajouter et supprimer des éléments avec des masques, et parcourir chaque sous-ensemble. Cela permet d’utiliser efficacement la programmation dynamique avec des masques de bits. 🎉
Questions Fréquemment Posées
La leçon « Masques binaires comme petits ensembles » est-elle gratuite ?
Oui — le texte complet de « Masques binaires comme petits ensembles » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Masques binaires comme petits ensembles » ?
Représenter des sous-ensembles par des entiers Tu pratiques Coding Interview Prep 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 Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep 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 4 sur 4.
Combien de temps prend la leçon « Masques binaires comme petits ensembles » ?
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 Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep 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