22 General utilities library [utilities]
reference ( ) ; constexpr reference & operator = ( bool x ) noexcept ; // for b[i] = x; constexpr reference & operator = ( const reference & ) noexcept ; // for b[i] = b[j]; constexpr bool operator
( ) const noexcept ; // flips the bit constexpr operator bool ( ) const noexcept ; // for x = b[i]; constexpr reference & flip ( ) noexcept ; // for b[i].flip(); > ; // [bitset. cons], constructors constexpr bitset ( ) noexcept ; constexpr bitset ( unsigned long long val ) noexcept ; template < class charT, class traits, class Allocator > constexpr explicit bitset ( const basic_string < charT, traits, Allocator > & str, typename basic_string < charT, traits, Allocator > :: size_type pos = 0 , typename basic_string < charT, traits, Allocator > :: size_type n = basic_string < charT, traits, Allocator > :: npos, charT zero = charT ( ‘0’ ) , charT one = charT ( ‘1’ ) ) ; template < class charT > constexpr explicit bitset ( const charT * str, typename basic_string < charT > :: size_type n = basic_string < charT > :: npos, charT zero = charT ( ‘0’ ) , charT one = charT ( ‘1’ ) ) ; // [bitset. members], bitset operations constexpr bitset & operator & = ( const bitset & rhs ) noexcept ; constexpr bitset & operator | = ( const bitset & rhs ) noexcept ; constexpr bitset & operator ^ = ( const bitset & rhs ) noexcept ; constexpr bitset & operator < < = ( size_t pos ) noexcept ; constexpr bitset & operator > > = ( size_t pos ) noexcept ; constexpr bitset operator < < ( size_t pos ) const noexcept ; constexpr bitset operator > > ( size_t pos ) const noexcept ; constexpr bitset & set ( ) noexcept ; constexpr bitset & set ( size_t pos, bool val = true ) ; constexpr bitset & reset ( ) noexcept ; constexpr bitset & reset ( size_t pos ) ; constexpr bitset operator
( ) const noexcept ; constexpr bitset & flip ( ) noexcept ; constexpr bitset & flip ( size_t pos ) ; // element access constexpr bool operator [ ] ( size_t pos ) const ; constexpr reference operator [ ] ( size_t pos ) ; constexpr unsigned long to_ulong ( ) const ; constexpr unsigned long long to_ullong ( ) const ; template < class charT = char , class traits = char_traits < charT > , class Allocator = allocator < charT > > constexpr basic_string < charT, traits, Allocator > to_string ( charT zero = charT ( ‘0’ ) , charT one = charT ( ‘1’ ) ) const ; // observers constexpr size_t count ( ) const noexcept ; constexpr size_t size ( ) const noexcept ; constexpr bool operator = = ( const bitset & rhs ) const noexcept ; constexpr bool test ( size_t pos ) const ; constexpr bool all ( ) const noexcept ; constexpr bool any ( ) const noexcept ; constexpr bool none ( ) const noexcept ; > ; // [bitset. hash], hash support template < class T > struct hash; template < size_t N > struct hash < bitset < N > > ; >
Битсет и битовое сжатие
Нумерованные множества можно представлять в виде булевых массивов: если элемент $x$ присутствует в множестве, то $x$-тый элемент массива будет равен единице, и нулю в противном случае.
Разные теоретико-множественные операции часто можно свести к поэлементным операциям булевыми массивами. Например:
- Объединение множеств — побитовое ИЛИ.
- Пересечение множеств — побитовое И.
- Симметрическая разность — побитовый XOR (исключающее ИЛИ).
Процессор устроен так, что работает не с отдельными битами, а сразу с блоками по, например, 32 или 64 бита — эта величина называется машинным словом — и поэтому операции, затрагивающие лишь один бит, на самом деле «стоят» столько же, сколько и операции над всеми битами int или long .
Здесь появляется следующая идея оптимизации: сгруппировать элементы булева массива в блоки размера 64 и каждый такой блок представить 64-битным двоичным числом. Тогда можно применять соответствующие побитовые операцию сразу к 64 элементам и тратить на это один процессорный такт вместо 64-х.
#std::bitset
Это всё несложно кодить и вручную, но в STL всё уже сделано до нас. bitset — структура, ведущая себя как большое двоичное число со всеми стандартными битовыми операциями:
Также для битсетов работает вся битовая арифметика: &, |, ^,
, <<, >> и их варианты с [operator]= .
Примечание. Часто «асимптотику» использующих битовое сжатие алгоритмов пишут как $O(f / 64)$. Автору не нравится такая нотация, потому что численную константу формально можно сократить, и, вообще, на разных архитектурах и у разных реализаций будут разные константы. Вместо этого будем везде писать $O(f / w)$, где $w$ означает размер машинного слова.
#Задача о рюкзаке
Даны $n$ предметов с положительными целыми весами $a_i$ и рюкзак размера $m$. Требуется выбрать подмножество предметов с максимальной суммой, не превышающий размер рюкзака.
Обычное решение за $O(n \cdot m)$:
…битовым сжатием разгоняется до $O(n \cdot m / w)$ так:
#Цикл длины 3
Нужно узнать, есть ли цикл длины 3 в ориентированном графе из $n$ вершин, заданном своей матрицей смежности.
Обернем матрицу смежности в массив битсетов, и тогда задача решается за $O(n^3 / w)$:
Бенчмарк: на серверах CodeForces этот код при $n = 5000$ работает за 7 секунд.
#Перемножение матриц
В задачах на подсчет числа путей часто используется факт, что матрица смежности графа, возведенная в степень $n$, имеет комбинаторный смысл: на пересечении $a$-ой строки и $b$-того столбца матрицы $G^n$ будет записано количество способов дойти из вершины $a$ в вершину $b$, используя ровно $n$ переходов.
В некоторых задачах нам не нужно знать именно число способов дойти из $a$ в $b$ — нам достаточно знания, можно ли вообще там оказаться за $n$ ходов. Тогда вместо числового умножения нам хватит битового умножения, то есть & :
#Метод Гаусса
Иногда встречаются задачи, требующие решения системы линейных уравнений. Большую часть из них на самом деле можно решить над полем $\mathbb
Есть $n$ переключателей лампочек. Каждый активированный переключатель меняет состояние (включает или выключает) какого-то подмножества из $n$ лампочек. Известно текущее состояние всех лампочек, требуется восстановить по нему состояние переключателей.
Нас по сути просят решить следующую систему:
$$ \begin
Здесь $x$ — состояния переключателей, $b$ — состояния лампочек, а бит $a_
В таком случае можно значительно ускорить и упростить обычный метод Гаусса:
Код находит вектор $x$ из уравнения $Ax = b$ при условии, что решение существует и единственно. Для простоты кода предполагается, что вектор $b$ приписан справа к матрице $A$.
#Детали реализации
На самом деле, на высоких уровнях оптимизации ( g++ -O3 -march=native . ) компилятор в конечном итоге будет использовать группы не по 64, а по 256 бит, используя SIMD-инструкции. Однако, для реализации .count() самое быстрое, что можно придумать — вызывать инструкцию popcnt по очереди от каждого 64-битного числа (в GCC она доступна как встроенный интринзик __builtin_popcount ), поэтому этот метод работает в несколько раз медленнее побитовых операций.
Операции с битсетами довольно просто реализовывать и с нуля: нужен только цикл с достаточно простым телом, и компилятор сделает всё сам, никакой тёмной магии при этом не требуется.
O.1 – Битовые флаги и битовые манипуляции с помощью std::bitset
В современных компьютерных архитектурах наименьшей адресуемой единицей памяти является байт. Поскольку все объекты должны иметь уникальные адреса памяти, это означает, что объекты должны быть размером не менее одного байта. Для большинства типов переменных это нормально. Однако для логических значений это немного расточительно. Логические типы имеют только два состояния: true (1) или false (0). Для этого набора состояний требуется только один бит. Однако если переменная должна быть как минимум байтом, а байт равен 8 битам, это означает, что логическое значение использует 1 бит, а остальные 7 остаются неиспользованными.
В большинстве случаев это нормально – обычно мы не настолько ограничены в памяти, чтобы заботиться о 7 потерянных битах (мы лучше займемся оптимизацией для удобства понимания и поддержки). Однако в некоторых случаях с интенсивным хранением для повышения эффективности хранения может быть полезно «упаковать» 8 отдельных логических значений в один байт.
Для этого требуется, чтобы мы могли манипулировать объектами на битовом уровне. К счастью, C++ дает нам для этого инструменты. Изменение отдельных битов внутри объекта называется битовой манипуляцией.
Битовые манипуляции также полезны в алгоритмах шифрования и сжатия.
Примечание автора
Вся эта глава не обязательна для чтения. Не стесняйтесь её пропустить и вернуться позже.
Битовые флаги
До этого момента мы использовали переменные для хранения одиночных значений:
Однако вместо того, чтобы рассматривать объекты как содержащие одно значение, мы можем вместо этого рассматривать их как набор отдельных битов. Когда отдельные биты объекта используются как логические значения, биты называются битовыми флагами.
В качестве отступления.
В вычислениях флаг – это значение, которое действует как сигнал для некоторой функции или процесса. Для аналогии, в реальной жизни флаг почтового ящика используется, чтобы сигнализировать о том, что внутри почтового ящика что-то есть, и поэтому почтовый ящик не нужно открывать для проверки.
Чтобы определить набор битовых флагов, мы обычно используем целочисленный тип без знака соответствующего размера (8 бит, 16 бит, 32 бита и т.д., в зависимости от того, сколько у нас флагов) или std::bitset .
Лучшая практика
Битовые манипуляции – это один из немногих случаев, когда вы однозначно должны использовать беззнаковые целочисленные типы (или std::bitset ).
В этом уроке мы покажем, как легко манипулировать битами с помощью std::bitset . В следующем наборе уроков мы узнаем, как сделать это более сложным, но универсальным способом.
Нумерация битов и позиции битов
Учитывая последовательность битов, мы обычно нумеруем их справа налево, начиная с 0 (а не с 1). Каждое число обозначает позицию бита.
В данной последовательности битов 0000 0101, биты, которые находятся в позициях 0 и 2, имеют значение 1, а остальные биты имеют значение 0.
Управление битами через std::bitset
В уроке «4.13 – Литералы» мы уже показали, как использовать std::bitset для печати значений в двоичном формате. Однако это не единственная полезная вещь, которую может делать std::bitset .
std::bitset предоставляет 4 ключевые функции, которые полезны для работы с битами:
- test() позволяет нам узнать, равен ли бит 0 или 1;
- set() позволяет нам установить бит в 1 (она ничего не сделает, если бит уже равен 1);
- reset() позволяет нам сбросить бит в 0 (она ничего не даст, если бит уже равен 0);
- flip() позволяет нам инвертировать значение бита с 0 на 1, или наоборот.
Каждая из этих функций в качестве своего единственного аргумента принимает позицию бита, с которым мы хотим работать.
Эта программа напечатает:
Что, если мы хотим получить или установить сразу несколько битов
std::bitset не упрощает эту задачу. Для этого или, если вместо std::bitset мы хотим использовать битовые флаги в значениях целочисленных типов без знака, нам нужно обратиться к более традиционным методам. Мы рассмотрим их в следующих нескольких уроках.
What is Bitmasking?
At the Smallest scale in computers, data is stored as bits. A bit stores either 0 or 1. A binary number is a number expressed in the base-2 system. Each digit can be either 0 or 1.
You can check the binary representation of a number in python:
So, 21 is represented as ‘10101’ in Binary.
Bitmask
Now finally, what’s a mask? We can construct a binary number such that a particular digit is set to 1 and other digits are set to 0. This creates a “mask” that when we AND it to another binary it "turns off" (set to 0) all digits except the 1 digit in the mask.
Common Bitmask Operations
- (number | (1 << i))
this operation sets the i th bit in the number to 1. - (number &
more bitmask operations —
Bitset in C++
In C++, A Bitset is a data structure that is used to represent a set of bits. It is similar to an array, but instead of storing integers or characters, it stores binary values. Bitsets are commonly used in computer graphics, network programming, and cryptography.
In C++, a Bitset is implemented using the std::bitset class. This class provides a set of operations for manipulating and querying the bits in the bitset. For example:
Here’s an example of how to use bitset for masking:
Conclusion
One of the biggest benefits of using Bitmask and Bitset in C++ is their efficiency. Bitwise operations are much faster than arithmetic operations and can be used to manipulate multiple bits at once. This makes them ideal for working with large datasets in Competitive Programming competitions.