Битовое поле против Битсета

Question

Я хочу хранить биты в массиве (например, структура). Таким образом, я могу следовать любому из следующих двух подходов

Подход № 1 (AN 1)

struct BIT
{
   int data : 1
};

int main()
{
   BIT a[100];
   return 0;
}

Подход № 2 (AN 2)

int main()
{
    std::bitset<100> BITS;
    return 0;
}

Почему кто-то предпочел бы AN 2 над AN 1?

Answer 1

Потому что подход Nr. 2 фактически использует 100 бит памяти плюс некоторые очень незначительные (постоянные) издержки, в то время как nr. 1 обычно использует четыре байта памяти на Bit структуру. Как правило, struct имеет размер по крайней мере один байт в соответствии со стандартом C ++.

#include <bitset>
#include <iostream>

struct Bit { int data : 1; };

int main()
{
    Bit a[100];
    std::bitset<100> b;
    std::cout << sizeof(a) << "\n";
    std::cout << sizeof(b) << "\n";
}

отпечатков

400
16

Помимо этого, bitset оборачивает ваш битовый массив в хорошее представление объекта со многими полезными операциями.

Answer 2

Хороший выбор зависит от того, как вы собираетесь использовать биты.

std::bitset<N> имеет фиксированный размер. Visual C ++ 10.0 не соответствует требованиям. конструкторам; в общем, вы должны предоставить обходной путь. По иронии судьбы, это произошло из-за того, что Microsoft считала исправлением ошибки - они представили конструктор, принимающий аргумент int, насколько я помню.

std::vector<bool> оптимизируется так же, как и std::bitset. Стоимость: индексирование напрямую не предоставляет ссылку (в C ++ нет ссылок на отдельные биты), но вместо этого возвращает прокси-объект, который вы не заметите, пока не попробуете использовать его в качестве ссылки. Преимущество: минимальное хранилище, а вектор может быть изменен по мере необходимости.

Просто используя, например, unsigned также вариант, если вы собираетесь работать с небольшим количеством битов (на практике 32 или меньше, хотя формальная гарантия составляет всего 16 бит).

Наконец, все идентификаторы UPPERCASE по соглашению (кроме Microsoft) зарезервированы для макросов, чтобы уменьшить вероятность конфликтов имен. Поэтому не рекомендуется использовать ВСЕ идентификаторы UPPERCASE ни для чего, кроме макросов. И всегда использовать ВСЕ UPPERCASE идентификаторы для макросов (это также облегчает их распознавание).

Приветствия & hth.,

Answer 3

битовый набор имеет больше операций

Answer 4

Процитируем страницу cplusplus.com на bitset : «Этот класс очень похож на обычный массив, но оптимизирован для распределения пространства».Если ваши целые числа составляют 4 байта, битовый набор использует в 32 раза меньше места.

Даже выполнение bool bits[100], как предположил sbi, все еще хуже, чем битовый набор, потому что большинство реализаций имеют> = 1-байтовое bools.

Если только по соображениям интеллектуального интереса вы хотите реализовать свой собственный набор битов, вы можете сделать это, используя битовые маски:

typedef struct {
  unsigned char bytes[100];
} MyBitset;

bool getBit(MyBitset *bitset, int index)
{
  int whichByte = index / 8; 
  return bitset->bytes[whichByte] && (1 << (index = % 8));
}

bool setBit(MyBitset *bitset, int index, bool newVal)
{
  int whichByte = index / 8;

  if (newVal)
  {
    bitset->bytes[whichByte] |= (1 << (index = % 8));
  }
  else
  {
    bitset->bytes[whichByte] &= ~(1 << (index = % 8));
  }
}

(извините за использование структуры вместо классаКстати, я имею в виду прямое C, потому что я нахожусь в середине низкоуровневого задания для школы. Очевидно, что двумя огромными преимуществами использования класса являются перегрузка операторов и возможность иметь массив переменного размера.)

Answer 5

Подход № 1, скорее всего, будет скомпилирован как массив 4-байтовых целых чисел, и один бит каждого из них будет использоваться для хранения ваших данных. Теоретически, умный компилятор мог бы оптимизировать это, но я бы на это не рассчитывал.

Есть ли причина, по которой вы не хотите использовать std::bitset?