Бит-поле vs Bitset

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

Подход № 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?

Ответы

Ответ 1

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

#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 обертывает ваш бит-массив в представлении хорошего объекта с множеством полезных операций.

Ответ 2

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

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

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

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

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

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

Ответ 4

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

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

Ответ 5

Чтобы процитировать страницу cplusplus.com на битрейте, "Класс очень похож на обычный массив, но оптимизирует для размещения пространства". Если ваш ints равен 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, потому что я нахожусь в середине низкоуровневого задания для школы. Очевидно, что двумя огромными преимуществами использования класса являются оператор перегрузка и возможность иметь массив переменного размера.)