C ++高速ビットセット短絡ビットワイズ操作

Question

デモの問題：2つ与えられます std::bitset<N>S、 a と b 両方にビットが設定されているかどうかを確認してください a と b.

この問題には2つのかなり明白な解決策があります。これは、新しい一時的なビットセットを作成し、それらを捨てるためだけにあらゆる種類の場所をコピーするため、これは悪いことです。

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

このソリューションは、一度に1つずつ行くので悪いです。

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;
}

理想的には、私はこのようなことをすることができるでしょう、どこで block_type は uint32_t またはタイプのどんなタイプ 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;
}

これを行う簡単な方法はありますか？

Answer 1

私はあなたの最初の例を最適化してまとめました g++ また、3番目のソリューションと同じコードを作成しました。実際、小さなビットセット（320ビット）を使用すると、完全に展開されました。関数を呼び出すことなく、 a と b で不明でした main それは実際にすべてを最適化しました（両方がすべて0であることを知っています）。

レッスン：明白で読みやすいコードを書いて、コンパイラに対処させます。

Answer 2

あなたは、あなたの最初のアプローチが「それらを捨てるためにあらゆる種類の場所をコピーする」と言います。しかし、実際には1つの余分な値コピーだけがあります（の結果が operator& に返されます any_both_new_temp）、および値の代わりに参照を使用して排除できます。

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();
}

（しかし、明らかにそれはまだ一時的なものを作成します bitset コピー a それに。）