Количество битов, установленных в заданную позицию для 32-битного типа

Question

Я работаю с алгоритмом, который выполняет многократное добавление попкота / сбоку до заданного индекса для 32-битного типа.Я пытаюсь свести к минимуму операции, необходимые для выполнения того, что я в настоящее время реализовал, следующим образом:

int popcto_test1(unsigned int bitmap[], int idx){
int i = 0,      // index
    count = 0;  // number of set bits
do {
    // Each node contains 8 bitmaps
    if(bitmap[i/32] & 1 << (i & 31)){
        ++count;
    }
    ++i;
} while (i < idx);

return count;
}

Мне известны хиты с твилами для 64-битных типов , но, похоже, нетбыть быстрым способом сделать это для 32-битных типов.

Есть ли лучший вариант (меньше операций / минимальное ветвление) - или даже просто альтернатива, которую я могу попробовать, в идеале с источником?

Мне известно (из прочтения похожих постов), что такие оптимизации обычно не рекомендуются, но мой проект направлен на сравнение различий в производительности 'оптимизаций * - и того, улучшают ли они производительность или нет.

---

С тех пор я провел ряд тестов производительности, основанных на предложенных методах и том, что у меня было выше (протестировано 4 000 000 раз), и получил следующие результаты:

avg popcto_test1 ns= 133
avg popcto_test2 // тест не пройден
avg popcto_test3 ns = 28
avg popcto_test4 ns = 74

где функции теста были следующими:
Неудачный тест2:

int popcto_test2(unsigned int bitmap[], int idx){
int i = 0,      // index
    count = 0;  // number of set bits
do {
    // Each node contains 8 bitmaps
    count += (bitmap[i/32] & (1 << (i & 31)));
    ++i;
} while (i < idx);

return count;
}

popcto_test3 ns = 28
Одна (возможно) интересная особенность этого примечания состоит в том, что, хотя это самый быстрый уровень оптимизации 2или используются 3 (-O2 / -O3) неверный результат.

int popcto_test3(unsigned int bitmap[], int idx){
int i = 0,      // index
    count = 0,  // number of set bits
    map = idx/32;
while (i < map){
    // Each node contains 8 bitmaps
    count += __builtin_popcount(bitmap[i]);
    ++i;
}

count += __builtin_popcount(bitmap[map] & ((1<<idx)-1));
return count;
}

avg popcto_test4 ns = 74 (модифицированный метод Питера Вегнера)

int popcto_test4(unsigned int bitmap[], int idx){
int i = 0,      // index
    j = 0,
    count = 0,  // number of set bits
    map = idx/32;
unsigned int temp = 0;

while (i < map){
    temp = bitmap[i];
    j = 0;
    while(temp){
        temp &= temp - 1;
        ++j;
    }
    count += j;
    ++i;
}
temp = bitmap[i] & ((1<<idx)-1);
j = 0;
while(temp){
    temp &= temp - 1;
    ++j;
}
return count + j;
}

Answer 1

Спасибо всем за предложения, я решил собрать все методы, которые мне встретились, потому что я не смог найти ни одного подобного теста.

NB.показанное количество заполнений относится к индексам до argv[1], а не к числовому значению argv[1] - 8x 32-битные массивы составляют 256 бит. Код, используемый для получения этих результатов, можно увидеть здесь.

На моем Ryzen 1700, для моего использования, самым быстрым подсчетом населения был (часто) тот, который на странице 180 Руководство по оптимизации программного обеспечения для процессоров AMD64 .Это (часто) остается верным и для большего количества населения.

unsigned int population_count(int temp){
    // Software Optimization Guide for AMD64 Processors - Page 180
    temp = temp - ((temp >> 1) & 0x55555555);
    temp = (temp & 0x33333333) + ((temp >> 2) & 0x33333333);
    return (((temp + (temp >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
}

У меня нет параллельного сравнения для этого, но если вы используете CUDA;внутренний метод __popc является самым быстрым, вскоре за ним следует метод Вегнера.Метод AMD64 является вторым самым медленным (после только побитового), я полагаю, что это происходит из-за увеличения занятости / использования регистра по сравнению со всеми другими методами.