简单大整数的位集、bool 向量或 int 向量

Question

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

我需要的操作：

初始化为全零。
左移（乘以二）并设置新的 lsb。
添加并设置 msb。
比较两组，先找到smallest/lexicographically。

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

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

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

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

使用 vector 可以初始化零长度的向量：

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

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

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

Answer 1

我认为 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 影响最高有效位，即左边的值。那是因为"front"表示元素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()。

Answer 2

您描述的操作（忽略作为整数的隐式解释）实际上是由 deque. If you can tolerate the memory overhead, you could use std::deque<bool> 有效提供的操作（std::list<bool> 也可以，但会产生更高的开销）。

如果开销太大，你可以从

开始

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

并编写方法将位压入任一端（对于右端，如果 lsb_free==0 则 deq.push_back() 并将 存储到 deq.back() 除此以外）。比较将使用 deq.size() 和 ms_free+ls_free 来了解如何对齐两个序列。

简单大整数的位集、bool 向量或 int 向量

Bitset, vector of bool or vector of ints for simple big integer

c++

vector

biginteger

bitset

std-bitset