Allocate n bytes for x bits

First, this can be a general algorithm for any language, but I'm learning C and if there is some C specific features, I'd like to know!

I'm writing a function that will allocate enough memory for a given number of bits; into a long long * variable. The number of bits cannot be < 1. I tested the algorithm :

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);
}

It looks ok... but ugly :) Any way to 开发者_开发问答have a more elegant way to achieve this? Thank you!

Assuming you want to initialize your bit-field to zero, calloc() might be preferable to malloc(); you probably also should use an unsigned type to avoid signed shifts when twiddling bits.

#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);

The !! is a somewhat hackish way to convert non-zero values to 1, which is common in C and used here to allocate an additional block if the number of bits is not divisible by BITS_PER_BLOCK.

You could also get the required number of blocks (as - among others - Lars pointed out in the comments to another answer) via

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

I find the former version more readable, but as the latter is also quite common - it's a special case of a more general rounding algorithm using integer arithmetics - a C programmer should be comfortable with either choice.

Unless I'm missing something, I think it would just be:

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)

So assuming a long long size of 8 bytes, a value of 1-64 would return 8, 65-128 would return 16, etc.

If you want n bits, then the correct expression to calculate the amount of long long is:

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

You shouldn't need a loop for this. If you do a division of bits / sizeof(long long), you should get a rounded-down result. You can then check the remainder by doing a modulus of bits % sizeof(long long), and if it is non-zero, you will need to add one to your result.

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

   return x;
}

The ? : thing is just the ternary operator, which is a short way to do an if/else that evaluates to a value.

This is your code with just a new value added to the 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));
   /*             ^^^^^                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
}

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

Now, the number of bits in a long long is log2(ULLONG_MAX+1), not sizeof(long long). So you should revisit your calculation.

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

or if you know the sizes.

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