Enumeração de Submask

Enumerando todas as submasks de uma determinada mask

bitmask = máscara de bits

Dada uma bitmask $m$, você deseja iterar com eficiência sobre todas as suas submasks, isto é, $s$ máscaras nas quais apenas os bits que foram incluídos na máscara $m$ são setados.

Considere a implementação desse algoritmo, com base em truques nas operações de bits:

int s = m;
while (s > 0) {
 ... você pode usar s ...
 s = (s-1) & m;
}

ou, usando uma declaração for mais compacta:

for (int s=m; s; s=(s-1)&m)
 ... você pode usar s ...

Nas duas variantes do código, a submask igual a zero não será processada. Podemos processá-la fora do loop ou usar da seguinte forma:

for (int s=m; ; s=(s-1)&m) {
 ... você pode usar s ...
 if (s==0)  break;
}

Vamos analisar por que o código acima visita todas as submasks de $m$, sem repetições e em ordem decrescente.

Suponha que tenhamos uma bitmask atual $s$, e queremos passar para a próxima bitmask. Subtraindo da máscara $s$ uma unidade, removeremos o bit setado mais à direita e todos os bits à direita dele se tornarão 1. Em seguida, removeremos todos os bits "extras" que não estão incluídos na máscara $m$ e que, portanto, não pode fazer parte da submask. Fazemos essa remoção usando a operação bitwise (s-1) & m. Como resultado, cortamos a máscara(mask) $s-1$ para determinar o maior valor para a próxima iteração, isto é, a próxima submask depois de $s$ em ordem decrescente.

Portanto, esse algoritmo gera todas as submasks dessa máscara em ordem decrescente, realizando apenas duas operações por iteração.

Um caso especial é quando $s = 0$. Depois de executar $s-1$ obtemos uma máscara onde todos os bits estão setados, e após (s-1) & m teremos que $s$ será igual a $m$. Portanto, com a máscara $s = 0$ tenha cuidado - se o loop não terminar em zero, o algoritmo poderá ter um loop infinito.

Iterando sobre todas as masks com suas submasks. Complexidade $O(3^n)$

Em muitos problemas, especialmente aqueles que usam programação dinâmica com bitmask, você precisa iterar sobre todas as bitmasks e, para cada máscara, percorrer todas as suas submasks:

for (int m=0; m<(1<<n); ++m)
    for (int s=m; s; s=(s-1)&m)
 ... s e m ...

Vamos provar que o loop interno executará um total de $O(3^n)$ iterações.

Primeira prova: Considere o $i$-th bit. Existem exatamente três opções para ele:

  1. não está incluído na máscara $m$ (e, portanto, não está incluído na submask $s$),
  2. está incluído em $m$, mas não está incluído em $s$
  3. está incluído em $m$ e $s$.

Como há um total de $n$ bits, haverá $3^n$ combinações diferentes.

Segunda prova: Observe que se a máscara $m$ tiver $k$ bits habilitados, então ela terá $2^k$ submasks. Como temos um total de $\binom{n}{k}$ máscaras com $k$ bits habilitados (veja coeficientes binomiais), então a combinação total de todas as masks será:

$$\sum_{k=0}^n \binom{n}{k} \cdot 2^k$$

Para calcular esse número, observe que a soma acima é igual à expansão de $(1+2)^n$ usando o teorema do binômio. Portanto, temos $3^n$ combinações, como queríamos provar.

Problemas