问题标签 [bitvector]

我想知道 Bitvector32 是否有在 O(1) 时间内运行的位运算符。我目前正在使用大尺寸的 BitArray 并使用按 O（位数组的大小）操作的按位与、或和非。

我在互联网上搜索了这个，但找不到答案。希望这里的人能帮忙！

是否有一些相当快的代码可以帮助我快速搜索大位图（几兆字节）以查找连续的零位或一位的运行？

我所说的“相当快”是指可以利用机器字长并一次比较整个字的东西，而不是进行非常慢的逐位分析（例如使用vector<bool>）。

例如，在卷的位图中搜索可用空间（用于碎片整理等）非常有用。

在考虑这个问题时，我开始怀疑std::copy()和/或std::fill是否专门（我的意思是优化）std::vector<bool>.

这是 C++ 标准所要求的，还是 C++ 标准库供应商常用的方法？

简单来说，不知道是不是下面的代码：

在任何方面都比这更好/不同：

非常严格 - 可以说：std::fill<std::vector<bool>::iterator>()进入内部表示std::vector<bool>并设置它们的整个字节而不是单个位？我认为交std::fill朋友std::vector<bool>对图书馆供应商来说不是一个大问题？

[更新]

std::vector<bool>下一个相关问题：如果还没有专门化，我（或其他任何人：）可以专门化这样的算法吗？这是 C++ 标准允许的吗？我知道这将是不可移植的 - 但仅适用于一个选定的标准 C++ 库？假设我（或其他任何人）找到了接触std::vector<bool>私处的方法。

当前使用运行长度编码对位向量进行编码，当前运行时间为 2log(i)，其中是运行的大小。是否有另一种方法可以将其降低到 log(i)？谢谢。

stl 的位向量和位集容器有什么区别？请解释。据我了解，bitset 是位向量概念的实现，我是对还是错？实现位向量的其他方法是什么？

我正在尝试创建一个由int[].
所以我有以下代码：

我知道也许我应该使用byte[]等，但我想知道为什么这种方式不起作用。
这个想法是我int从一个流中传入并保留低 16 位并将相应的位标记为设置。因此，当我遍历向量时，我会发现缺少数字（由低 16 位表示）。
但我得到错误的结果。所以我相信我的处理是错误的。
有任何想法吗？

更新：
我有一个 32 位整数流。当我阅读它们时，我尝试通过使用低 16 位并设置位向量（发布的代码）来标记缺失的数字。
我还尝试找到第二次读取流的高 16 位丢失。
因此，虽然缺少的数字是： 231719592= ( 1101110011111100001010101000) = ( 3535- 49832) 当我读取流时，我没有得到49832缺少的低位，但是65536

更新2：

我得到：

我对 BitVector32 的行为有点困惑。看测试：

这通过了。即第一位设置为1（根据测试）。但是，如果您运行 ToString 方法，您将得到“BitVector32{00000000000000000000000000000000}”

有什么我想念的吗？

提前致谢！

我正在尝试使用 z3 来消除表达式

这等于

通过此代码：

我想得到如下结果：

然而，结果是：

有人会帮我吗？

众所周知，它std::vector<bool>不满足标准的容器要求，主要是因为打包表示阻止T* x = &v[i]返回指向布尔值的指针。

我的问题是：当reference_proxy 重载address-of以返回pointer_proxy时，这可以补救/缓解吗？operator&

在大多数实现中，指针代理可以包含与 reference_proxy 相同的数据，即指向打包数据的指针和用于隔离块内指向的特定位的掩码。然后，pointer_proxy 的间接生成将产生 reference_proxy。本质上，这两个代理都是“胖”指针，但是与基于磁盘的代理容器相比，它们仍然相当轻量级。

而不是T* x = &v[0]一个人可以这样做auto x = &v[0]，并且使用xlikeif(*x)没有问题。我也希望能够写for(auto b: v) { /* ... */ }

问题：这种多代理方法是否适用于 STL 的算法？还是某些算法真的依赖于x需要成为真实的需求bool*？或者是否有太多连续的用户定义转换需要阻止它工作？在尝试完全完成上述实现草图之前，我想知道任何此类障碍。

更新（基于@HowardHinnant 的回答和关于 comp.std.c++的古老讨论）

您几乎可以模仿内置类型：对于任何给定的类型 T，可以使一对代理（例如 reference_proxy 和 iterator_proxy）相互一致，即 reference_proxy::operator&() 和 iterator_proxy::operator* () 互为逆。

但是，在某些时候需要将代理对象映射回其行为类似于 T* 或 T&。对于迭代器代理，可以重载 operator->() 并访问模板 T 的接口，而无需重新实现所有功能。但是，对于参考代理，您需要重载 operator.()，这在当前的 C++ 中是不允许的（尽管Sebastian Redl 在 BoostCon 2013 上提出了这样的提议）。您可以在引用代理中进行详细的解决方法，例如 .get() 成员，或者在引用中实现所有 T 的接口（这是对 vector::bit_reference 所做的），但这会丢失内置语法或引入没有用于类型转换的内置语义的用户定义的转换（每个参数最多可以有一个用户定义的转换）。

我们可能都知道 C++ 98vector<bool>专门化将布尔值存储为位而不是布尔变量。vector<bool>的元素不可寻址，因为 C++ 没有指针和对位的引用，是否有解决方法，任何明显的陷阱（我似乎没有注意到），甚至尝试这样做是否可行？