Быстрые битовые операции C ++ с быстрым битрейтом - PullRequest
Новая
       25

Быстрые битовые операции C ++ с быстрым битрейтом

8 голосов
/ 02 декабря 2011

Демонстрационная проблема: учитывая две std::bitset<N> s, a и b, проверьте, установлен ли какой-либо бит в a и b.

Есть два довольно очевидных решения этой проблемы. Это плохо, потому что он создает новый временный набор битов и копирует значения во все виды мест, просто чтобы выбросить их. 

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

Это решение плохое, потому что оно идет по одному разу, что не идеально: 

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

Есть ли простой способ сделать это?

Ответы [ 2 ]

6 голосов
/ 02 декабря 2011

Я скомпилировал ваш первый пример с оптимизацией в g++, и он дал код, идентичный вашему третьему решению.Фактически, с небольшим битрейтом (320 бит) он полностью развернул его.Не вызывая функцию, гарантирующую, что содержимое a и b было неизвестно в main, она фактически оптимизировала всю вещь (зная, что все они были 0).

Урок: Напишите очевидное,читаемый код и пусть компилятор справится с ним.

0 голосов
/ 02 декабря 2011

Вы говорите, что ваш первый подход "копирует значения во всевозможные места, чтобы просто выбросить их". Но на самом деле есть только одна дополнительная копия значения (когда результат 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.)

...