How to build N bits variables in C++?

Question

I am dealing with very large list of booleans in C++, around 2^N items of N booleans each. Because memory is critical in such situation, i.e. an exponential growth, I would like to build a N-bits long variable to store each element.

For small N, for example 24, I am just using unsigned long int. It takes 64MB ((2^24)*32/8/1024/1024). But I need to go up to 36. The only option with build-in variable is unsigned long long int, but it takes 512GB ((2^36)*64/8/1024/1024/1024), which is a bit too much. With a 36-bits variable, it would work for me because the size drops to 288GB ((2^36)*36/8/1024/1024/1024), which fits on a node of my supercomputer.

I tried std::bitset, but std::bitset< N > creates a element of at least 8B. So a list of std::bitset< 1 > is much greater than a list of unsigned long int. It is because the std::bitset just change the representation, not the container.

I also tried boost::dynamic_bitset<> from Boost, but the result is even worst (at least 32B!), for the same reason.

I know an option is to write all elements as one chain of booleans, 2473901162496 (2^36*36), then to store then in 38654705664 (2473901162496/64) unsigned long long int, which gives 288GB (38654705664*64/8/1024/1024/1024). Then to access an element is just a game of finding in which elements the 36 bits are stored (can be either one or two). But it is a lot of rewriting of the existing code (3000 lines) because mapping becomes impossible and because adding and deleting items during the execution in some functions will be surely complicated, confusing, challenging, and the result will be most likely not efficient.

How to build a N-bits variable in C++?

Answer 1

How about a struct with 5 chars (and perhaps some fancy operator overloading as needed to keep it compatible to the existing code)? A struct with a long and a char probably won't work because of padding / alignment...

Basically your own mini BitSet optimized for size:

struct Bitset40 {
   unsigned char data[5];
   bool getBit(int index) {
     return (data[index / 8] & (1 << (index % 8))) != 0;
   }
   bool setBit(int index, bool newVal) {
     if (newVal) {
        data[index / 8] |= (1 << (index % 8));
     } else {
        data[index / 8] &= ~(1 << (index % 8));
     }
   }
};

Edit: As geza has also pointed out int he comments, the "trick" here is to get as close as possible to the minimum number of bytes needed (without wasting memory by triggering alignment losses, padding or pointer indirection, see http://www.catb.org/esr/structure-packing/).

Edit 2: If you feel adventurous, you could also try a bit field (and please let us know how much space it actually consumes):

struct Bitset36 {
  unsigned long long data:36;
}

Answer 2

I'm not an expert, but this is what I would "try". Find the bytes for the smallest type your compiler supports (should be char). You can check with sizeof and you should get 1. That means 1 byte, so 8 bits.

So if you wanted a 24 bit type...you would need 3 chars. For 36 you would need 5 char array and you would have 4 bits of wasted padding on the end. This could easily be accounted for.

i.e.

char typeSize[3] = {0}; // should hold 24 bits

Now make a bit mask to access each position of typeSize.

const unsigned char one = 0b0000'0001;
const unsigned char two = 0b0000'0010;
const unsigned char three = 0b0000'0100;
const unsigned char four = 0b0000'1000;
const unsigned char five = 0b0001'0000;
const unsigned char six = 0b0010'0000;
const unsigned char seven = 0b0100'0000;
const unsigned char eight = 0b1000'0000;

Now you can use the bit-wise or to set the values to 1 where needed..

typeSize[1] |= four; 
*typeSize[0] |= (four | five); 

To turn off bits use the & operator..

typeSize[0] &= ~four; 
typeSize[2] &= ~(four| five); 

You can read the position of each bit with the & operator.

typeSize[0] & four

Bear in mind, I don't have a compiler handy to try this out so hopefully this is a useful approach to your problem.

Good luck ;-)

Answer 3

You can use array of unsigned long int and store and retrieve needed bit chains with bitwise operations. This approach excludes space overhead.

Simplified example for unsigned byte array B[] and 12-bit variables V (represented as ushort):

Set V[0]:  
B[0] = V & 0xFF; //low byte 
B[1] = B[1] & 0xF0;  // clear low nibble
B[1] = B[1] | (V >> 8);  //fill low nibble of the second byte with the highest nibble of V