C ++ bitwise bitwise bitwise operations

Question

Demonstration task: if two std::bitset<N> s, a and b check if any bit is set in either a or b .

There are two fairly obvious solutions to this problem. This is bad because it creates a new temporary bitset and copies the values ​​to all kinds 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 could do something like this, where block_type is uint32_t or any type that stores bitset :

 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 do this?

Answer 1

I put together your first g++ optimization example and created code identical to your third solution. In fact, with a small bit (320 bits), he fully deployed it. Without calling the function so that the contents of a and b were unknown in main , it actually optimized the whole thing (knowing that both were all 0).

Lesson: write obvious, readable code and let the compiler deal with it.

Answer 2

You say that your first approach is "copying values ​​to all kinds of places just to throw them away." But in reality there is only one additional copy of the value (when the result of operator& returns to any_both_new_temp ), and it can be eliminated by using the link instead of the 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.)