2

我有一个算法，我目前使用两个无符号整数作为位图来存储有关输入的信息；这将最大输入大小限制为 64，因此我想创建一个版本，其中整数被位集或简单的大整数替换。我开始使用vector<bool> 写一些东西，但是环顾四周，我看到很多答案告诉我要避免使用vector<bool>。

我需要的操作：

  • 初始化为全零。
  • 左移（乘以 2）并设置新的 lsb。
  • 添加并设置 msb。
  • 比较两组以首先找到最小/字典顺序。

创建它们时，我知道最大位数，但起初我只需要 1 位；然后，在每一步，一组左移，而另一组将添加一个新的最高位： 

{
    a <<= 1;
    a[0] = x;
    b[++msb] = y;
    if (a < b) b = a;
}

如果我创建大小为 1 的位集，然后逐渐扩展它们，也许比较会比我立即将长度设置为最大值并可能有数千个前导零更快？

那么我应该继续使用 vector<bool> 还是使用 std::bitset （不幸的是它是固定大小的）或者编写一个简单的 biginteger 实现，该实现能够使用无符号整数向量完成上述操作？

使用 vector<bool> 您可以初始化长度为零的向量： 

std::vector<bool> a(0), b(0);

然后像这样执行上面提到的操作： 

{
    a.push_back(x);
    b.insert(b.begin(), y);
    if (a < b) b = a;
}
4

2 回答 2

4

我想boost::dynamic_bitset这就是你所追求的。

这是一个涵盖您的要求的示例：

#include <iostream>
#include <boost/dynamic_bitset.hpp>
int main() {
    boost::dynamic_bitset<> a(3, 2); // a = 010
    a[0] = true;                     // a = 011
    a.push_back(true);               // a = 1011
    boost::dynamic_bitset<> b = a;   // b = 1011
    a <<= 1;                         // a = 0110
    bool aless = a < b;              // true
    unsigned long al = a.to_ulong(); // al = 6
    std::cout << "a=" << a << ", al=" << a.to_ulong() << "\n"
              << "b=" << b << ", bl=" << b.to_ulong() << "\n"
              << "a<b=" << (a<b) << "\n";
}

几点注意事项：

  • 该对象是完全动态的，没有机会利用您对最大尺寸的了解。我相信它甚至不使用小对象优化，所以它总是会分配一些动态内存。
  • 构造函数有点奇特。第一个参数是位数，第二个参数是它们的整数值。这意味着按照您的要求初始化为一个真实位，您将使用dynamic_bitset<>(1, 1). 可悲的是没有initializer_list构造函数，所以你不能只做a = {true}. 也许最清楚的事情是默认构造对象并push_back(true)在单独的行上。
  • push_back影响最高有效位，即左侧的值。那是因为“前”表示元素 0，它是最低有效位。
  • 左移运算符不会增大对象，因此要将项目附加到前面，您需要：
    1. a.push_back(false)（您推送的值无关紧要，因为它会立即被丢弃）。
    2. a <<= 1
    3. a[0] = x如果要设置新值。
  • to_ulong()仅当对象具有足够少的元素以适合unsigned long您的平台时才会起作用。请注意，它不是unsigned long long，因此即使在 64 位系统上，它也可能是 32 位。
  • 还有一些其他有趣的方法值得一看，例如any()，all()和count()。
于 2017-09-20T21:50:22.320 回答
0

您描述的操作（将隐式解释省略为整数）实际上是由deque有效提供的操作。如果您可以容忍内存开销，则可以使用std::deque<bool>(std::list<bool>也可以，但开销会更高)。

如果开销太大，你可以从

struct Bits {
  std::deque<unsigned> deq;
  int ms_free,ls_free;   // unused bits in the two end words
};

并编写方法以在任一端推送位（对于右端，您将deq.push_back()iflsb_free==0并存储到 deq.back()else 中）。比较将使用deq.size()并ms_free+ls_free知道如何对齐两个序列。

于 2017-09-23T23:33:09.873 回答