Выделить n байтов для x битов

Question

Во-первых, это может быть общий алгоритм для любого языка, но я изучаю C, и если есть какие-то особенности C, я бы хотел знать!

Я пишу функцию, которая будет выделять достаточно памяти для заданного количества битов; в переменную long long *. Количество битов не может быть < 1. Я проверил алгоритм:

int bits;  // the function argument, checked for value > 0
size_t dataSize;  // the value passed to the malloc function

for (bits = 1; bits<100; bits++) {
   if (bits < sizeof(long long)) {
      dataSize = 1;
   } else {
      dataSize = (bits + (sizeof(long long) - (bits % sizeof(long long)))) / sizeof(long long);
   }

   printf("%d = %d\n", bits, (int) dataSize);
}

Смотрится нормально ... но безобразно :) Есть ли способ сделать это более элегантно? Спасибо!

Answer 1

Если вы хотите инициализировать ваше битовое поле нулевым значением, calloc() может быть предпочтительнее, чем malloc();вам, вероятно, также следует использовать тип без знака, чтобы избежать сдвигов со знаком при переворачивании битов.

#include <limits.h>

const size_t BITS_PER_BLOCK = sizeof (long long) * CHAR_BIT;
size_t count = bits / BITS_PER_BLOCK + !!(bits % BITS_PER_BLOCK);
unsigned long long *blocks = calloc(count, sizeof *blocks);

!! - довольно хакерский способ преобразования ненулевых значений в 1, что часто встречается в Cи используется здесь для выделения дополнительного блока, если количество битов не делится на BITS_PER_BLOCK.

Вы также можете получить необходимое количество блоков (как - среди прочего - Ларс указал в комментариях к другомуответ) через

size_t count = (bits + BITS_PER_BLOCK - 1) / BITS_PER_BLOCK;

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

Answer 2

Если вы хотите n бит, то правильное выражение для вычисления суммы long long будет:

int bits = n;
int items = (((bits - 1) / CHAR_BIT) / sizeof(long long)) + 1;

Answer 3

Если я что-то упустил, я думаю, что это будет просто:

int bits;
size_t dataSize;

dataSize = bits / (sizeof(long long) * 8);
if( bits % (sizeof(long long) * 8) ) { //Don't add 1 if it was evenly divisible
    dataSize++;
}
dataSize *= sizeof(long long)

Таким образом, предполагая размер long long 8 байтов, значение 1-64 вернет 8, 65-128вернул бы 16 и т. д.

Answer 4

Number_of_long_longs_for_x= (x + sizeof(long long) - 1)/sizeof(long long)

Теперь число битов в long long равно log2(ULLONG_MAX+1), а не sizeof(long long).Поэтому вам следует вернуться к своим расчетам.

Answer 5

#define SIZEOF_LL  sizeof(long long)
nbytes  =  (xbits  + 8         - 1) / 8;
nllongs =  (nbytes + SIZEOF_LL - 1) / SIZEOF_LL;

или если вы знаете размеры.

nbytes =  (xbits  + 7) / 8;
nllongs = (nbytes + 7) / 8;

Answer 6

Это ваш код с новым значением, добавленным к printf

int bits;  // the function argument, checked for value > 0
size_t dataSize;  // the value passed to the malloc function

for (bits = 1; bits<100; bits++) {
   if (bits < sizeof(long long)) {
      dataSize = 1;
   } else {
      dataSize = (bits + (sizeof(long long) - (bits % sizeof(long long)))) / sizeof(long long);
   }

   printf("%d = %d (%d)\n", bits, (int) dataSize, 1 + bits/sizeof (long long));
   /*             ^^^^^                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
}

Answer 7

size_t len_needed(int bits) {
   size_t x=  bits/(sizeof(long long) * 8);
   x = (bits%(sizeof(long long) * 8) ? 1 : 0;

   return x;
}

? : - это просто троичный оператор, который является коротким способом выполнить if / else, который оценивает значение.

Answer 8

Вам не нужен цикл для этого.Если вы делите биты / sizeof (long long), вы должны получить округленный результат.Затем вы можете проверить остаток, выполнив модуль битов% sizeof (long long), и если он ненулевой, вам нужно будет добавить один к вашему результату.