最快的比较位集路（小于运营商对位集）？ [英] Fastest way to compare bitsets (< operator on bitsets)?

问题描述

什么是最优化的方式来实现＆LT; 运营商的std :: bitset的相应的比较再presentation无符号整数（它应该为超过64位位集）？

What is the most optimized way to implement a < operator for std::bitset corresponding to the comparison of the unsigned integer representation (it should work for bitsets of 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;
}

当我说最优化的方式：我正在寻找使用位运算和元编程技巧，实现（之类的东西）。

When I say "most optimized way" I am looking for implementations using bitwise operations and metaprogramming tricks (and things like that).

编辑：我想我已经找到了诀窍：模板元编程进行编译时递归和右bitshift以比较位集几无符号long long整数。但是，如何做到这一点没有明确的想法...

I think that I've found the trick: template metaprogramming for compile-time recursion and right bitshift in order to compare bitsets as several unsigned long long integers. But no clear idea of how to do that...

推荐答案

最明显的优化是

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（）＆LT; y.to_string（）和希望为 to_string（）和字符串比较进行优化比按位访问更好位集，但是这是一个长镜头。

Other than that, it should be quite impossible to use a more bits-per-test as there is no standard-conforming way to access them. You could benchmark x.to_string() < y.to_string() and hope for both to_string() and string comparison to be optimized better than bitwise access to a bitset, but that's a long shot.

这篇关于最快的比较位集路（小于运营商对位集）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！