Vincent Vincent - 3 months ago 49
C++ Question

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

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

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.

Comments