algorithm - 仅使用 10000 位表示 10000 个布尔值

Question

我想代表 10000 位信息。（每个都可以是 1 或 0）。有什么办法可以做到这一点吗？

维基百科解释了一些 hack来实现这一点。但随后它要求我有一个大至 2^10000 的数字来存储 10000 位。

即使存储大量位，是否也有一些易于处理的方法？

Answer 1

正如 wikipedia 解释的那样，位字段在这里是一个合适的选择。一个可以容纳 10,000 位的位域有 2^10000 个状态。

这样做的一个不错的选择（假设整数是 32/64 位）是位向量，这里有详细的询问和解释：

Programming Pearls，第 2 版中 set 的位向量实现

一般的想法是您使用一个用作位字段的整数数组。

Answer 2

例如，如果您有一堆bool，例如，您可以使bool占用 1 位。在一个结构中，像这样：

结构 A { bool a:1, b:1, c:1, d:1, e:1; };

如果变量数量很大，上述方法将无用。所以改为创建一个大小为 10000/4*8 的整数数组。它将精确地创建 10000 位。现在您可以使用偏移量和 << 或 >> 访问每个位（例如访问第 55 位，使用 floor(55/4*8) 和 >>55%32。您可以到达该位）。

Answer 3

在 C++ 中，您可以非常简单地做到这一点，使用两个标准库容器之一：

std::vector<bool>

标准向量的这种特殊化（几乎）与任何其他向量一样，但将其内容压缩到每个元素一位。除了享受这一事实之外，您还可以将其视为向量：

// Create a vector of 10000 booleans
std::vector<bool> lots_of_bits(10000);
// Set all the odd ones to true
for (int i = 1; i < lots_of_bits.size(); i += 2) {
  lots_of_bits[i] = true;
}
// Add another 100 trues at the end
for (int j = 0; j < 100; ++j) {
  lots_of_bits.push_back(true);
}
// etc.

std::bitset<N>

不伪装成标准容器的“新的、改进的”位向量。特别是，它的大小是固定的，您需要在编译时知道大小。这可能有点限制，但它是一个非常有用的类。就像std::vector<bool>，它实现了[]用于获取和设置各个位的运算符。它还支持按位逻辑运算符&, |, '^' and ~(and, or, xor and not)，以及左右位移，以及其他一些实用程序。

Answer 4

您是否担心访问位数n需要移位n时间？如果是这样，您可以通过使用字符数组将您的 10,000 位分成 10,000 / 8 个桶来解决问题（假设这里是 C 或 C++）。现在，您可以n通过找出该位在 ( n / 8) 中的哪个存储桶以及存储桶中的哪个位置( ) 来访问位号n % 8。然后你只做掩蔽。不需要额外的存储空间（除了最后的填充，如果你没有 32 位的完美倍数，则需要一些额外的位）。