Fastest way to compare bitsets (< operator on bitsets)?

Question

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) ?

A trivial implementation would be:

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).

EDIT: 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...

Answer 1

The obvious optimization would be

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;
}

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.