Masques binaires : définir, effacer, inverser et vérifier

Un masque de bits est un entier utilisé pour sélectionner, modifier ou vérifier certains bits d’un autre entier. Le masque contient des 1 aux positions qui vous intéressent et des 0 ailleurs. Combinés aux opérateurs bit à bit, les masques permettent d’effectuer des opérations précises sur les bits sans modifier les autres.

Les quatre opérations fondamentales sur les masques sont : positionner (mettre un bit à 1), effacer (mettre un bit à 0), inverser (basculer un bit) et vérifier (déterminer si un bit vaut 1). Chacune utilise un opérateur différent — OR, ET-NON, XOR et AND, respectivement — avec le masque 1 << k.

Pour positionner le bit k (le forcer à 1 quelle que soit sa valeur actuelle), combinez le nombre par OR avec le masque 1 << k. Comme 0 OR 1 = 1 et 1 OR 1 = 1, le bit ciblé devient 1. Tous les autres bits sont combinés par OR avec 0, ce qui les laisse inchangés.

Positionner un bit est une opération idempotente : l’appeler plusieurs fois produit le même effet que de l’appeler une seule fois. Si le bit k vaut déjà 1, le résultat ne change pas. Cette propriété est importante pour la gestion des indicateurs, lorsque vous souhaitez activer une fonctionnalité sans vous soucier de son état actuel.

Pour effacer le bit k (le forcer à 0 quelle que soit sa valeur actuelle), combinez le nombre par AND avec le complément du masque : n & ~(1 << k). Le complément ~(1 << k) contient des 1 dans tous les bits, sauf dans le bit k qui vaut 0. La combinaison avec 0 force le bit ciblé à 0 ; la combinaison avec 1 conserve tous les autres bits.

Comme positionner un bit, l’effacer est une opération idempotente. Effacer un bit qui vaut déjà 0 ne modifie pas le nombre. En Python, ~(1 << k) fonctionne correctement pour toute valeur de k, car Python gère automatiquement l’extension du signe : le complément possède conceptuellement des 1 dans tous les bits de poids supérieur.

Pour inverser le bit k (le faire passer de 0 à 1 ou de 1 à 0), combinez le nombre par XOR avec le masque 1 << k. Combiner un bit avec 1 par XOR l’inverse ; le combiner avec 0 le laisse inchangé. Il s’agit de la propriété fondamentale de XOR appliquée à un seul bit.

L’inversion est la seule des quatre opérations qui n’est pas idempotente : l’appeler deux fois rétablit la valeur initiale. Elle convient donc parfaitement aux fonctionnalités qui alternent entre deux états, comme un interrupteur marche/arrêt ou un indicateur booléen dans une représentation entière compacte.

Pour vérifier si le bit k est positionné, décalez n vers la droite de k positions, puis effectuez un AND avec 1 : (n >> k) & 1. Cela amène le bit k à la position 0 et masque tous les bits de poids supérieur, en laissant 0 (le bit k valait 0) ou 1 (le bit k valait 1). Vous pouvez aussi utiliser bool(n & (1 << k)) pour obtenir un résultat True/False.

Vérifier un bit est une opération non destructive : elle ne modifie pas n. Vous pouvez vérifier plusieurs bits en décalant et en masquant chaque position indépendamment. C’est la base du parcours de la représentation binaire d’un nombre, utilisé pour l’énumération de sous-ensembles et la programmation dynamique avec des états représentés par des masques de bits.

Un entier de n bits peut représenter un sous-ensemble d’un ensemble à n éléments : le bit k vaut 1 si l’élément k appartient au sous-ensemble, et 0 sinon. Cela compresse un sous-ensemble en un seul entier et permet des opérations en O(1) : test d’appartenance (mask & (1 << k)), ajout d’un élément (mask | (1 << k)), suppression d’un élément (mask & ~(1 << k)) et union/intersection d’ensembles (mask1 | mask2 et mask1 & mask2).

Avec n éléments, il existe 2^n sous-ensembles possibles, chacun représenté de manière unique par un entier de n bits compris entre 0 et 2^n - 1. Parcourir tous les entiers de 0 à 2^n - 1 permet donc d’énumérer tous les sous-ensembles.

