Поле бит vs Bitset

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; 
} 

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

Answer 1

Потому что подход эл. 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

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

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

Answer 3

BitSet имеет more operations

Answer 4

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

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

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

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

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

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

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

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

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

Приветствия & НТН.,