Bezdepbonusu7Программирование: статьи и ответы
Меню

Вопрос

Самый быстрый способ подсчитать количество установленных битов за интервал

Автор вопроса: Qiang LiОтветов: 2

Мне нужен быстрый способ подсчета количества установленных битов для интервала индекса для битового вектора. Например, при заданном 10000100100011000 и интервале индекса [2, 5] возврат будет 2. Индекс начинается с 0 справа. У меня есть много вопросов, которые нужно выполнить в этом стиле. Подсчет количества битов по отдельности и получение разного - лучший способ, или есть ли какая-либо предварительная обработка, которая может быть сделана для уменьшения сложности?

  • возможный дубликат Best алгоритм подсчета количества установленных битов в 32-битном целом числе? Dave 26.01.2012
  • @ Дэйв: Я хорошо осведомлен об этой проблеме. Как я сказал здесь, мне нужно получить разницу между двумя числами установленных битов. Я спрашиваю, есть ли какой-либо метод предварительной обработки, позволяющий эффективно выполнять множество запросов, или метод различия является лучшим. Qiang Li 26.01.2012
  • Обнулите диапазон [0-1] и [6-31], затем используйте алгоритм подсчета битов. Dave 26.01.2012
  • @Dave: Я использую длинный битовый вектор, а не то, что вы предполагали как 32-битное целое число. Qiang Li 26.01.2012
  • Насколько широк может быть индексный интервал? Но да, вы можете предварительно обработать его за O (n), чтобы получить O (1) запросов - вычислить массив суммы префиксов. Затем запрос преобразуется в вычитание двух элементов из суммы префикса. harold 27.01.2012
  • На какой архитектуре вы работаете (x86 / ARM) и какова наиболее вероятная длина тестируемого битового вектора? Для длинных векторов вы можете читать данные по байтам и использовать таблицу поиска, чтобы получить количество установленных битов в каждом байте. Вы можете замаскировать концы начала / конца не точно на границе байта. BitBank 01.02.2012

bit-manipulation

Ответы

Ответ 1 · рейтинг 1 · TemplateRex

Вот способ реализовать предложение Дэйва, которое также работает для всех целых чисел и std :: bitset. Обнуление дополнения диапазона выполняется смещением вектора вправо и влево. Вы можете передать T через const &, если вы используете очень большие битовые наборы. Вы также можете следить за неявными преобразованиями при передаче 8-битных и 16-битных целых чисел.

// primary template for POD types
template<typename T>
struct num_bits
{
    enum { value = 8 * sizeof(T) };
};

// partial specialization for std::bitset
template<size_t N>
struct num_bits< std::bitset<N> >
{
    enum { value = N };
};

// count all 1-bits in n
template<typename T>
size_t bit_count(T n)
{
    return // your favorite algorithm
}

// count all 1-bits in n in the range [First, Last)
template<typename T>
size_t bit_count(T n, size_t First, size_t Last)
{
    // class template T needs overloaded operator<< and operator>>
    return bit_count((n >> First) << (num_bits<T>::value - Last));
}

// example: count 1-bits in the range [2, 5] == [2, 6)
size_t result = bit_count(n, 2, 6);

Ответ 2 · рейтинг 1 · recursion.ninja

Предполагается, что a - это нижний индекс, а b - это верхний индекс, считая справа налево. Предполагает, что входные данные v нормализованы до размера 64 бит (хотя могут быть изменены для меньших значений).

Data  10000100100011000
Index .......9876543210

Код C:

  uint64_t getSetBitsInRange(uint64_t v, uint32_t a, uint32_t b) {
      // a & b are inclusive indexes
      if( a > b) { return ~0; } //check invariant: 'a' must be lower then 'b'

      uint64_t mask, submask_1, submask_2;
      submask_1   = submask_2 = 0x01;
      submask_1 <<= a;             // set the ath bit from the left
      submask_1 >>= 1;             // make 'a' an inclusive index
      submask_1  |= submask_1 - 1; // fill all bits after ath bit
      submask_2 <<= b;             // set the bth bit from the left
      submask_2  |= submask_2 - 1; // fill all bits after bth bit
      mask = submask_1 ^ submask_2;
      v &= mask;   // 'v' now only has set bits in specified range

      // Now utilize any population count algorithm tuned for 64bits
      // Do some research and benchmarking find the best one for you
      // I choose this one because it is easily scalable to lower sizes
      // Note: that many chipsets have "pop-count" hardware implementations
      // Software 64bit population count algorithm (parallel bit count):

      const uint64_t m[6] = { 0x5555555555555555ULL, 0x3333333333333333ULL,
                              0x0f0f0f0f0f0f0f0fULL, 0x00ff00ff00ff00ffULL,
                              0x0000ffff0000ffffULL, 0x00000000ffffffffULL};
      v = (v & m[0]) + ((v >> 0x01) & m[0]);
      v = (v & m[1]) + ((v >> 0x02) & m[1]);
      v = (v & m[2]) + ((v >> 0x04) & m[2]);
      v = (v & m[3]) + ((v >> 0x08) & m[3]);   //comment out this line & below to make  8bit
      v = (v & m[4]) + ((v >> 0x10) & m[4]);   //comment out this line & below to make 16bit
      v = (v & m[5]) + ((v >> 0x20) & m[5]);   //comment out this line to make 32bit
      return (uint64_t)v;
    }

Перевод вопроса и ответов сообщества Stack Overflow, лицензия CC BY-SA. Оригинал на Stack Overflow.

Похожие материалы