我有一个算法,目前使用两个无符号整数作为位图来存储有关输入的信息;这将最大输入大小限制为 64,因此我想创建一个版本,其中整数被位集或简单的大整数替换。我开始使用 vector
我需要的操作:
- 初始化为全零。
- 左移(乘以二)并设置新的 lsb。
- 添加并设置 msb。
- 比较两个集合,首先找到最小/按字典顺序排列的集合。
当它们被创建时,我知道最大位数,但一开始我只需要 1 位;然后,在每一步中,一组左移,而另一组将添加新的最高位:
{
a <<= 1;
a[0] = x;
b[++msb] = y;
if (a < b) b = a;
}
如果我创建大小为 1 的位集,然后逐渐扩展它们,也许比较会比我立即将长度设置为最大值并且可能有数千个前导零更快?
那么我应该继续使用 vector
使用 vector
std::vector<bool> a(0), b(0);
然后像这样执行上面提到的操作:
{
a.push_back(x);
b.insert(b.begin(), y);
if (a < b) b = a;
}
最佳答案
我认为 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";
}
一些注意事项:
- 该对象是完全动态的,没有机会利用您对最大尺寸的了解。我相信它甚至不使用小对象优化,因此它总是会分配一些动态内存。
- 构造函数有点特殊。第一个参数是位数,第二个参数是它们的整数值。这意味着按照您的要求初始化为单个 true 位,您将使用
dynamic_bitset<>(1, 1)
。遗憾的是没有initializer_list
构造函数,所以你不能只做a = {true}
。也许最清楚的事情是默认构造对象和push_back(true)
单独一行。 -
push_back
影响最高有效位,即左侧的值。这是因为“front”表示元素 0,即最低有效位。 - 左移运算符不会增加对象,因此要将项目附加到前面,您需要:
-
a.push_back(false)
(你推送的值并不重要,因为它很快就会被丢弃)。 -
a <<= 1
-
a[0] = x
如果您想设置新值。
-
-
to_ulong()
仅当对象具有足够少的元素以适合unsigned long
时才有效在您的平台上。请注意,它不是unsigned long long
,因此即使在 64 位系统上它也可能是 32 位。 - 还有一些其他有趣的方法值得一看,例如
any()
,all()
和count()
.
关于c++ - 位集、 bool vector 或简单大整数的整数 vector ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46331998/