Menu
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...
804
bitset lacks iterators outright and that often makes people wanting to use it to avoid dealing with bitwise logic to use operator[] to check each bit individually in a sequential loop that just wants to find out which bits are set. That too is not nearly as efficient as what a for_each method implementation could do.
template< std::size_t N > class bitset; The class template bitset represents a fixed-size sequence of N bits. Bitsets can be manipulated by standard logic operators and converted to and from strings and integers.
Bitset represents a fixed-size sequence of N bits and stores values either 0 or 1. Zero means value is false or bit is unset and one means value is true or bit is set. Bitset class emulates space efficient array of boolean values, where each element occupies only one bit.
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.
142
If you are willing to adopt the solution if STL bitset changes you may use
template<int n>
bool compare(bitset<n>& l, bitset<n>& r){
if(n > 64){
typedef array<long, (n/64)> AsArray;
return *reinterpret_cast<AsArray*>(&l)
< *reinterpret_cast<AsArray*>(&r);
}//else
return l.to_ulong() < r.to_ulong();
}
the compiler throws the irrelevant branch of the if away
36
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
