Vincent - 1 year ago 170

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

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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.

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**