比较bitsets的最快方法(<bitset上的运算符)？

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()和字符串比较优化比按位访问a更好bitset,但这是一个很长的镜头.

Answer 2

如果您愿意在 STL 位集更改时采用该解决方案，您可以使用

template<int n>
bool compare(bitset<n>& l, bitset<n>& r){
  if(n > 64){
  typedef array<long, (n/64)> AsArray;
  return *reinterpret_cast<AsArray*>(&l)
       < *reinterpret_cast<AsArray*>(&r);
    }//else
  return l.to_ulong() < r.to_ulong();
}

编译器将 if 的无关分支扔掉