Могу ли я выделить определенное количество битов в C?
https://stackoverflow.com/questions/284519
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытаюсь сохранить большой объем логической информации, которая определяется во время выполнения.Мне было интересно, каким мог бы быть наилучший метод.
В настоящее время я пытаюсь выделить память, используя:
pStatus = malloc((<number of data points>/8) + 1);
думая, что это даст мне достаточно битов для работы.Затем я мог бы ссылаться на каждое логическое значение, используя указатель в обозначении массива:
pStatus[element]
К сожалению, похоже, что это работает не очень хорошо.Во-первых, у меня возникли трудности с инициализацией памяти целочисленным значением 0.Можно ли это сделать с помощью memset()?Тем не менее, я не думаю, что это влияет на то, почему я терплю крах при попытке доступа pStatus[element].
Я также не совсем уверен, что этот подход является наилучшим для использования.Чего я действительно хочу, так это, по сути, гигантской битовой маски, которая отражает статус логических значений.Я что-то пропустил?
Решение
pStatus = malloc((<number of data points>/8) + 1);
Это выделяет достаточно байт для ваших битов.Однако,
pStatus[element]
Это приводит к доступу к элементу 'th байт, не укушенный.Таким образом, когда элемент составляет более одной восьмой от общего числа битов, вы получаете доступ к концу выделенного массива.
Я бы определил несколько вспомогательных функций
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;
}
(проверка ошибки в диапазоне элемента опущена для ясности.Вы тоже могли бы создать эти макросы)
Другие советы
...думая, что это даст мне достаточно битов для работы.Затем я мог бы ссылаться на каждое логическое значение, используя указатель в обозначении массива:
pStatus[element]
элемент адресует байты, а не биты.Вы хотите что-то вроде:
pStatus[element/8] & (1 << (element % 8))
Маленькая точка:чтобы получить достаточно памяти для хранения N битов, (N / 8) + 1 байт является неточным (может быть слишком много).
Однако (N + 7)/8 всегда является минимальным числом.
Ну, самым простым ответом было бы использовать calloc вместо malloc .
Он определен для инициализации памяти, которую он выделяет, равным нулю, и часто может сделать это, используя приемы сопоставления страниц.
Это решит вашу проблему с инициализацией памяти.Остальные дюжины постов здесь, похоже, адекватно решают проблему индексации и тот факт, что вы иногда выделяете дополнительный байт (о ужас!), поэтому я не буду здесь повторять их содержание.
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)
то, что у вас было, будет работать, но иногда тратит байт впустую
Я не могу не заметить, что все ответы на C здесь, похоже, предполагают, что байт равен 8 битам.Это не обязательно верно в C (хотя, конечно, это будет верно на большинстве основных аппаратных средств), поэтому делать такое предположение в коде - довольно дурной тон.
Правильный способ написания кода, не зависящего от архитектуры, заключается в
#include <limits.h>
и затем используйте CHAR_BIT макрос везде, где вам нужно "количество битов в char".
Сделайте себя счастливее и определите тип и функции для работы с этим типом.Таким образом, если вы обнаружите, что доступ к битам происходит слишком медленно, вы можете изменить единицу памяти на логическое значение на байт / слово / длину или принять разреженные / динамические структуры данных, если память действительно является проблемой (т. Е., если ваши наборы в основном состоят из нулей, вы могли бы просто сохранить список с координатами единиц.
Вы можете написать свой код таким образом, чтобы он был полностью невосприимчив к изменениям в реализации вашего битового вектора.
pStatus[элемент] не адресует бит.Точный байт, который он получает, зависит от типа pStatus - я предполагаю, что char * или эквивалент - поэтому pStatus[element] возвращает вам байт элемента.
Вы могли бы memset установить равным 0, да.
pStatus = malloc((<number of data points>/8) + 1);
Эта часть прекрасна.
pStatus[element]
вот тут-то у вас и возникают проблемы.Вы адресуете байты, когда хотите адресовать биты.
pStatus[element / 8 ]
получит вам нужный байт в массиве.
Вам нужно выделить c = malloc((N+7)/8) байт, и вы можете установить n-й с помощью
c[n/8]=((c[n/8] & ~(0x80 >> (n%8))) | (0x80>>(n%8)));
ясно с
c[n/8] &= ~(0x80 >> (n%8));
и протестируйте с помощью
if(c[n/8] & (0x80 >> (n%8))) blah();
Если вы не возражаете против написания оболочек, вы также можете использовать bit_set или bit_vector из STL C ++, похоже, что в них (особенно в последнем) есть именно то, что вам нужно, уже закодированное, протестированное и упакованное (и множество наворотов).
Очень жаль, что нам не хватает простого способа использования кода C ++ в приложениях на C (нет, создание оболочки для меня не является простым делом и не доставляет удовольствия, а означает больше работы в долгосрочной перспективе).
Что было бы не так с std::vector<bool>?
Меня поражает, что только в одном ответе здесь упоминается CHAR_BIT .Байт часто состоит из 8 бит, но не всегда.
Ваш код распределения правильный, смотрите set_bit() и get_bit() функции, приведенные в этот ответ чтобы получить доступ к логическому значению.
Если вы ограничены всего несколькими битами, вы можете вместо решения eaanon01 также использовать встроенное в c средство bitfield (существует очень мало случаев, когда вы могли бы их использовать, но это был бы один)
Для этого немного потрясающего материала я могу порекомендовать:Херни Уорренс "Хакерский восторг"
Логическое значение - это "никогда" отдельное значение в C.Таким образом, структура может быть создана для того, чтобы заставить вас двигаться дальше.
Это правда, что вы не инициализируете область памяти, поэтому вам нужно сделать это индивидуально.
Вот простой пример того, как вы могли бы сделать это с помощью объединений, структур и перечислений
typedef unsigned char BYTE;
typedef unsigned short WORD;
typedef unsigned long int DWORD;
typedef unsigned long long int DDWORD;
enum STATUS
{
status0 = 0x01,
status1 = 0x02,
status2 = 0x04,
status3 = 0x08,
status4 = 0x10,
status5 = 0x20,
status6 = 0x40,
status7 = 0x80,
status_group = status0 + status1 +status4
};
#define GET_STATUS( S ) ( ((status.DDBuf&(DDWORD)S)==(DDWORD)S) ? 1 : 0 )
#define SET_STATUS( S ) ( (status.DDBuf|= (DDWORD)S) )
#define CLR_STATUS( S ) ( (status.DDBuf&= ~(DDWORD)S) )
static union {
BYTE BBuf[8];
WORD WWBuf[4];
DWORD DWBuf[2];
DDWORD DDBuf;
}status;
int main(void)
{
// Reset status bits
status.BBuf[0] = 0;
printf( "%d \n", GET_STATUS( status0 ) );
SET_STATUS( status0 );
printf( "%d \n", GET_STATUS( status0 ) );
CLR_STATUS(status0);
printf( "%d \n", GET_STATUS( status0 ) );
SET_STATUS( status_group );
printf( "%d \n", GET_STATUS( status0 ) );
system( "pause" );
return 0;
}
Надеюсь, это поможет.Этот пример может обрабатывать до 64 логических значений состояния и может быть легко расширен.
Этот пример основан на Char = 8 бит int = 16 бит long int = 32 бита и long long int = 64 бита
Теперь я также добавил поддержку статусных групп.
