§24 Контейнер bitset. Логические операции

Общие сведения

Контейнер 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
Print Friendly, PDF & Email

Comments are closed