Большие битовые массивы в C - PullRequest
Новая
       4

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

2 голосов
/ 24 сентября 2010

Наш профессор ОС упомянул, что для назначения идентификатора процесса новому процессу ядро ​​постепенно ищет первый нулевой бит в массиве с размером, равным максимальному числу процессов (по умолчанию ~ 32 768), где выделен процесс в id хранится 1.

Насколько я знаю, в C. нет битового типа данных. Очевидно, что-то здесь мне не хватает.

Есть ли такая специальная конструкция, из которой мы можем построить битовый массив? Как это сделано точно?

Что более важно, какие операции можно выполнить с таким массивом?

Ответы [ 4 ]

4 голосов
/ 24 сентября 2010

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

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

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

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

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

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

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

 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 в покое.

3 голосов
/ 24 сентября 2010

A 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 голос
/ 24 сентября 2010
0 голосов
/ 24 сентября 2010

Нет битового типа в 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));
}
...