C ++ schnelle Bitset Shortcirit Bitwise Operations

Question

Ein Demo -Problem: zwei gegeben std::bitset<N>s, a und b Überprüfen Sie, ob in beiden ein Bit festgelegt ist a und b.

Es gibt zwei ziemlich offensichtliche Lösungen für dieses Problem. Das ist schlecht, weil es eine neue temporäre Bitset erzeugt und die Werte alle möglichen Orte kopiert, um sie wegzuwerfen.

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

Diese Lösung ist schlecht, weil sie ein bisschen nach dem anderen geht, was weniger als ideal ist:

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

Idealerweise könnte ich so etwas tun, wo block_type ist uint32_t oder was auch immer type die bitset speichert:

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

Gibt es eine einfache Möglichkeit, dies zu tun?

Answer 1

Ich habe Ihr erstes Beispiel mit Optimierung in kompiliert g++ und es erzeugte Code, der mit Ihrer dritten Lösung identisch ist. Tatsächlich hat es mit einem kleinen Bitset (320 Bit) es vollständig abgerollt. Ohne eine Funktion aufzurufen, um sicherzustellen, dass der Inhalt von a und b waren unbekannt in main Es optimierte tatsächlich das Ganze weg (wissend, dass beide alle 0 waren).

Lektion: Schreiben Sie den offensichtlichen, lesbaren Code und lassen Sie den Compiler damit umgehen.

Answer 2

Sie sagen, dass Ihr erster Ansatz "alle möglichen Orte kopiert, um sie wegzuwerfen". Aber es gibt wirklich nur eine zusätzliche Wertschöpfung (wenn das Ergebnis von operator& wird zurückgegeben zu any_both_new_temp), und es kann durch Verwendung einer Referenz anstelle eines Wertes beseitigt werden:

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

(Aber offensichtlich wird es immer noch eine vorübergehende Erzeugung erzeugen bitset und kopieren a hinein.)