간격의 설정 비트 수를 계산하는 가장 빠른 방법

Question

비트 벡터의 인덱스 간격에 대해 설정된 비트 수를 계산하는 빠른 방법이 필요합니다. 예를 들어, 10000100100011000 및 인덱스 간격 [2, 5]을 지정하면 반환 값은 2입니다. 인덱스는 오른쪽에서부터 0부터 시작합니다. 이 방식으로 많은 쿼리를 수행 할 수 있습니다. 비트 수를 개별적으로 계산하고 다른 방법을 얻거나 복잡성을 줄이기 위해 수행 할 수있는 사전 처리가있는 경우?

Answer 1

다음은 모든 정수와 std :: bitset에도 적용되는 Dave의 제안을 구현하는 방법입니다. 범위 보완의 제로화는 벡터를 오른쪽과 왼쪽으로 이동하여 수행됩니다. 매우 큰 비트 집합을 사용하는 경우 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; 
    }