Большие битовые массивы в C

struct может назначать членам битовые размеры, но это степень «битового типа» в «C».

struct int_sized_struct {
   int foo:4;
   int bar:4;
   int baz:24;
};

Остальное делается с помощью побитовых операций. Например. поиск этого растрового изображения PID можно выполнить с помощью:

extern uint32_t *process_bitmap;
uint32_t *p = process_bitmap;
uint32_t bit_offset = 0;
uint32_t bit_test;

/* Scan pid bitmap 32 entries per cycle. */
while ((*p & 0xffffffff) == 0xffffffff) {
  p++;
}

/* Scan the 32-bit int block that has an open slot for the open PID */
bit_test = 0x80000000;
while ((*p & bit_test) == bit_test) {
   bit_test >>= 1;
   bit_offset++;
}
pid = (p - process_bitmap)*8 + bit_offset;

Это примерно в 32 раза быстрее, чем простое циклическое сканирование массива с одним байтом на PID. (На самом деле больше, чем 32x, поскольку большая часть растрового изображения останется в кеше ЦП.)

Битовые массивы — это просто массивы байтов, в которых вы используете побитовые операторы для чтения отдельных битов.

Предположим, у вас есть 1-байтовая переменная char. Он содержит 8 бит. Вы можете проверить, является ли самый младший бит истинным, выполнив побитовую операцию И со значением 1, например.

 char a = /*something*/;
 if (a & 1) {
    /* lowest bit is true */
 }

Обратите внимание, что это один амперсанд. Он полностью отличается от логического оператора И &&. Это работает, потому что a & 1 будет маскировать все биты, кроме первого, и поэтому a & 1 будет ненулевым тогда и только тогда, когда младший бит a равен 1. Точно так же вы можете проверить, является ли второй младший бит истинным, объединив его с 2 и третий с помощью И с 4 и т. д. для продолжающихся степеней двойки.

Таким образом, битовый массив из 32 768 элементов будет представлен как массив byte из 4096 элементов, где первый байт содержит биты 0-7, второй байт содержит биты 8-15 и т. д. Чтобы выполнить проверку , код будет выбирать байт из массива, содержащего бит, который он хочет проверить, а затем использовать побитовую операцию для чтения значения бита из байта.

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

То, как вы записываете бит, зависит от того, хотите ли вы записать 0 или 1. Чтобы записать 1-бит в байт a, вы выполняете операцию, противоположную операции И: операцию ИЛИ, например.

 char a = /*something*/;
 a = a | 1; /* or a |= 1 */

После этого младший бит a будет установлен в 1 независимо от того, был он установлен ранее или нет. Опять же, вы можете записать это во вторую позицию, заменив 1 на 2, или в третью на 4, и так далее для степеней двойки.

Наконец, чтобы записать нулевой бит, вы выполняете И с инверсией позиции, в которую хотите записать, например.

 char a = /*something*/;
 a = a & ~1; /* or a &= ~1 */

Теперь младший бит a установлен в 0, независимо от его предыдущего значения. Это работает, потому что в ~1 все биты, кроме младшего, будут установлены в 1, а самый младший — в ноль. Это маскирует младший бит до нуля и оставляет оставшиеся биты a в покое.

см. http://graphics.stanford.edu/~seander/bithacks.html

В C нет битового типа, но манипулирование битами довольно прямолинейно. У некоторых процессоров есть инструкции, специфичные для битов, для которых приведенный ниже код был бы хорошо оптимизирован, даже без этого он должен быть довольно быстрым. Может или не может быть быстрее, используя массив 32-битных слов вместо байтов. Встраивание вместо функций также поможет повысить производительность.

Если у вас есть память для записи, просто используйте целый байт для хранения одного бита (или целого 32-битного числа и т. д.), что значительно улучшит производительность за счет используемой памяти.

unsigned char data[SIZE];

unsigned char get_bit ( unsigned int offset )
{
    //TODO: limit check offset
    if(data[offset>>3]&(1<<(offset&7))) return(1);
    else return(0);
}
void set_bit ( unsigned int offset, unsigned char bit )
{
    //TODO: limit check offset
    if(bit) data[offset>>3]|=1<<(offset&7);
    else    data[offset>>3]&=~(1<<(offset&7));
}