10.3 Представление множеств¶

Каждое подмножество множества {0, 1, 2, ..., n-1} можно представить в виде n-битного целого числа, где единичные биты показывают, какие элементы входят в подмножество. Это очень удобный способ хранения множеств: на каждый элемент нужен всего один бит памяти, а операции над множествами превращаются в обычные побитовые операции.

Например, тип int в C++ обычно занимает 32 бита. Значит, одно значение типа int может хранить любое подмножество множества {0, 1, 2, ..., 31}.

Рассмотрим множество {1, 3, 4, 8}. Его битовая запись выглядит так:

00000000000000000000000100011010

Это число равно:

Реализация множества¶

Следующий код объявляет переменную x, которая хранит подмножество множества {0, 1, 2, ..., 31}. Затем в это множество добавляются элементы 1, 3, 4 и 8, после чего выводится его размер.

int x = 0;

x |= (1 << 1);
x |= (1 << 3);
x |= (1 << 4);
x |= (1 << 8);

cout << __builtin_popcount(x) << "\n"; // 4

Функция __builtin_popcount(x) возвращает количество единичных битов в числе x, то есть фактически размер множества.

Теперь выведем все элементы, которые входят в множество:

for (int i = 0; i < 32; i++) {
    if (x & (1 << i)) cout << i << " ";
}

// вывод: 1 3 4 8

Здесь мы по очереди проверяем каждый бит. Если i-й бит установлен, значит элемент i принадлежит множеству.

Операции над множествами¶

Побитовые операции позволяют очень быстро выполнять стандартные операции теории множеств.

Разберём пример. Пусть

• x = {1, 3, 4, 8}
• y = {3, 6, 8, 9}

Тогда объединение этих множеств равно {1, 3, 4, 6, 8, 9}:

int x = (1 << 1) | (1 << 3) | (1 << 4) | (1 << 8);
int y = (1 << 3) | (1 << 6) | (1 << 8) | (1 << 9);

int z = x | y;

cout << __builtin_popcount(z) << "\n"; // 6

Для наглядности можно представить это так:

flowchart TD
    X["x = {1, 3, 4, 8}"]
    Y["y = {3, 6, 8, 9}"]
    Z["z = x ∪ y = {1, 3, 4, 6, 8, 9}"]
    X --> Z
    Y --> Z

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

Очень важное применение битовых масок — перебор всех подмножеств.

Следующий код проходит по всем подмножествам множества {0, 1, ..., n-1}:

for (int b = 0; b < (1 << n); b++) {
    // обработать подмножество b
}

Каждое число b от 0 до 2^n - 1 кодирует одно подмножество.

Если нужно перебрать только подмножества размера k, можно использовать __builtin_popcount:

for (int b = 0; b < (1 << n); b++) {
    if (__builtin_popcount(b) == k) {
        // обработать подмножество b размера k
    }
}

Также часто нужно перебрать все подмножества уже заданного множества x. Это можно сделать так:

int b = 0;
do {
    // обработать подмножество b
} while ((b = (b - x) & x));

Этот приём компактен и очень популярен в задачах на битовые маски.

Что важно запомнить¶

Представление множеств через биты особенно полезно, когда:

• число элементов невелико;
• нужно быстро выполнять операции пересечения, объединения и разности;
• требуется перебирать все подмножества;
• состояние в задаче удобно кодировать набором выбранных элементов.

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