En programmation dynamique par masques de bits, vous devez souvent parcourir tous les sous-ensembles d’un masque donné. Une astuce courante consiste à commencer par sub = mask, puis à répéter sub = (sub - 1) & mask jusqu’à atteindre 0. Chaque itération produit un sous-masque différent. La complexité totale est O(3^n) pour tous les masques, car chaque élément peut appartenir uniquement au masque externe, uniquement au sous-masque, aux deux, ou à aucun des deux.

Cette technique intervient dans des problèmes tels que « partitionner un tableau en sous-ensembles dont le XOR est égal » ou « trouver le AND maximal d’un sous-ensemble ». La capacité à énumérer efficacement les sous-masques est caractéristique de la programmation dynamique avancée par masques de bits.

La DP par masque de bits résout les problèmes dont the état inclut un sous-ensemble d'éléments visités. L'exemple classique est le problème du voyageur de commerce (TSP) : trouvez la tournée de coût minimal visitant n villes. L'état est dp[mask][city] = coût minimal pour visiter les villes de mask, en terminant dans city. Avec n villes, il y a 2^n × n états, ce qui donne un temps d'exécution de O(n^2 × 2^n), réalisable pour n ≤ 20.

Le masque sert d'ensemble visité compact. Positionner, effacer et vérifier des bits correspond respectivement à visiter, quitter et interroger des villes. C'est le principe central de la DP par masque de bits : utiliser les bits comme ensemble compact pour représenter l'état.

Vous devez parfois extraire non pas un seul bit, mais un champ de plusieurs bits — une plage contiguë de bits. Pour extraire les bits de la position start à start+length-1, créez un masque de length bits à 1 consécutifs : mask = (1 << length) - 1, puis utilisez (n >> start) & mask.

Cette technique est utilisée pour analyser des formats d'entiers compactés, comme les adresses IP, les données de pixels ou les registres matériels, dans lesquels plusieurs petites valeurs sont stockées dans un seul entier. Par exemple, un pixel RGB565 de 16 bits stocke le rouge dans les bits 15-11, le vert dans les bits 10-5 et le bleu dans les bits 4-0.

Les masques de bits apparaissent couramment dans les types de problèmes d'entretien suivants :

• Énumération de sous-ensembles : parcourir les 2^n sous-ensembles à l'aide de masques allant de 0 à 2^n-1
• DP avec compression d'état : encoder un ensemble de nœuds ou d'éléments visités sous forme de masque de bits dans l'état de la DP
• Systèmes d'autorisations : combiner les indicateurs READ/WRITE/EXECUTE avec OR et les vérifier avec AND
• Suivi des cases visitées dans une grille : pour les petites grilles, regrouper les cases visitées dans un seul entier

Un indicateur important que les masques de bits sont utiles : le problème concerne un petit ensemble (n ≤ 20 éléments) et vous devez suivre des combinaisons d'appartenance. Les ensembles plus grands nécessitent d'autres représentations.

Pour parcourir les bits positionnés d'un masque, deux techniques courantes sont utilisées. La méthode du décalage et de la vérification consiste à décaler vers la droite et à vérifier le LSB. La méthode d'isolement du bit positionné de poids faible consiste à isoler le bit positionné de poids faible avec n & -n, à le traiter, puis à l'effacer avec n &= n - 1. La seconde méthode ne parcourt que les bits positionnés et est plus rapide lorsque le masque est peu dense.

En Python, vous pouvez également utiliser bin(n).count('1') ou n.bit_count() (3.10 ou version ultérieure) pour compter les bits à 1. Pour obtenir la position de chaque bit positionné, utilisez n.bit_length() - 1 pour le bit positionné le plus élevé.

Évaluez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation — abordés dans cette leçon.

Dans cette leçon, vous avez appris que the quatre opérations fondamentales sur les masques de bits sont le positionnement (OR), l'effacement (AND-NOT), l'inversion (XOR) et la vérification (décalage-AND), que les entiers peuvent représenter des sous-ensembles, chaque bit indiquant l'appartenance d'un élément, ce qui permet d'énumérer les 2^n sous-ensembles, et que l'extraction de champs de plusieurs bits et la DP par masque de bits utilisent les mêmes principes de masquage pour encoder des états plus complexes. Nous allons ensuite étudier le comptage des bits, les nombres manquants et l'inversion des bits à l'aide des techniques de cette leçon et de la précédente.