最快的方法來計算間隔的設置位數

Question

我需要一個快速的方法來計算位矢量的索引間隔的設置位數。例如，給定10000100100011000和索引區間[2, 5]，返回值爲2.索引從右側的0開始。我有很多問題需要以這種方式完成。是否要單獨計算比特數並以不同的最佳方式計算，還是需要進行預處理以降低複雜性？

Answer 1

這裏有一種實現Dave的建議，適用於所有整數和std :: bitset的方法。範圍補碼的歸零是通過將矢量向右和向左移動來完成的。如果您使用的是非常大的比特集，則可能需要通過const &傳遞T.傳遞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); 

Answer 2

假定a是較低折射率和b是較高折射率的由右至左計數。假設輸入數據v被歸一化爲64位的大小（雖然對於較小的值可以修改）。

Data 10000100100011000 
Index .......

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