C++ Fast Bitset Short-Circuit Bitwise Operations

Question

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?

Answer 1

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.

Answer 2

You say that your first approach "copies values all sorts of places just to throw them away." But there's really only one extra value-copy (when the result of operator& is returned to any_both_new_temp), and it can be eliminated by using a reference instead of a value:

template <size_t N>
bool any_both_new_temp(const std::bitset<N>& a, const std::bitset<N>& b)
{
    std::bitset<N> tmp = a;
    tmp &= b;
    return tmp.any();
}

(But obviously it will still create a temporary bitset and copy a into it.)