A demo problem: Given two std::bitset<N>
s, a
and b
check if any bit is set in both a
and b
.
There are two rather obvious solutions to this problem. This is bad because it creates a new temporary bitset, and copies values all sorts of places just to throw them away.
template <size_t N>
bool any_both_new_temp(const std::bitset<N>& a, const std::bitset<N>& b)
{
return (a & b).any();
}
This solution is bad because it goes one bit at a time, which is less than ideal:
template <size_t N>
bool any_both_bit_by_bit(const std::bitset<N>& a, const std::bitset<N>& b)
{
for (size_t i = 0; i < N; ++i)
if (a[i] && b[i])
return true;
return false;
}
Ideally, I would be able to do something like this, where block_type
is uint32_t
or whatever type the bitset
is storing:
template <size_t N>
bool any_both_by_block(const std::bitset<N>& a, const std::bitset<N>& b)
{
typedef std::bitset<N>::block_type block_type;
for (size_t i = 0; i < a.block_count(); ++i)
if (a.get_block(i) & b.get_block(i))
return true;
return false;
}
Is there an easy way to go about doing this?
I compiled your first example with optimization in g++
and it produced code identical to your third solution. In fact, with a smallish bitset (320 bits) it fully unrolled it. Without calling a function to ensure that the contents of a
and b
were unknown in main
it actually optimized the entire thing away (knowing both were all 0).
Lesson: Write the obvious, readable code and let the compiler deal with it.
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