I need to create a very large array of bits/boolean values. How would I do this in C/C++?

Question

Is it even possible to create an array of bits with more than 100000000 elements? If it is, how would I go about doing this? I know that for a char array I can do this:

char* array;

array = (char*)malloc(100000000 * sizeof(char));

If I was to declare the array by char array[100000000] then I would get a segmentation fault, since the maximum number of elements has been exceeded, which is why I use malloc.

Is there something similar I can do for an array of bits?

Answer 1

If you are using C++, std::vector<bool> is specialized to pack elements into a bit map. Of course, if you are using C++, you need to stop using malloc.

Answer 2

You could try looking at boost::dynamic_bitset. Then you could do something like the following (taken from Boost's example page):

boost::dynamic_bitset<> x(100000000); // all 0's by default
x[0] = 1;
x[1] = 1;
x[4] = 1;

The bitset will use a single bit for each element so you can store 32 items in the space of 4 bytes, decreasing the amount of memory required considerably.

Answer 3

In C and C++, char is the smallest type. You can't directly declare an array of bits. However, since an array of any basic type is fundamentally made of bits, you can emulate them, something like this (code untested):

unsigned *array;
array = (unsigned *) malloc(100000000 / sizeof(unsigned) + 1);

/* Retrieves the value in bit i */
#define GET_BIT(array, i) (array[i / sizeof(unsigned)] & (1 << (i % sizeof(unsigned))))

/* Sets bit i to true*/
#define SET_BIT(array, i) (array[i / sizeof(unsigned)] |= (1 << (i % sizeof(unsigned))))

/* Sets bit i to false */
#define CLEAR_BIT(array, i) (array[i / sizeof(unsigned)] &= ~(1 << (i % sizeof(unsigned))))

Answer 4

The segmentation fault you noticed is due to running out of stack space. Of course you can't declare a local variable that is 12.5 MB in size (100 million bits), let alone 100MB in size (100 million bytes) in a thread with a stack of ~ 4 MB. Should work as a global variable, although then you may end up with a 12 or 100 MB executable file -- still not a good idea. Dynamic allocation is definitely the right thing to do for large buffers like that.

Answer 5

If it is allowed to use STL, then I would use std::bitset.

(For 100,000,000 bits, it would use 100000000 / 32 unsigned int underneath, each storing 32 bits.)

std::vector<bool>, already mentioned, is another good solution.

Answer 6

There are a few approaches to creating a bitmap in C++.

If you already know the size of bitmap at compile time, you can use the STL, std::bitset template.

This is how you would do it with bitset std::bitset<100000000> array

Otherwise, if the size of the bitmap changes dynamically during runtime, you can use std::vector<bool> or boost::dynamic_bitset as recommended here http://en.cppreference.com/w/cpp/utility/bitset (See note at the bottom)

Answer 7

Yes but it's going to be a little bit more complicated !

The better way to store bits is to use the bits into the char itself !

So you can store 8 bits in a char !

Which will "only" require 12'500'000 octets !

Here is some documentation about binaries : http://www.somacon.com/p125.php

You should look on google :)

Answer 8

Other solution:

unsigned char * array;
array = (unsigned char *) malloc ( 100000000 / sizeof(unsigned char) + 1);

bool MapBit ( unsigned char arraybit[], DWORD position, bool set)
{
    //work for 0 at 4294967295 bit position
    //calc bit position
    DWORD bytepos = ( position / 8 );
    //
    unsigned char bitpos =  ( position % 8);

    unsigned char bit = 0x01;

    //get bit
    if ( bitpos )
    {
        bit = bit << bitpos;
    }

    if ( set )
    {
        arraybit [ bytepos ] |= bit;
    }
    else
    {
        //get
        if ( arraybit [ bytepos ] & bit )
            return true;
    }

    return false;
}

Answer 9

I'm fond of the bitarray that's in the open source fxt library at http://www.jjj.de/fxt/. It's simple, efficient and contained in a few headers, so it's easy to add to your project. Plus there's many complementary functions to use with the bitarray (see http://www.jjj.de/bitwizardry/bitwizardrypage.html).