我需要一种快速的方法来计算位向量的索引间隔的设置位数。例如,给定 10000100100011000
和索引区间 [2, 5]
,返回值为 2。索引从右边的 0 开始。我有很多疑问要以这种方式完成。分别计算位数并获得不同的最佳方法,或者是否可以进行任何预处理以降低复杂性?
最佳答案
这是一种实现 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);
关于bit-manipulation - 计算一个间隔的设置位数的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9022647/