在C++中的二进制位数组

Question

在解 Project Euler 问题时，我经常需要处理大的（>10**7）位数组。

我的通常解决方案有：

bool* sieve = new bool[N];

bool sieve[N];

当 N = 1,000,000 时，我的程序使用了 1 兆字节 (8 * 1,000,000 位)。

在 C++ 中，是否有比 bool 更高效的存储位数组的方法？

- Seth

---

我使用向量实现了埃拉托斯特尼筛法算法。它可以容纳那么多数字。 - Vaibhav

可能是C/C++高效位数组的重复问题。 - Ciro Santilli OurBigBook.com

Answer 1

如果 N 是一个常量，使用 std::bitset，否则使用 std::vector<bool>，就像其他人提到的一样（但不要忘记阅读 Herb Sutter 的这篇优秀文章）。

bitset 是一种特殊的容器类，专门用于存储位（元素只有两个可能值：0 或 1，true 或 false，...）。

该类非常类似于普通数组，但它优化了空间分配：每个元素仅占用一个位（比 C++ 中最小的基本类型 char 小八倍）。

编辑：

Herb Sutter（在那篇文章中）提到

std::vector < bool > 之所以不符合规范是因为它在幕后使用技巧来优化空间：它将 bools 装入单独的位 (例如 chars) 中以进行存储，而不是为每个 bool 存储一个完整的 char 或 int（在具有 8 位字符的平台上至少需要 8 倍的空间）。

std::vector < bool > 强制 所有用户使用特定的优化，将其奉为标准。这不是一个好主意；不同的用户具有不同的需求，现在所有 vector 的用户必须支付性能代价，即使他们不想或不需要节省空间。

编辑 2：

如果你使用了 Boost，你可以使用boost::dynamic_bitset（如果 N 在运行时已知）。

- Prasoon Saurav

---

很遗憾，到2021年11月24日为止，Sutter文章的链接已经失效。 - Gergely Máté

@GergelyMáté，它今天可用（2023年01月05日）。 - vonbrand

Answer 2

无论好坏，std::vector<bool> 将使用位(bit)而不是布尔值(bool)，以节省空间。因此，应该一开始就像使用 std::vector 一样使用它。

如果 N 是一个常量，则可以使用 std::bitset。

- GManNickG

Answer 3

您可以查阅 std::bitset 和 std::vector<bool>。后者通常不被推荐使用，因为尽管名字中有“vector”，但它实际上并不像任何其他类型的对象的向量，并且事实上不符合容器的要求。尽管如此，它仍然可以非常有用。

另一方面，没有什么可以（至少是可靠地）将 100 万个 bool 值存储在少于 100 万位中。这根本无法确定。如果您的位集包含某种程度的冗余，则有各种压缩方案可能会有效（例如，LZ*，Huffman，算术），但是如果没有对内容的了解，则无法确定它们是否有效。但是，这些方案通常仅将每个 bool/bit 存储在一个存储位上（加上一些开销以进行簿记 - 但这通常是一个常数，最多是几个字节到几十个字节）。

- Jerry Coffin

Answer 4

'bool'类型并不仅使用1位进行存储。从您对大小的评论来看，每个bool似乎使用了整个字节。

一种类似C的处理方式是：

uint8_t sieve[N/8]; //array of N/8 bytes

然后将字节逻辑或在一起，以获取所有位：

sieve[0] = 0x01 | 0x02; //this would turn on the first two bits

在这个例子中，0x01和0x02是代表字节的十六进制数。

- whooops

---

点赞，好主意，可能是，它是N/8+1，它是位压缩数组。 - Manohar Reddy Poreddy

Answer 5

'bool'类型并不仅使用1位进行存储。从您对大小的评论来看，每个bool似乎使用了整整1个字节。

C语言的一种方法是：

uint8_t sieve[N/8]; //array of N/8 bytes

数组元素是：

result = sieve[index / 8] || (1 << (index % 8)); 

或者

result = sieve[index >> 3] || (1 << (index & 7));

在数组中设置1：

sieve[index >> 3] |= 1 << (index & 7);

- Vladimir

Answer 6

你可能会对尝试BITSCAN库感兴趣，作为一种替代方案。最近，已经提出了一种针对稀疏性的扩展，我不确定这是否符合你的情况，但这个库可能会有所帮助。

- chesslover

Answer 7

你可以使用字节数组并进行索引。索引n将位于字节索引 n/8，位# n%8。（如果由于某些原因 std::bitset 不可用）。

- driis

Answer 8

如果 N 在编译时已知，使用 std::bitset，否则使用 boost::dynamic_bitset。

- Eugen Constantin Dinca