Module: Itérer sur tous les sous-modèles d'un masque donné

Il arrive qu'il soit nécessaire d'énumérer toutes les séquences de bits d'une certaine longueur. Ou en d'autres termes, itérer sur toutes les options possibles, où pour chaque objet l'un des deux états possibles est sélectionné.

Dans de telles situations, il est possible de mettre en œuvre une énumération à l'aide de masques de bits. L'avantage de cette approche est qu'un tel code fonctionne de manière non récursive et opère sur des nombres au lieu de collections ou similaires, ce qui améliore considérablement les performances.

Le code général utilisant des masques de bits est donné ci-dessous : international ; // nombre d'oobjects (longueur de la séquence de bits) for (int mask = 0; mask < (1 << n); mask++) { // boucle sur tous les nombres de 0 à 2^n - 1, où chaque nombre correspond à un masque de bits // le masque de nombre actuel est un masque de bits, où le ième bit spécifie l'état du ième objet for (int i = 0; i < n; i++) { // itération sur n bits pour comprendre l'état de chaque objet if ((1 << i) & mask) { // vérifie si le i-ème bit est égal à un // traite l'option selon laquelle le i-ème objet a l'état '1' } else { // cas où le i-ième bit est zéro // traite l'option que le i-ème objet de l'état '0' } } }
Ce code s'exécute en O(2^n * f(n)), où f(n) est le temps qu'il vous faut pour traiter un itérable particulier.