有没有一种方法可以迭代设置为 true 的位数std::bitset是线性的（可能很大） ？我想避免检查位集中的每个位置。迭代应连续返回设置为 true 的每个位的索引。
10985 次
6 回答
18
标准位向量不支持对真实位的有效迭代 - 运行时间始终为 O(n)，其中 n 是总位数，与 k 无关。但是，有专门的数据结构，如van Emde Boas 树和y-fast Trys，它们支持在 O(k lg lg n) 时间内对比特进行迭代，其中 n 是比特数，k 是真实比特数。
于 2011-01-17T01:14:17.660 回答
4
为了使其成为线性，您需要一个链表/数组/一组索引设置为 true。保持这样的二级索引不是 std::bitset 要求的性能/存储权衡的一部分，并且如果没有您的特定要求，它会使每个人都处于不利地位，因此实现无法提供这一点。你可以考虑自己用这样的容器来补充你的 bitset，或者使用 boost 的多索引容器库。
于 2011-01-17T01:01:36.093 回答
1
您可以使用 u64 累加器和 32 条目表一次最多检查 32 位，例如
u32 kTable[]
{
0x01, 0x03, 0x07, 0x0F ..., 0xFFFFFFFF
};
只需将 32 位读入 u64 累加器并根据偏移量将其向下移动，然后对照表检查您的位。您可以以二进制方式执行此操作，以使比较次数最多为 5。对于时尚非“线性”的数据，这将变慢。然后这成为日志时间。
于 2011-01-17T01:05:06.613 回答
1
只有两个选项在总位数上比 O(N) 好得多：
- 使用某些架构中可用的特殊位扫描指令，例如x86 中的 BSF。
- 有 O(log2(N)) 算法可以找到一个字中设置的最低位。当位集密集而不是稀疏时，这当然不能很好地扩展。恢复我的一些模糊记忆，我在FXT 库中找到了源详细信息可以在FXT 书籍 (pdf)中找到，在第 1.3.2 节中。
于 2012-05-22T22:19:06.350 回答
-1
循环遍历整个位集并简单地检查值并存储索引，如果为真，则为线性。您可以使用查找表加快速度。请参阅此代码：
于 2011-01-17T01:02:17.877 回答