Маска как множество

Главное применение битов в олимпиадных задачах: число — это множество. Бит номер $i$ означает «элемент $i$ входит».

При $n \le 20$ всех подмножеств $2^{20} \approx 10^6$ — их можно перебрать. При $n \le 25$ уже $3 \cdot 10^7$, тоже иногда проходит. Дальше — нет.

Словарь

множества	маски
$A \cap B$	a & b
$A \cup B$	a | b
$A \triangle B$	a ^ b
$A \setminus B$	a & ~b
дополнение в $n$ битах	a ^ ((1 << n) - 1)
$x \in A$	(a >> x) & 1
$A \subseteq B$	(a & b) == a
$\|A\|$	__builtin_popcount(a)
пустое множество	0
всё множество	(1 << n) - 1

Обратите внимание на дополнение: ~a перевернёт все биты типа, включая те, которых в задаче нет. Дополнение в пределах $n$ битов — это a ^ ((1 << n) - 1).

Перебор всех подмножеств

for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++)
        if (mask >> i & 1) { ... }               // элемент i входит
}

Стоит это $O(2^n \cdot n)$. Если нужны только входящие элементы, а множество разреженное, быстрее перебирать единицы:

for (int rest = mask; rest; rest &= rest - 1) {
    int i = __builtin_ctz(rest);                 // очередной входящий элемент
    ...
}

Порядок перебора

Полезное свойство: если перебирать маски по возрастанию, то любая подмаска встретится раньше самой маски. Это позволяет считать динамику по подмножествам простым циклом for (int mask = 0; ...), без рекурсии и без топологической сортировки.

Обратное тоже верно: перебор по убыванию гарантирует, что надмаска встретится раньше.

Смежное

• Подмаски — перебор подмножеств одного множества;
• Динамика по подмножествам — главное применение;
• Сколько стоит перебор — когда маски заменяют рекурсию.