Module: Iterar sobre todos os subpadrões de uma determinada máscara

Acontece que é necessário enumerar todas as sequências de bits de um determinado comprimento. Ou seja, iterar sobre todas as opções possíveis, onde para cada objeto um dos dois estados possíveis é selecionado.

Em tais situações, é possível implementar a enumeração usando máscaras de bits. A vantagem dessa abordagem é que esse código funciona de forma não recursiva e opera em números em vez de coleções ou similares, o que melhora muito o desempenho.

O código geral usando bitmasks é dado abaixo: int; // número de oobjects (comprimento da sequência de bits) for (int mask = 0; mask < (1 << n); mask++) { // percorre todos os números de 0 a 2^n - 1, onde cada número corresponde a um bitmask // a máscara de número atual é uma bitmask, onde o i-ésimo bit especifica o estado do i-ésimo objeto for (int i = 0; i < n; i++) { // iterar sobre n bits para entender o estado de cada objeto if ((1 << i) & mask) { // verifica se o i-ésimo bit é igual a um // processa a opção que o i-ésimo objeto tem o estado '1' } else { // caso quando o i-ésimo bit é zero // processa a opção que o i-ésimo objeto do estado '0' } } }
Este código é executado em O(2^n * f(n)), onde f(n) é o tempo que você leva para processar um determinado iterável.