4

甚至可以创建一个包含超过 100000000 个元素的位数组吗？如果是，我将如何去做？我知道对于 char 数组，我可以这样做：

char* array;

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

如果那时我要声明数组，char array[100000000]我会遇到分段错误，因为已超过最大元素数，这就是我使用malloc.

我可以为一组位做类似的事情吗？

4

9 回答 9

12

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

于 2010-03-27T18:00:15.417 回答
8

您可以尝试查看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 个项目，从而大大减少了所需的内存量。

于 2010-03-27T18:03:27.423 回答
5

在 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))))
于 2010-03-27T18:00:00.520 回答
4

您注意到的分段错误是由于堆栈空间不足。当然，您不能在堆栈约为 4 MB 的线程中声明大小为 12.5 MB（1 亿位）的局部变量，更不用说大小为 100 MB（1 亿字节）的局部变量了。应该作为一个全局变量工作，尽管这样你最终可能会得到一个 12 或 100 MB 的可执行文件——这仍然不是一个好主意。对于像这样的大缓冲区，动态分配绝对是正确的做法。

于 2010-03-27T18:04:52.380 回答
3

如果允许使用 STL，那么我会使用std::bitset.

（对于 100,000,000 位，它将unsigned int在下面使用 100000000 / 32，每个存储 32 位。）

std::vector<bool>，已经提到，是另一个很好的解决方案。

于 2010-03-27T18:55:23.653 回答
1

有几种方法可以在 C++ 中创建位图。

如果您在编译时已经知道位图的大小，则可以使用 STL、std::bitset模板。

这就是你将如何使用 bitset std::bitset<100000000> array

否则，如果位图的大小在运行时动态变化，您可以使用std::vector<bool>或boost::dynamic_bitset按照此处的建议http://en.cppreference.com/w/cpp/utility/bitset（请参阅底部的注释）

于 2014-04-21T01:20:04.540 回答
0

是的，但它会有点复杂！

存储位的更好方法是将位使用到 char 本身！

所以你可以在一个 char 中存储 8 位！

这将“仅”需要 12'500'000 个八位字节！

这是一些关于二进制文件的文档：http: //www.somacon.com/p125.php

你应该看看谷歌:)

于 2010-03-27T18:00:21.440 回答
0

其他解决方案：

无符号字符 * 数组；
数组 = (unsigned char *) malloc ( 100000000 / sizeof(unsigned char) + 1);

bool MapBit ( unsigned char arraybit[], DWORD position, bool set)
{
    //在 4294967295 位位置为 0 工作
    //计算位位置
    DWORD 字节位置 = ( 位置 / 8 );
    //
    unsigned char bitpos = (位置 % 8);

    无符号字符位 = 0x01；

    //获取位
    如果（位位置）
    {
        位 = 位 << 位位置；
    }

    如果（设置）
    {
        数组位 [ 字节位置 ] |= 位；
    }
    别的
    {
        //得到
        if ( 数组位 [ 字节位置 ] & 位 )
            返回真；
    }

    返回假；
}
于 2010-03-27T18:08:09.370 回答
0

我喜欢位于http://www.jjj.de/fxt/的开源 fxt 库中的 bitarray 。它简单、高效且包含在几个标题中，因此很容易添加到您的项目中。此外，还有许多与 bitarray 一起使用的补充功能（请参阅http://www.jjj.de/bitwizardry/bitwizardrypage.html）。

于 2010-03-27T18:28:19.900 回答