Процессор устроен так, что работает не с индивидуальными битами, а сразу с блоками по 32 или 64 бита — эта величина называется машинным словом. Как следствие, операции, затрагивающие лишь один бит, на самом деле «стоят» столько же, сколько и операции над целым int-ом или long-ом.
Когда требуется делать какие-то теоретико-множественные операции, их часто можно свести к большому количеству одинаковых операций над элементами булевого массива. Например:
Объединение множеств — побитовое ИЛИ.
Пересечение множеств — побитовое И.
Симметрическая разность — побитовый XOR.
Здесь появляется следующая идея оптимизации: сгруппировать элементы массива в блоки размера 64 и каждый такой блок считать двоичным числом. Тогда можно применить эту битовую операцию сразу к 64 элементам и потратить на это один такт вместо 64-х.
Это всё несложно кодить и вручную, но в STL это уже сделали до нас, написав структуру, ведущую себя как большое двоичное число со всеми стандартными битовыми операциями: bitset.
Работать с ним нужно вот так:
const int lim = 1000;
bitset<lim> b; // создать битсет размера lim (должно быть константой)
b.set(); // заполнить единицами
b.reset(); // заполнить нулями
b.flip(); // заменить единички на нули и наоборот
b.count(); // посчитать число единичек
cout << b; // вывести битовую строкуТакже для битсетов работает вся битовая арифметика: &, |, ^, ~, <<, >> и их варианты с [operator]=.
Примечание. Часто «асимптотику» использующих bitset решений пишут как \(O(f / 64)\). Автору не нравится такая нотация, потому что численную константу формально можно сократить, и, вообще, на разных архитектурах будут разные константы. Вместо этого мы будем везде писать \(O(f / w)\), где \(w\) означает размер машинного слова.
Даны \(n\) предметов с положительными целыми весами \(a_i\) и рюкзак размера \(lim\). Требуется выбрать подмножество предметов с максимальной суммой, не превышающий размер рюкзака.
Обычно его решают так:
bool dp[lim] = {}; // так можно его заполнить нулями
dp[0] = 1;
for (int i = 0; i < n; i++)
for (int x = lim - a[i]; x >= 0; x--)
dp[x + a[i]] |= dp[x];…а с битсетом оно разгоняется так:
bitset<lim> b;
b[0] = 1;
for (int i = 0; i < n; i++)
b |= b << a[i];Пусть нам нужно узнать, есть ли цикл длины 3 в ориентированном графе из \(n\) вершин, заданном своей матрицей смежности. Обернем эту матрицу в битсет, и тогда задача решается за \(O(n^3 / 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()) {
// цикл найден
}
}
}Бенчмарк: на серверах CodeForces этот код при \(n = 5000\) работает за 7 секунд.
Основное применение в олимпиадах: матрица смежности графа, возведенная в степень \(n\), имеет комбинаторный смысл — на пересечении \(a\)-ой строки и \(b\)-того столбца матрицы \(G^n\) будет записано количество способов дойти из вершины \(a\) в вершину \(b\), используя ровно \(n\) переходов.
В некоторых задачах нам не нужно знать именно число способов — нам хватит знания, можно ли вообще через \(n\) ходов там оказаться. Тогда вместо числового умножения нам хватит битового умножения, то есть &:
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;
}Иногда встречаются задачи, требующие решения системы линейных уравнений. Большую часть из них на самом деле можно решить над полем \(\mathbb{Z}_2\) — то есть взять все числа по модулю 2.
Пример: есть \(n\) переключателей лампочек, каждый активированный переключатель меняет состояние (включает или выключает) какого-то подмножества из \(n\) лампочек. Известно текущее состояние всех лампочек, нужно восстановить по нему состояние переключаетелей.
Нас по сути просят решить следующую систему:
\[ \begin{cases} a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n \equiv b_1 \pmod 2\\ a_{21} x_1 + a_{22} x_2 + \ldots + a_{2n} x_n \equiv b_2 \pmod 2\\ \ldots \\ a_{n1} x_1 + a_{n2} x_2 + \ldots + a_{nn} x_n \equiv b_n \pmod 2 \end{cases} \]
Здесь \(x\) — состояния переключателей, \(b\) — состояния лампочек, а матрица \(A\) содержит информацию о том, влияет ли переключатель на лампочку.
В таком случае можно значительно ускорить и упростить обычный метод Гаусса:
t gauss(matrix a) {
for (int i = 0; i < n; i++) {
int nonzero = i;
for (int j = i+1; j < n; j++)
if (a[j][i])
nonzero = j;
swap(a[nonzero], a[i]);
for (int j = 0; j < n; j++)
if (j != i && a[j][i])
a[j] ^= a[i];
}
t x;
for (int i = 0; i < n; i++)
x[i] = a[i][n] ^ a[i][i];
return x;
}Код находит вектор \(x\) из уравнения \(Ax = b\) при условии, что решение существует и единственно. Для простоты кода предполагается, что вектор \(b\) приписан справа к матрице \(A\).
На самом деле, реализация из STL очень медленная. Простой for, в котором and-ят int-ы, будет работать в несколько раз быстрее аналогичной операции битсета. Ускорение получается за счёт векторизации — компилятор перестраивает цикл, используя специальные инструкции, работающие с блоками по 128 / 256 бит, а не 64.
Нужно просто написать цикл с достаточно простым телом, и компилятор сделает всё сам. Трудности возникают только при реализации битовых сдвигов и .count(). Последнюю проще всего реализовать через встроенную в GCC быструю функцию __builtin_popcount, но вообще в STL для этого используется предпосчитанный массив размера 256 с числами от 0 до 8 — количеста единичных бит в записи каждого возможного значения байта.
Автор предполагает, что битсет из STL реализовывали во времена, когда векторизация и отдельная инструкция popcnt ещё не поддерживались процессорами, поэтому всё устроено так, как устроено.