Общие сведения
Контейнер bitset
представляет собой псевдо-контейнер предназначенный для хранения и работы с фиксированной последовательностью битов. Иными словами, элементами массива могут быть только нули и единицы, а сам массив является статическим. bitset
может хранить двоичное представление целого числа, размер которого превосходит размер любого фундаментального типа, т. е. больше 64 bit. Этот контейнер можно также использовать для битовых масок, что весьма полезно при решении целого ряда сложных задач, в которых есть необходимость сохранять флаги. Получить bitset
можно путем импорта символов строки или значением одного из целочисленных типов. Предусмотрен также и экспорт в строку, либо в тип unsigned long long
.
Создание объекта bitset. Инициализация
Для начала работы с контейнером необходимо включить заголовок следующей директивой:
#include <bitset>
Конструктор
Чтобы создать объект типа bitset
необходимо определить битсет, указав количество битов, которые будут содержаться в массиве:
bitset<N> name_obj;
Выражение N
должно быть константным выражением целого типа. Объект name_obj
будет инициализирован значениями по умолчанию, то есть нулевыми битами. Деструктор для данного контейнера не определен, поэтому удалить его можно, если использовать указатель на тип битсета.
Инициализация строкой
Чтобы инициализировать объект битсет строкой, нужно передать строку конструктору, как аргумент. Дополнительными (необязательными) аргументами могут быть позиции начала и конца чтения.
Программа 24.1
#include <iostream> #include <bitset> #include <string> using namespace std; int main() { cout << "Введите битовую последовательность:" << endl; string Sbit; cin >> Sbit; bitset<20> mybs(Sbit); cout << mybs << endl; for (size_t i = 0; i < mybs.size(); i++) cout << mybs[i]; cout << endl; return 0; }
Введите битовую последовательность: 11110000111110010101 11110000111110010101 10101001111100001111
Обратите внимание на то, что элементы в битсете хранятся в обратном порядке, что продемонстрировано в программе 21.1. Младшие биты (биты находящиеся в конце строки) будут хранится в начале, т. е. элемент Sbit[Sbit.size() - 1]
будет помещен в mybs[0]
.
Собственно, символы ‘0’ и ‘1’ в строке Sbit
выступают как символы для маски по умолчанию. Но в качестве таких символов маски могут быть выбраны и другие символы. Формат передачи аргументов в конструктор в общем виде будет таков:
bitset<N> name_obj(myStr, pos1, pos2, zero, one)
где pos1
– нальная позиция, pos2
– конечная позиция (читение до конца строки можно осуществить используя константу string::npos
), zero
– символ-маска нуля, one
– символ-маска единицы.
Программа 24.2
#include <iostream> #include <bitset> #include <string> using namespace std; int main() { cout << "Введите маску битовой последовательности" "\nс помощью символов a (маска 0) и b (маска 1):" << endl; string Sbit; cin >> Sbit; bitset<20> mybs(Sbit, 0, 8, 'a', 'b'); cout << mybs; return 0; }
Введите маску битовой последовательности с помощью символов a (маска 0) и b (маска 1): bbbbbbbbbaaaaaaaaaaaa 00000000000011111111
Недостающие биты будут проинициализированы нулями. Если размер строки больше, чем размер битсета, то старшие биты будут отброшены.
Операции <<, >>
В программах выше нетрудно заметить, что битсет, как и объект класса string
, можно выводить с помощью потоковой операции вставка "<<"
, без поэлементного перебора. При выводе элементы будут перестроены в обратном порядке. Операция извлечения - ">>"
используется аналогично, но элементы будут сохраняться в битсете так, как было описано ранее для инициализации с помощью строки.
Программа 24.3
#include <iostream> #include <bitset> using namespace std; int main() { cout << "Введите битовую последовательность:" << endl; bitset<20> mybs; cin >> mybs; for (size_t i = 0; i < mybs.size(); i++) cout << mybs[i]; cout << endl; cout << mybs << endl; return 0; }
Введите битовую последовательность: 10101010101111101101 10110111110101010101 10101010101111101101
Инициализация числовым значением
Помимо инициализации строкой, битсет можно инициализировать фундаментальными целочисленными типами, которые будут преобразованы в беззнаковый тип unsigned long long
. Если размер последовательности битов числа меньше, чем размер битсета, то старшие биты будут инициализированы нулевыми битами, а если больше, то старшие биты будут отброшены. Например:
Программа 24.4
#include <iostream> #include <bitset> using namespace std; int main() { bitset<8> mybs1(0b1111111111); bitset<8> mybs2(2017); //0b11111100001 bitset<8> mybs3(0x75BCD15); //0b111010110111100110100010101 bitset<8> mybs4(0b1111); cout << mybs1 << "\n" << mybs2 << "\n" << mybs3 << "\n" << mybs4 << "\n" << endl; return 0; }
11111111 11100001 00010101 00001111
Доступ к элементам и их изменение
Не велика была бы польза от этого контейнера, если бы битсет не имел большой набор методов и перегруженных логических операций.
Элементы битсета можно обходить обычным циклом for
(диапазонный for
использовать нельзя, так как итераторы в данном контейнере не поддерживаются) с использованием операции обращения по индексу []
. Проверка выхода за границы массива не производится.
Метод test()
Возвращает значение бита, который находится в позиции pos
:
bool test(size_t pos) const;
В отличии от operator[]
, метод производит проверку выхода за границы массива с вызовом исключения out_of_range
, если pos
не является корректной позицией в наборе битов.
Методы all(), any() и none()
Проверяют, соответственно, что все биты были установлены в true
(all
), что хотя бы один бит был установлен в true
(any
) и что ни один из битов не был установлен в true
(none
). Возвращают true
, или false
, в противном случае.
Метод count()
Возвращает количество битов, которые установлены в true
:
size_t count() const;
Метод size()
Возвращает количество битов, которые содержатся в массиве:
constexpr size_t size() const;
Метод set()
Устанавливает все биты или только в указанной позиции pos
в значение true
:
bitset<N>& set(); bitset<N>& set(size_t pos);
Метод reset()
Сбрасывает все биты или только в указанной позиции pos
в значение false
:
bitset<N>& reset(); bitset<N>& reset(size_t pos);
Метод flip()
Инвертирует биты, то есть меняет значение true
на false
(и наоборот), во всем массиве или только в позиции pos
:
bitset<N>& flip(); bitset<N>& flip(size_t pos);
Логические операции
Перегруженные логические операции реализуют основные операции Булевой алгебры над битсетами одинаковой длины. К этим операциям относятся следующие: побитовое "И", побитовое "ИЛИ" и побитовое "Исключающее ИЛИ" (XOR) с присваиваниями, а также инверсия (&=
,|=
,^=
,~
). Исходя из сущности операции (с присваиванием), битсет принимает новое значение путем выполнения побитовых операций с битсетом other
или инверсии битов данного битсета:
bitset& operator&=(const bitset & other); bitset & operator|=(const bitset & other); bitset & operator^=(const bitset & other); bitset operator~() const;
К битсетам можно применять и перегруженные бинарные операции &
,|
и ^
. В этом случае мы можем получить новый битсет на основе выполнения побитовых операций с двумя другими битсетами.
Программа 24.5
#include <iostream> #include <bitset> using namespace std; int main() { bitset<8> mybs1(0b10101011); bitset<8> mybs2(0b00101111); bitset<8> mybs3(0b11111111); mybs1 &= mybs2; cout << mybs1 << endl; mybs1 |= mybs2; cout << mybs1 << endl; bitset<8> mybs4(mybs1 ^ mybs3); cout << mybs4 << endl; return 0; }
00101011 00101111 11010000
Преобразования
Битсет поддерживает и обратные преобразования в строку или в беззнаковое целое unsigned long long
.
to_string()
Преобразует битсет в строку. Может принимать два необязательных аргумента маски-символы для true
(one) и false
(zero):
b.to_string(zero, one)
Если используется один параметр, то маска будет использоваться для "0"
.
to_ullong()
Преобразует содержимое битового набора в целочисленное значение типа unsigned long long
:
b.to_ullong()
Функция не принимает никаких аргументов, но может возвращать исключение overflow_error
, если битсет не может быть представлен в типе unsigned long long
(т. е. размер типа меньше, чем размер битсета).
Преобразования производятся по тому же принципу, по которому осуществляется операции ввода/вывода битсета посредством перегруженных операций <<
и >>
.
Программа 24.6
#include <iostream> #include <bitset> using namespace std; int main() { bitset<15> mybs(2017ull); cout << mybs << "\n" << mybs.to_string('*', '#') << "\n" << mybs.to_ullong() << endl; return 0; }
000011111100001 ****######****# 2017
Приведем пример практического использования этого контейнера. Решим следующую задачу.
Программа 24.7 Проведены 50 экспериментов. Результаты этих экспериментов записаны в виде массива действительных чисел в интервале от 10 до 200, включительно. Верными результатами считаются только те, которые удовлетворяют следующим условиям:
1. принадлежат интервалу [A, B];
2. среднее арифметическое трех предыдущих измерений должно быть меньше, чем среднее арифметическое трех последующих измерений;
3. результаты каждого из трех первых и трех последних экспериментов верны в том случае, если они больше средних арифметических трех последующих или предыдущих результатов, соответственно.
Определить количество экспериментов, в ходе которых получены верные результаты. Являются ли результаты первого и последнего эксперимента верными. Проверить, является ли результат К-го эксперимента верным, и если это так, то аннулировать этот результат.
#include <iostream> #include <bitset> #include <vector> #include <random> #include <ctime> using namespace std; int main() { size_t A, B; const int N = 50; default_random_engine rnd(time(0)); uniform_real_distribution<double> d(10.0, 200.0); cout << "A = "; cin >> A; cout << "B = "; cin >> B; vector<double> ex; bitset<N> exbi; ex.reserve(N); for (size_t i = 0; i < N; i++) { ex.push_back(d(rnd)); cout.precision(3); cout << ex[i] << " "; } for (size_t i = 0; i < ex.size(); i++) if (ex[i] >= A && ex[i] <= B) { double wl = (ex[i + 1] + ex[i + 2] + ex[i + 3]) / 3; double wr = (ex[i - 1] + ex[i - 2] + ex[i - 3]) / 3; if (i < 3 && ex[i] > wl) exbi.set(i); else if (i > ex.size() - 3 && ex[i] > wr) exbi.set(i); else if (wl < wr) exbi.set(i); } cout << "\n" << exbi; cout << "\nКоличество верных результатов: " << exbi.count() << (exbi.test(0) == 1 || exbi.test(exbi.size()-1) == 1 ? "\nРезультаты первого или последнего эксперимента верные" : "\nРезультаты первого и последнего эксперимента не верные") << "\nВведите номер эксперимента: "; cin >> A; if (exbi.test(A)) { exbi.reset(A); cout << "Результаты " << A << "-го эксперимента обнулены"; } else { cout << "Результаты " << A << "-го эксперимента не верные"; } cout << "\n" << exbi << endl; return 0; }
A = 50 B = 150 41.1 138 121 191 13.7 83.2 116 181 112 13.2 41 144 109 91.7 176 137 70.6 143 160 157 74.9 22.7 170 19.5 41.7 195 93.4 94.3 153 134 30.2 84.4 19.8 91.5 149 54.2 160 82.5 66.8 196 134 115 189 79.9 21.4 39.9 56.7 148 113 111 11000010100000000010101000000100001000000100000110 Количество верных результатов: 12 Результаты первого или последнего эксперимента верные Введите номер эксперимента: 49 Результаты 49-го эксперимента обнулены 01000010100000000010101000000100001000000100000110