В переменной типа bool можно хранить только один бит, в то время как переменная занимает в памяти восемь. Если нужно хранить множество булевых значений, например 400, то при использовании массива эти данные займут в памяти больше трёх килобайт. Если же для хранения этих значений использовать битовые шкалы, то все данные уместятся в те же 400 байт.

Мы рассмотрим только основы по работе с битовыми шкалами и ограничимся размером битовой шкалы в 16 бит, то есть в данной структуре данных можно будет хранить 16 булевых значений.

Класс для битовых шкал - Bitvector

Создадим класс для битовых шкал - Bitvector:

class Bitvector
{
private:
  unsigned short bv;
public:
  Bitvector(): bv(0) {}
};

В классе всего одна переменная - bv типа unsigned long. Размер типа unsigned long - 16 бит. Собственно переменная bv - это и есть битовая шкала.

Конструктор класса Bitvector устанавливает переменную bv в ноль. Чтобы установить в шестнадцатибитной шкале все биты в единицу, можно присвоить переменной bv значение 65535. Но для больших битовых шкал проделать подобную операцию довольно проблематично: уже при 64-ёх битах придётся использовать двадцатизначное число.

Переменной bv можно пользоваться как и любой другой:

bv = 3;
bv = 79;
cout << bv;

Но делать этого не нужно! В конце-то концов, мы битовую шкалу создаём или что?

Итак, теперь у нас есть шестнадцатибитная переменная. Чтобы из этой переменной получить полноценную битовую шкалу, необходимо научиться получать доступ к отдельным битам. Для доступа к отдельным битам нам понадобятся поразрядные (побитовые) операции сдвига: >> - операция поразрядного (побитового) сдвига вправо и << - операция поразрядного (побитового) сдвига влево. Кроме того мы будем использовать логические поразрядные операции. О поразрядных логических операциях вы можете узнать в разделе C++, на страничке Операции C++.

Операции поразрядного (побитового) смещения

В С++ представлены две операции поразрядного (побитного) сдвига (смещения): >> и <<. Рассмотрим пример работы с этими операциями:
unsigned short bv = 128;
// А вот как bv выглядит в памяти:
// 0000000010000000

bv = bv << 1;
// Теперь bv = 256
// 0000000100000000

bv = bv >> 3;
// Теперь bv = 32
// 0000000000100000
Жирным шрифтом показана текущая позиция, подчёркиванием показана позиция текущего бита до операции.

Небольшое замечание: биты считаются справа налево. Самый правый бит - самый младший, самый левый бит - самый старший. Отсчёт начинается с нуля!

В данном примере я специально взял степень двойки (27 = 128) для простоты.

Для более наглядного представления битовой шкалы из шестнадцати битов я нарисовал картинку:

Здесь мы видим как работают операции поразрядных сдвигов. Левый операнд - переменная в которой нужно произвести смещение, а правый операнд - количество битов в смещении.

При смещении сдвигаются все биты переменной. При этом крайние биты отбрасываются. Рассмотрим небольшой пример:

unsigned short bv = 32769;
// 1000000000000001;

if (условие a)
{
  bv = bv << 1;
  // bv = 2;
  // 0000000000000010
}
else if (условие b)
{
  bv = bv >> 1;
  // bv = 16384;
  // 0100000000000000
}

Замечание:
Операции поразрядных сдвигов и операции извлечения и вставки - совершенно разные операции и не имеют ничего общего кроме одинакового обозначения. Операции смещения работают с битовым представлением чисел, а операции вставки и извлечения позволяют вывести информацию на экран или, наоборот, получить информацию с клавиатуры.

Методы класса Bitvector

В предыдущем примере мы установили два бита в переменной bv: первый и последний.

Если вам нужно установить только один бит, то этого можно добиться присвоив переменной степень двойки. Причём, степень двойки равна номеру того бита который нужно установить. На картинке это наглядно показано - все биты пронумерованы.

Конечно такой способ установки битов в битовых шкалах никуда не годится. Вместо этого мы создадим метод Set (set - установить):

void Set (int, bool); // прототип

