Перебор всех подмасок данной маски

Перебор подмасок фиксированной маски

Дана битовая маска $m$ . Требуется эффективно перебрать все её подмаски, т.е. такие маски $s$ , в которых могут быть включены только те биты, которые были включены в маске $m$ .

Сразу рассмотрим реализацию этого алгоритма, основанную на трюках с битовыми операциями:

int s = m;
while (s > 0) {
	... можно использовать s ...
	s = (s-1) & m;
}

или, используя более компактный оператор $for$ :

for (int s=m; s; s=(s-1)&m)
	... можно использовать s ...

Единственное исключение для обоих вариантов кода — подмаска, равная нулю, обработана не будет. Её обработку придётся выносить из цикла, или использовать менее изящную конструкцию, например:

for (int s=m; ; s=(s-1)&m) {
	... можно использовать s ...
	if (s==0)  break;
}

Разберём, почему приведённый выше код действительно находит все подмаски данной маски, причём без повторений, за O (их количества), и в порядке убывания.

Пусть у нас есть текущая подмаска $s$ , и мы хотим перейти к следующей подмаске. Отнимем от маски $s$ единицу, тем самым мы снимем самый правый единичный бит, а все биты правее него поставятся в $1$ . Затем удалим все "лишние" единичные биты, которые не входят в маску $m$ и потому не могут входить в подмаску. Удаление осуществляется битовой операцией $\& m$ . В результате мы "обрежем" маску $s-1$ до того наибольшего значения, которое она может принять, т.е. до следующей подмаски после $s$ в порядке убывания.

Таким образом, этот алгоритм генерирует все подмаски данной маски в порядке строгого убывания, затрачивая на каждый переход по две элементарные операции.

Особо рассмотрим момент, когда $s = 0$ . После выполнения $s-1$ мы получим маску, в которой все биты включены (битовое представление числа $-1$ ), и после удаления лишних битов операцией $(s-1) \& m$ получится не что иное, как маска $m$ . Поэтому с маской $s = 0$ следует быть осторожным — если вовремя не остановиться на нулевой маске, то алгоритм может войти в бесконечный цикл.

Перебор всех масок с их подмасками. Оценка $3^n$

Во многих задачах, особенно на динамическое программирование по маскам, требуется перебирать все маски, и для каждой маски - все подмаски:

for (int m=0; m<(1<<n); ++m)
	for (int s=m; s; s=(s-1)&m)
		... использование s и m ...

Докажем, что внутренний цикл суммарно выполнит $O (3^n)$ итераций.

Доказательство: 1 способ. Рассмотрим $i$ -ый бит. Для него, вообще говоря, есть ровно три варианта: он не входит в маску $m$ (и потому в подмаску $s$ ); он входит в $m$ , но не входит в $s$ ; он входит в $m$ и в $s$ . Всего битов $n$ , поэтому всего различных комбинаций будет $3^n$ , что и требовалось доказать.

Доказательство: 2 способ. Заметим, что если маска $m$ имеет $k$ включённых битов, то она будет иметь $2^k$ подмасок. Поскольку масок длины $n$ с $k$ включёнными битами есть $C_n^k$ (см. "биномиальные коэффициенты"), то всего комбинаций будет:

$\sum_{k=0}^n C_n^k 2^k.$

Посчитаем эту сумму. Для этого заметим, что она есть не что иное, как разложение в бином Ньютона выражения $(1+2)^n$ , т.е. $3^n$ , что и требовалось доказать.