Сегодня разберём мощный и крайне полезный инструмент оптимизации в алгоритмах - битовые маски и битовые структуры данных.
Идея
Если у нас есть множество чисел, то его можно представить как булев массив, где 1 означает присутствие элемента, а 0 — отсутствие.
Но процессоры работают не с отдельными битами, а целыми машинными словами (обычно 64 бита).
Поэтому можно группировать 64 булевых значений в одно число и делать 64 операций за один такт.
Это называется битовое сжатие, и оно ускоряет алгоритмы примерно в 64 раза.
std::bitset
В C++ уже есть готовая структура - std::bitset, которая работает как большое двоичное число:
bitset<lim> b;
b.set();
b.reset();
b.flip();
b.count();
cout << b[42];
Поддерживает все операции: &, |, ^, ~, <<, >>.
Удобно, просто и очень быстро.
Задача 1: Задача о рюкзаке
Классическое решение работает за
O(n ⋅ m):
bool dp[m] = {};
dp[0] = 1;
for (int i = 0; i < n; i++)
for (int x = m - a[i]; x >= 0; x--)
dp[x + a[i]] |= dp[x];Но с битсетами - всего O(n * m / w):
bitset<m> b;
b[0] = 1;
for (int i = 0; i < n; i++)
b |= b << a[i];
Ускорение - в 30–60 раз. А мы по сути ничего толком и не меняли😎😎😎
Задача 2: Проверка цикла длины 3
Пусть есть ориентированный граф (матрица смежности).
Нужно проверить, существует ли цикл вида a -> b -> c -> a.
С битсетами решение работает за
O(n³ / w):
bitset<maxn> g[maxn];
for (int a = 0; a < n; a++) {
for (int b = 0; b < n; b++) {
if (g[a][b] && (~g[a] & g[b]).any()) {
// найден цикл длины 3
}
}
}
Задача 3: Перемножение матриц
Если считаем не количество путей, а только факт достижения, достаточно побитового умножения:
typedef bitset<maxn> t;
typedef array<t, maxn> matrix;
matrix matmul(matrix a, matrix b) {
matrix c;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (a[i][j])
c[i] |= b[j];
return c;
}
Работает намного быстрее обычного умножения
@postupashki_prog