void Bitvector::Set (int index, bool value)
{
  unsigned short t = 1; // временная переменная;
                        // 0000000000000001
  t = t << index;

  if (value == 1) // нужно установить бит  в единицу
  {
    bv = bv | t;
  }
  else // нужно установить бит  в ноль
  {
    t = ~t;
    bv = bv & t;
  }
}

Разберём подробно метод Set. Метод принимает два параметра: номер бита - index и значение бита - value. Рассмотрим пример. Пусть bv будет содержать 1001000011001101, и нам нужно установить в пятый бит (с номером четыре - отсчёт ведётся от нуля) единицу, а затем в четвёртый бит - ноль.

bv1.Set(4,1);

// t = t << 4;
// 0000000000010000 - t
// 1001000011001101 - bv
// bt = bv | t;
// 1001000011011101

bv1.Set(3,0);

// t = t << 3;
// 0000000000001000
// t = ~t;
// 1111111111110111 - t
// 1001000011011101 - bv
// bv = bv & t;
// 1001000011010101

Если вы внимательно проследите процесс происходящий в методе (закоментированные строки), думаю вы поймёте как происходит установка битов.

В Set используется временная переменная

В теле метода используется временная переменная t, которая хранит единицу. Эта переменная используется для смещения битов. Мы смещаем все биты данной переменной на количество битов index.

Если в бит нужно установить ноль, то над переменными bv и t производится операция поразрядного логического ИЛИ - |.

Если в бит нужно установить единицу, то сначала выполняется операция поразрядное логическое НЕ - ~. Данная операция просто меняет все биты на противоположные. После смены всех битов во временной переменной, нада переменными bv и t производится операция поразрядного логического И - &.

Чтобы установить значение в первый бит, нужно вызвать метод, передав ему index - 0, а для того, чтобы установить значение в последний бит, index - 15;

Доступ к элементам битовых шкал

Теперь создадим метод, который позволит получить доступ к отдельным битам битовых шкал. Для этого используется метод Access (access - получить доступ):

int Access (int);

int Bitvector::Access(int index)
{
  int t = 1;
  t = t << index;
  t = bv & t;
  t = t >> index;
  return t;
}

Для наглядности рассмотрим пример. Значение bv - прежнее:

bv1.Access(14)

// t = t << index
// 0100000000000000 - t
// 1001000011010101 - bv
// t = bv & t
// 0000000000000000
// t = t >> index;
// 0000000000000000

bv1.Acess(7)

// t = t << index
// 0000000010000000 - t
// 1001000011010101 - bv
// t = bv & t
// 0000000010000000
// t = t >> index;
// 0000000000000001

Заключение

Мы рассмотрели битовую шкалу, состоящую только из шестнадцати элементов. Наибольшую битовую шкалу, используя только одну переменную, можно получить благодаря типу __int64 - 64 бита. Когда нужны большие битовые шкалы (сотни битов или больше), то обычно используется массив массив переменных. Только вместо типа unsigned short используется unsigned int.

Вот в общем-то и всё, что я хотел рассказать про битовые шкалы. Напоследок стоит сказать пару слов про использование битовых шкал в играх. Конечно же с помощью битовых шкал можно сэкономить память, но в настоящий момент, это уже не актуально, так как рядовые компьютеры снабжаются просто колоссальными объёмами памяти. Но есть другой сектор, где нужно экономить память - сетевые игры и прежде всего MMO: когда в мире взаимодействует тысяча игроков, проблема экономии встаёт в полный рост. Кроме того, используя определённые техники, можно добиться некоторого выигрыша в производительности. Мы ещё вернёмся к рассмотрению этих техник.

Упражнения

1. В класс Bitvector добавьте два метода: SetAll (установить всё) и ClearAll (очистить всё). Из названия методов, думаю понятно, что они должны делать.

2. Добавьте к классу Bitvector метод Out, который будет выводить битову шкалу на экран. Для этого воспользуйтесь циклом и методом Access.

3. Подумайте, как можно создать битовую шкалу из 64-ёх битов, используя тип unsigned short. Доступ к отдельным битам должен осуществляться через метод Access. Например: Access(38), Access(0), Access(63).

P.S.: Если что непонятно, и нужны разъяснения, пишите на e-mail или в комментарии к блогу.
P.S.S.: Если заметите ошибки, пожалуйста, сообщите.