c++ - 比较位集的最快方法(<位集上的运算符)？

Question

实现 < 的最优化方法是什么？ std::bitset 的运算符对应于无符号整数表示的比较(它应该适用于 more than 64 bits 的位集)？

一个简单的实现是:

template<std::size_t N>
bool operator<(const std::bitset<N>& x, const std::bitset<N>& y)
{
    for (int i = N-1; i >= 0; i--) {
        if (x[i] && !y[i]) return false;
        if (!x[i] && y[i]) return true;
    }
    return false;
}

当我说“最优化的方式”时，我正在寻找使用按位运算和元编程技巧(以及类似的东西)的实现。

编辑:我认为我找到了诀窍:用于编译时递归和右位移位的模板元编程，以便将位集与几个无符号长整数进行比较。但不清楚如何做到这一点......

Answer 1

明显的优化是

template<std::size_t N>
bool operator<(const std::bitset<N>& x, const std::bitset<N>& y)
{
    for (int i = N-1; i >= 0; i--) {
        if (x[i] ^ y[i]) return y[i];
    }
    return false;
}

除此之外，不可能使用更多的每次测试位，因为没有符合标准的方法来访问它们。您可以对 x.to_string() < y.to_string() 进行基准测试并希望两者to_string()和字符串比较比按位访问 bitset 更优化，但这是不可能的。