Vincent - 7 months ago 94

C++ Question

What is the most optimized way to implement a

`<`

`std::bitset`

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