Подмаски и надмаски

Подмаска маски $m$ — это число, все единичные биты которого есть и у $m$. На языке множеств — подмножество.

Перебираются подмаски одной идиомой, и она достаточно неочевидна, чтобы её запомнить:

for (int s = m; ; s = (s - 1) & m) {
    ...                        // здесь s — очередная подмаска m
    if (s == 0) break;
}

Почему это работает

Пусть $s$ — подмаска $m$. Вычитание единицы «занимает» из младшей единицы $s$: она превращается в ноль, а нули правее — в единицы. Среди этих единиц могут оказаться биты, которых нет в $m$; операция & m их отбрасывает.

Получается следующая по убыванию подмаска. Значит, перебор идёт по всем подмаскам в порядке убывания и заканчивается на нуле.

Проверка на ноль стоит после тела цикла. Если поставить её в условие, пустая подмаска не обработается — и это самая частая ошибка в этой идиоме.

Почему всего $3^n$

Если перебрать подмаски каждой маски, суммарное количество итераций равно $3^n$. Доказательство в одну строку: каждая пара «маска, подмаска» задаётся тем, в каком из трёх состояний находится каждый бит — есть и там и там, есть только в маске, нет нигде.

Проверено перебором: при $n = 3$ пар ровно 27, при $n = 10$ — 59 049, при $n = 15$ — 14 348 907, то есть в точности $3^n$.

При $n = 20$ это $3.5 \cdot 10^9$ — уже много. Замер: перебор подмасок всех масок при $n = 20$ занял 2674 мс, а при $n = 18$ — 265 мс. Если задача требует считать что-то по подмаскам для всех масок, обычно нужен другой способ — суммы по подмаскам за $O(2^n \cdot n)$.

Надмаски

Симметрично: надмаска $m$ — это число, у которого есть все биты $m$ и, возможно, ещё какие-то. Перебираются они через дополнение:

int full = (1 << n) - 1;
for (int s = full ^ m; ; s = (s - 1) & (full ^ m)) {
    int superset = s | m;                        // очередная надмаска
    if (s == 0) break;
}

То есть перебираем подмаски дополнения и добавляем к ним саму $m$.

Смежное

• Маска как множество;
• Суммы по подмаскам — когда $3^n$ слишком много.