在std::bitset中高效迭代true位的方法是什么？

Question

有没有一种方法可以迭代（可能很大的）std::bitset，并且该迭代是 线性的，即与设置为true的位数成线性关系？我想避免必须检查位集中的每个位置。迭代应连续返回设置为true的每个位的索引。

- Astyanax

Answer 1

标准的比特向量不支持高效迭代真正存在的位 - 运行时间总是O(n)，其中n是总位数，与k无关。然而，还有一些专门的数据结构，如Van Emde Boas树和y-fast tries，它们支持在O(k lg lg n)的时间内迭代位，其中n是位数，k是真存在的位数。

- templatetypedef

Answer 2

要使其线性，您需要一个将索引设置为true的链表/数组/集合。保留这样的辅助索引不是std::bitset所需的性能/存储权衡的一部分，而且考虑到它会给没有您特定要求的人造成不利影响，因此实现中不会提供此功能。您可以考虑自己使用这样的容器来补充您的bitset，或者使用boost的multi-index容器库。

- Tony Delroy

---

我明白。不幸的是，保留一个单独的索引存储不是一个选择。感谢您的见解。 - Astyanax

Answer 3

您可以使用u64累加器和32个条目的表格一次检查最多32位，例如：

u32 kTable[]
{
0x01, 0x03, 0x07, 0x0F ..., 0xFFFFFFFF
};

将32位数据读入到u64累加器中，根据偏移量将其向下移位，并将其与表格中的位进行比较。您可以以二进制方式执行此操作，以使最大比较次数为5。对于不是“线性”的数据，这将会变慢。然后，这就成为了对数时间。

- Michael Dorgan

---

有趣。你能详细介绍一下如何使用这样的表格吗？ - Astyanax

O(N/32)仍然是O(N)，这在总位数上仍然是线性的。 - MSalters

kTable已排序，因此您可以对位进行二分搜索。这使得时间复杂度为log。 - Michael Dorgan

Answer 4

只有两个选项比O(N)更好地处理总位数：

1. 使用某些体系结构中可用的专用位扫描指令，例如x86中的BSF。
2. 有一些O(log2(N))算法可以找到字中设置的最低位。当位集是密集的而不是稀疏的时，这当然不会很好地扩展。我想起了一些模糊的记忆，我在FXT库中找到了源代码。详细信息可以在FXT书籍（pdf）的1.3.2节中找到。

- Bryce Schober

Answer 5

有一种方法可以在接近O(k)的时间内[加上O(n/64)]使用C++20中的标准位操作工具来完成。
对于我来说，O(n/64)不是问题，但如果您设置得非常大且非常稀疏，则可能会成为问题。
这些映射到所有主要平台（x64、ARM等）的CPU指令。

为了使其正常工作，我们必须做出一些假设。

1：位集是与本机寄存器大小相关联的标准大小。 64位是一个很好的起点。 您可以将位集存储在如下所示的数组中。

2：已知设置位数，或已知位集的长度。 您可以向函数添加长度检查，但此代码假定您事先知道设置位数（因为您正在某个附加列表中跟踪它们）。

//Walk through an array of std::bitset<64>
//And return the index of the next set bit.
//No attempt is made to stay within the bounds of the array
//So you need to know how many bits are set in total.
template <bool satbit>
int NextSetBit(const std::bitset<64>* bits, const int previous = -1) {
    //walking through the satisfied bits of a bitset using tzcnt is much faster than testing each single bit
    //esp for bitset that have many 0 bits.
    assert(nullptr != bits);
    assert(previous >= -1);
    //get followup bits
    auto next = previous + 1;
    auto chunk = (next / 64); //starting chunk
    const auto firstmask = uint64_t(-1) << (next % 64); //mask off the previously investigated bits
    const auto getnextchunk = [=](const int chunk) { 
        if constexpr (satbit) { return   bits[chunk].to_ullong(); }
        else                  { return ~(bits[chunk].to_ullong()); }
    };
    auto data = firstmask & getnextchunk(chunk);
    while (0 == data) { 
        data = getnextchunk(++chunk);
    }
    next = std::countr_zero(data);
    assert(bits[chunk].test(next) == satlit);
    return (next + (chunk * 64));
}

代码的调用如下：

const auto length = LengthOf(bits);
auto next = -1;
for (auto i = 0; i < SetBitCount; i++) {
    next = NextSetBit<true>(bits, next);
    assert(next < length);
    doStuff(next);
}

只有在集合非常稀疏的情况下，n/64的额外开销因子才是一个问题。您可以通过从迭代中排除空块，并使用跟踪其中设置位的块的列表来解决此问题。这样的簿记可以很容易地成为O(1)。
因此，您可以避免空块，使代码真正成为O(k)，代价是一些恒定的开销。

由于这样的注册需要跟踪每个块中设置的位数，因此您可以直接使用现有的代码而无需添加边界检查。

- Johan

Answer 6

有时人们会使用运行长度编码来处理这类问题。如果将输入的位集编码为一系列运行长度，则您最终得到的运行次数不会超过设置和清除位之间的转换次数，最多为2*k。此外，在许多应用程序中，转换次数远少于k，因此您不仅可以获得线性最坏情况下的性能，还可以获得出色的平均时间性能。

此外，添加一个数据结构以便您可以高效地搜索“从数组中第n个位置开始的下一个设置位”等内容是很容易的：只需构建一个扫描运行长度即可。

- Michael

Answer 7

遍历整个位集并仅检查值并在为真时存储索引是线性的。但是，您可以通过查找表来加速此过程。请参见以下代码：

http://xiangqi-engine.cvs.sourceforge.net/viewvc/xiangqi-engine/tsito2/src/Utility.cpp?revision=1.5&view=markup

- Edward Strange

---

问题的要点在于扫描整个位集并不一定与设置的位数成线性关系。例如，如果已知位集的位数约为ln N，其中N是集合的大小，则扫描仍将需要O(N)而不是O(ln N)的时间。 - Tony Delroy

Eddie，这不是真实位数的线性。请考虑编辑您的答案或将其删除。 - einpoklum