c++ - 获得 C++ std::bitset 的最低设置位的最快方法是什么？

Question

我注意到 std::bitset没有用于返回或弹出位集的最低设置位的功能(也没有与此相关的最高设置位)。完成此任务的最快方法是什么，特别是对于不能保证一定长度的 std::bitset 对象？我查看了 g++ 编译器扩展和 C++20 numerics图书馆，但没有找到与我的问题相关的任何内容。

要考虑的两种明显方法是遍历 bitset 的长度并使用 operator[] 或使用 operator>> 逐渐移动 bitset 直到第一个集合找到位。

Answer 1

我将像大多数现代实现一样使用尾随零，以便轻松处理没有设置位的情况。要利用硬件计数尾随零指令，我们可以使用 to_ullong()，但要使其正常工作，我们需要屏蔽该值以使其适合 unsigned long long

#include <bitset>
#include <bit>
#include <climits>

template<size_t N>
size_t count_trailingzero(std::bitset<N> b)
{
    if (b.none())
        return N;                   // The whole bitset was zero

    const decltype(b) mask(-1ULL);  // Mask to get the lowest unsigned long long
    size_t tz = 0;                  // The number of trailing zero bits
    const int width = sizeof(unsigned long long)*CHAR_BIT;
    do {
        auto lsw = (b & mask).to_ullong();  // The least significant word
        auto lsb = std::countr_zero(lsw);   // Position of the least significant bit

        if (lsb < width)                    // Found the first set bit from right
            return tz + lsb;
        
        // A set bit was not found because the lsw is all zero
        // so we'll increase the number of trailing zero bits
        tz += width;

        // Shift the bitset to get the next higher significant word
        b >>= width;
    } while (b.any());

    return tz;
}

Demo on Godbolt

这样就不需要对单个位进行循环，并且可以使用硬件加速。但它仍然不是最有效的方法，因为整个位集的每次迭代仍然需要屏蔽掉。这就是为什么 std::bitset 通常不是对位进行操作的好工具，我在实践中总是避免使用它们。为位操作包装一个数组的类在性能和灵 active 上会好得多