Как я могу иметь ровно 2 бита в памяти?

Question

Я должен иметь возможность хранить значение в структуре данных, которое может быть от 0 до 3 .. поэтому мне нужно 2 бита.Эта структура данных, я буду велика 2 ^ 16 мест.Итак, я хочу иметь 2 ^ 16 * 2 (бит).В C ++ вы используете в памяти ровно 2 бита?

Answer 1

Вам нужно два бита на единицу (не три), поэтому вы можете упаковать четыре единицы в один байт или 16 единиц в одно 32-разрядное целое число.

Таким образом, вам понадобится std::array<uint32_t, 4096> для размещения 2 ¹⁶ единиц 2-битных значений.

Вы получаете доступ к n ^th следующим образом:

unsigned int get(std::size_t n, std::array<uint32_t, 4096> const & arr)
{
    const uint32_t u = arr[n / 16];
    return (u >> (2 * (n % 16))) & 0x3;
}

В качестве альтернативы, вы можете использовать битовое поле:

struct BF32 {
  uint32_t u0 : 2;
  uint32_t u1 : 2;
  //...
  uint32_t uF : 2;
}

А затем сделайте std::array<BF32, 4096>.

Answer 2

Нельзя выделить один объект размером менее 1 байта (поскольку 1 байт является наименьшей адресуемой единицей в системе).

Однако вы можете иметь части структуры, которые меньше байта, используя битовые поля. Вы можете создать одно из них, чтобы оно содержало 8 ваших значений, размер которых составляет ровно 3 байта:

#pragma pack(1) // MSVC requires this
struct three_by_eight {
  unsigned value1 : 3;
  unsigned value2 : 3;
  unsigned value3 : 3;
  unsigned value4 : 3;
  unsigned value5 : 3;
  unsigned value6 : 3;
  unsigned value7 : 3;
  unsigned value8 : 3;
}
__attribute__ ((packed)) // GCC requires this
;

С ними может быть неуклюже работать, поскольку к ним нельзя получить доступ с помощью [] .... Лучше всего было бы создать собственный класс, который работает аналогично bitset, но работает с 3 битами вместо 1.

Answer 3

Если вы не работаете со встроенной системой и ресурсов достаточно, вы можете взглянуть на std::bitset<>, что облегчит вашу работу программиста.

Но если вы работаете со встроенной системой, набор битов, вероятно, вам не подходит (ваш компилятор, вероятно, даже не поддерживает шаблоны). Существует множество методов манипулирования битами, каждый из которых имеет свои причуды; вот статья, которая может вам помочь:
> http://www.atmel.com/dyn/resources/prod_documents/avr_3_04.pdf

Answer 4

3^5 = 243 

и может вместить 5 записей в 8 бит. Таким образом, вы тратите на 20% меньше места на хранение большого количества данных. Все, что вам нужно, это справочная таблица для 2-х направленных поисков и манипуляций.

Answer 5

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

Из-за выравнивания указатели на x86 или x64 часто кратны 4, следовательно, два наименее значимых бита таких указателей (например, указатели на int) всегда 0. Вы можете использовать это и пробраться туда со своими двумя битами, но вы должны убедиться, что удалили их при доступе к этим указателям (в зависимости от архитектуры, я не уверен здесь).

Опять же, это противный, опасный и красивый UB, но, возможно, оно того стоит в вашем случае.

Answer 6

Прошлой ночью было обсуждение размера, выделенного структурам битового поля . Структура не может быть меньше байта, и с большинством машин и компиляторов будет 2 или 4, в зависимости от компилятора и размера слова. Итак, нет, вы не можете получить 3-битную структуру (2-битную, как вам действительно нужно). Однако вы можете упаковать биты в массив, скажем, uint64_t s. Или вы можете создать структуру из 16 2-битных членов и посмотреть, делает ли gcc 4-байтовую структуру, а затем использовать их массив.

Answer 7

от 0 до 3 имеет 4 возможных значения. Поскольку log2 (4) == 2 или 2 ^ 2 == 4, вам нужно два бита, а не три.

Возможно, вы захотите использовать битовые поля