Битсет

std::bitset<N> — массив из $N$ битов, упакованных в машинные слова. Операции над ним обрабатывают 64 значения за одну инструкцию.

Асимптотику это не меняет: $O(NW)$ остаётся $O(NW)$, просто с делением на 64. Но константа часто решает задачу.

Классический пример: рюкзак

Задача: можно ли набрать вес ровно $W$, выбрав часть предметов? Обычная динамика:

for (int i = 0; i < n; i++)
    for (int v = W; v >= w[i]; v--)
        if (can[v - w[i]]) can[v] = true;

Заметим, что это просто сдвиг всего массива и «или» с ним же:

std::bitset<2000001> can;
can[0] = 1;
for (int i = 0; i < n; i++) can |= can << w[i];

Замер при $N = 2000$ и $W = 2 \cdot 10^6$: булев массив — 1078 мс, битсет — 75 мс, то есть в 14 раз быстрее.

Почему не в 64, как можно было ожидать? Потому что компилятор векторизует и обычный цикл по char, а битсетная версия упирается в память. Шестьдесят четыре — верхняя оценка, четырнадцать — то, что получается на практике. Этого обычно достаточно.

Что важно знать

Размер — константа времени компиляции. std::bitset<n> с переменной $n$ не скомпилируется. Берут максимум из условия.

Память. Битсет на $2 \cdot 10^6$ битов занимает 250 килобайт. Массив bool того же размера — 2 мегабайта.

Полезные методы: count() — число единиц, any(), none(), all(), _Find_first() и _Find_next(i) — обход единиц (последние два нестандартны, но есть в GCC).

Динамический размер — это std::vector<bool>, но он не поддерживает сдвиги и побитовые операции целиком. Если размер известен только во время работы, битсет пишут руками на std::vector<uint64_t>.

Где ещё помогает

задача	что ускоряется
транзитивное замыкание графа	строка матрицы достижимости
наибольшая общая подпоследовательность	слой динамики
решето Эратосфена	массив признаков
проверка достижимости множества сумм	тот же рюкзак

Общий признак: во внутреннем цикле стоит булев массив, и операция над ним — «или», «и» или сдвиг.

Смежное

• Рюкзак — исходная задача;
• Битовые операции.