bit-manipulation - 计算一个间隔的设置位数的最快方法

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