C ++ Fast bitset cortocircuito operaciones bit a bit

Question

Un problema de demostración: dados dos std::bitset<N>s, a y b Compruebe si se establece algún bit en ambos a y b.

Hay dos soluciones bastante obvias a este problema. Esto es malo porque crea un nuevo bitset temporal y copia valora todo tipo de lugares solo para tirarlos.

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

Esta solución es mala porque va un poco a la vez, que es menos que 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;
}

Idealmente, podría hacer algo como esto, donde block_type es uint32_t o cualquier tipo el bitset está almacenando:

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

¿Hay una manera fácil de hacer esto?

Answer 1

Compilé su primer ejemplo con optimización en g++ y produjo un código idéntico a su tercera solución. De hecho, con un bitset pequeño (320 bits) completamente desenrollado. Sin llamar a una función para garantizar que el contenido de a y b eran desconocidos en main En realidad, optimizó todo el asunto (sabiendo que ambos fueron 0).

Lección: Escriba el código obvio y legible y deje que el compilador lo haga.

Answer 2

Usted dice que su primer enfoque "copia los valores de todo tipo de lugares solo para tirarlos". Pero en realidad solo hay una copia de valor adicional (cuando el resultado de operator& se devuelve a any_both_new_temp), y se puede eliminar usando una referencia en lugar de un valor:

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

(Pero obviamente todavía creará un temporal bitset y copiar a en ello.)