Bitset

Битовое сжатие

Пусть нам требуется хранить $n$ битов информации. Простым решением данной задачи было бы сохранить $n$ чисел, каждое из которых принимает одно из двух значений --- 0 или 1. Это простое решение. но неэффективное. Заметим, что компьютер умеет за $O(1)$ оперировать 64-битными числами, а это значит, что мы можем использовать одно 64-битное число для хранения сразу 64 различных битов информации. Тогда необходимые затраты памяти уменьшатся в 64 раза. К слову, std::vector<bool> делает такое преобразование по умолчанию. Также есть специальная структура std::bitset, которая не только экономит память, но и умеет делать специальные операции.

Операции над bitset

Числа можно инвертировать, с ними можно делать И, ИЛИ, XOR, побитовые сдвиги и все вытекающие операции. Бисет позволяет делать такие же вещи, но с множеством битов. Кроме того, поскольку для 64-битных чисел такие операции работают за $O(1)$, то на множестве размера $n$ такие операции будут работать за $O(\frac{n}{64})$ Такие трюки позволяют, к примеру, решать задачу о рюкзаке в 64 раза быстрее:

1 bitset<maxw> b;
2 b[0] = 1;
3 for (int weight : goods) {
4     b = b | (b << weight);
5 }

Также битсет позволяет итерироваться по своим единичным битам с помощью функций b._Find_first() и b._Find_next(idx)

[Категория:Конспекты]

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s