Мне нужен быстрый способ подсчета количества установленных битов для интервала индекса для битового вектора. Например, при заданном 10000100100011000
и интервале индекса [2, 5]
возврат будет 2. Индекс начинается с 0 справа. У меня есть много вопросов, которые нужно выполнить в этом стиле. Подсчет количества битов по отдельности и получение разного - лучший способ, или есть ли какая-либо предварительная обработка, которая может быть сделана для уменьшения сложности?
самый быстрый способ подсчитать количество установленных битов за интервал
comment
возможный дубликат Best алгоритм подсчета количества установленных битов в 32-битном целом числе?
- person Dave   schedule 26.01.2012
comment
@ Дэйв: Я хорошо осведомлен об этой проблеме. Как я сказал здесь, мне нужно получить разницу между двумя числами установленных битов. Я спрашиваю, есть ли какой-либо метод предварительной обработки, позволяющий эффективно выполнять множество запросов, или метод различия является лучшим.
- person Qiang Li   schedule 26.01.2012
comment
Обнулите диапазон [0-1] и [6-31], затем используйте алгоритм подсчета битов.
- person Dave   schedule 26.01.2012
comment
@Dave: Я использую длинный битовый вектор, а не то, что вы предполагали как 32-битное целое число.
- person Qiang Li   schedule 26.01.2012
comment
Насколько широк может быть индексный интервал? Но да, вы можете предварительно обработать его за O (n), чтобы получить O (1) запросов - вычислить массив суммы префиксов. Затем запрос преобразуется в вычитание двух элементов из суммы префикса.
- person harold   schedule 27.01.2012
comment
На какой архитектуре вы работаете (x86 / ARM) и какова наиболее вероятная длина тестируемого битового вектора? Для длинных векторов вы можете читать данные по байтам и использовать таблицу поиска, чтобы получить количество установленных битов в каждом байте. Вы можете замаскировать концы начала / конца не точно на границе байта.
- person BitBank   schedule 01.02.2012
Ответы (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);
person
TemplateRex
schedule
22.02.2012
Предполагается, что 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;
}
person
recursion.ninja
schedule
02.02.2013