计数位设置到 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;
}

我知道 bit twiddling hacks for 64 bit types但对于 32 位类型，似乎没有快速的方法来执行此操作。

是否有更好的(更少的操作/最少的分支)- 或者甚至只是我可以尝试的替代方案，最好是有源代码？

我知道(通过阅读类似的帖子)通常不推荐此类优化，但我的项目侧重于比较“优化” 的性能差异 - 以及它们是否提高了性能。

---

从那以后，我根据建议的方法和上面的方法(测试了 4,000,000 次)运行了一系列性能基准测试，并得到了以下结果:

平均 popcto_test1 ns=133
avg popcto_test2//测试失败
平均 popcto_test3 ns=28
平均 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(修改后的 Peter Wegner 方法)

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

感谢大家的建议，我决定将我遇到的所有方法进行比较，因为我找不到任何类似的测试。

注意显示的人口计数是针对 argv[1] 的索引，而不是 argv[1] 的人口计数 - 8 个 32 位数组组成 256 位。 The code used to produce these results can be seen here.

在我的 Ryzen 1700 上，就我的使用而言，最快的人口计数(通常)是 Software Optimization Guide for AMD64 Processors 第 180 页上的那个.对于更大的人口数量，这(通常)也是如此。

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 方法是最快的，紧随其后的是 wegner 方法。 AMD64 方法是第二慢的(仅次于按位)，我相信这是由于与所有其他方法相比占用/寄存器使用增加。