我需要创建一个非常大的位/布尔值数组.我如何在C/C++中做到这一点？

Question

甚至可以创建一个超过100000000个元素的位数组？如果是的话,我该怎么做呢？我知道对于char数组我可以这样做:

char* array;

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

如果我要在char array[100000000]那时声明数组,那么我会得到一个分段错误,因为已经超出了最大数量的元素,这就是我使用的原因malloc.

有什么类似的东西,我可以做一个位数组？

Answer 1

如果您使用的是C++,std::vector<bool>则专门将元素打包到位图中.当然,如果您使用的是C++,则需要停止使用malloc.

Answer 2

您可以尝试查看boost :: dynamic_bitset.然后你可以做类似下面的事情(取自Boost的示例页面):

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

bitset将为每个元素使用一个位,因此您可以在4个字节的空间中存储32个项目,从而大大减少了所需的内存量.

Answer 3

在C和C++中,char是最小的类型.你不能直接声明一个位数组.但是,由于任何基本类型的数组基本上都是由比特组成的,你可以模仿它们,类似这样(代码未经测试):

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