Могу ли я выделить определенное количество бит в C?

Question

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

В настоящее время я пытаюсь выделить память, используя:

pStatus = malloc((<number of data points>/8) + 1);

думая, что это даст мне достаточно битов для работы. Затем я мог бы ссылаться на каждое логическое значение, используя указатель в записи массива:

pStatus[element]

К сожалению, это, похоже, работает не очень хорошо. Во-первых, мне трудно инициализировать память целочисленным значением 0. Можно ли это сделать с помощью memset()? Тем не менее, я не думаю, что это влияет на причину сбоя при попытке доступа к pStatus[element].

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

Answer 1

pStatus = malloc((<number of data points>/8) + 1);

Это выделяет достаточно байтов для ваших битов. Тем не менее,

pStatus[element]

Получает доступ к элементу байт , а не бит. Поэтому, когда элемент составляет более одной восьмой от общего числа битов, вы получаете доступ с конца выделенного массива.

Я бы определил несколько вспомогательных функций

int get_bit(int element)
{
    uint byte_index = element/8;
    uint bit_index = element % 8;
    uint bit_mask = ( 1 << bit_index);

    return ((pStatus[byte_index] & bit_mask) != 0);
}

void set_bit (int element)
{
    uint byte_index = element/8;
    uint bit_index = element % 8;
    uint bit_mask = ( 1 << bit_index);

    pStatus[byte_index] |= bit_mask);
}

void clear_bit (int element)
{
    uint byte_index = element/8;
    uint bit_index = element % 8;
    uint bit_mask = ( 1 << bit_index);

    pStatus[byte_index] &= ~bit_mask;
}

(ошибка проверки диапазона элементов оставлена ​​для ясности. Вы также можете сделать этот макрос)

Answer 2

... думая, что это даст мне достаточно битов для работы. Затем я мог бы ссылаться на каждое логическое значение, используя указатель в записи массива:

pStatus[element]

Элемент

адресует байтов , а не бит. Вы хотите что-то вроде:

pStatus[element/8] & (1 << (element % 8))

Answer 3

Небольшая точка: чтобы получить достаточно памяти для хранения N битов, (N / 8) + 1 байт неточно (может быть слишком много).

(N + 7) / 8 всегда минимальное число.

Answer 4

Ну, самый простой ответ - использовать calloc вместо malloc.

Он определен для инициализации памяти, которую он выделяет для нуля, и часто может делать это, используя приемы отображения страниц.

Это позаботится о вашей проблеме инициализации памяти. Другие дюжины сообщений здесь, похоже, адекватно решают проблему индексации и тот факт, что вы время от времени выделяете дополнительный байт (о ужас!), Поэтому я не буду повторять их содержание здесь.

Answer 5

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

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

#include <limits.h>

и затем используйте макрос CHAR_BIT, где вам нужно «количество бит в char».

Answer 6

pStatus [элемент] даст вам целый байт по этому адресу.

Чтобы установить определенный элемент, вы должны сделать что-то вроде:

pStatus[element >> 3] |= 1 << (element & 7);

Для сброса элемента:

pStatus[element >> 3] &= ~1 << (element & 7);

и для проверки элемента:

if (pStatus[element >> 3] & (1 << (element & 7)) != 0)

начальное распределение должно быть

pstatus = malloc((<number of data points> + 7) / 8)

то, что у вас было, будет работать, но время от времени тратит байт

Answer 7

Сделайте себя счастливее и определите тип и функции для работы с этим типом. Таким образом, если вы обнаружите, что битовый доступ слишком медленный, вы можете изменить единицу памяти на логическое значение на байт / слово / длинный или принять разреженные / динамические структуры данных, если память действительно является проблемой (т. Е. Если ваши наборы в основном равны нулю , вы можете просто сохранить список с координатами 1.

Вы можете написать свой код, чтобы быть полностью защищенным от изменений в реализации вашего битового вектора.

Answer 8

Меня удивляет, что только один ответ здесь упоминает CHAR_BIT. Байт часто 8 бит, но не всегда.

Answer 9

Что будет не так с std::vector<bool>?

Answer 10

Если вы ограничены несколькими битами, вы можете вместо решения eaanon01 также использовать встроенную функцию битового поля c (очень мало случаев, когда вы могли бы их использовать, но это будет один)

Для всего этого я могу порекомендовать: Херни Уорренс "Хакер Делайт"