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

Question

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

Answer 1

Предполагается, что 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;  
    }

Answer 2

Вот способ реализовать предложение Дейва, которое работает и для всех целых чисел, и для 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);