最快的计算位数方法

Question

最快的计算位数方法

9

可能是重复问题：
如何计算32位整数中设置位的数量？

给定一个无符号字符类型的值，计算其中的总位数。什么是最快的方法？我编写了三个函数，哪个是最好的方法，并且有人能想出更快的方法吗？（我只想要非常快的方法）

const int tbl[] =
{
#define B2(n)   n, n+1, n+1, n+2
#define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
    B6(0), B6(1), B6(1), B6(2)
};

char naivecount (unsigned char val)
{
    char cnt = 0;
    while (val)
    {
        cnt += (val & 1);
        val = val >> 1;
    }
    return cnt;
}

inline tableLookUp(int val)
{
    assert(val >= 0 && val <= 255);
    return tbl[val];
}

int asmCount(int val)
{
    int res = 0;
    asm volatile("xor %0, %0\n\t"
            "begin:\n\t"
            "cmp $0x0, %1\n\t"
            "jle end\n\t"
            "movl %1, %%ecx\n\t"
            "and $0x1, %%ecx\n\t"
            "addl %%ecx, %0\n\t"
            "shrl %1\n\t"
            "jmp begin\n\t"
            "end:"
            : "=r"(res)
            : "r" (val));
    return res;
}

编辑：

我已经测试了所有的方法，最快的方法是使用 popcntl 指令。在没有该指令的平台上，我将使用查表法。

- prehistoricpenguin

2

在网上查找此关键字的方法是 popcount。 - Jens Gustedt

1

请查看Wikipedia。 - fuz

2个回答

2

如果您不进行太多的比较和分支，而是减少这些在被执行和未被执行之间变化的操作，那么您的汇编代码将会更快。但显然，最快的方法是使用字节查找，特别是因为您只需要处理256个值（可以使用简单方法编写值列表，然后在函数中只需使用“static const table[256] = {...}; return table[value];”）。请对不同的解决方案进行基准测试。我不会感到惊讶，如果您的汇编代码比编译器生成的代码慢！编辑：通过以下方式，您的汇编代码将会稍微更快：

int asmCount(int val)
{
    int res = 0;
    asm volatile("begin:\n\t"
            "movl %1, %%ecx\n\t"
            "and $0x1, %%ecx\n\t"
            "addl %%ecx, %0\n\t"
            "shrl %1\n\t"
            "jnz begin\n\t"
            "end:"
            : "=r"(res)
            : "r" (val)
            : "ecx");      // Important: clobbers ecx!
    return res;
}

我删除了异或操作（res = 0 在任何情况下都会执行），以及比较操作（如果 val 是零，我们会执行一些额外的指令，但是对于任何高位设置的值，它都更糟糕，因为每次迭代需要两个额外的指令，可能意味着多达 16 个额外的指令 - 其中一个是分支！），并将循环末尾的跳转改为 jnz。这大概就是编译器在第一个情况下生成的代码。试图在简单的代码上击败编译器并不容易！

- Mats Petersson

是的，我的汇编代码不像我预期的那样快。 - prehistoricpenguin

我通过删除一些多余的指令来改进了您的汇编代码。但我非常确定表格法更快。特别是如果编译器能够内联它。 - Mats Petersson

好的代码，谢谢！我已经测试了所有的方法，最快的一个是使用 popcntl 指令。 - prehistoricpenguin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fuz · Accepted Answer

如果您想手工编码，请尝试以下方法：

#include <stdint.h>

int popcnt8(uint8_t x) {

    x = (x & 0x55) + (x >> 1 & 0x55);
    x = (x & 0x33) + (x >> 2 & 0x33);
    x = (x & 0x0f) + (x >> 4 & 0x0f);

    return x;
}

在x86上，这段代码会被编译成（AT&T语法）：

popcnt8:
    movl    %edi, %eax
    shrb    %dil
    andl    $85, %eax
    andl    $85, %edi
    addl    %eax, %edi
    movl    %edi, %eax
    shrb    $2, %dil
    andl    $51, %eax
    andl    $51, %edi
    addl    %eax, %edi
    movl    %edi, %eax
    shrb    $4, %dil
    andl    $15, %eax
    addl    %edi, %eax
    movzbl  %al, %eax
    ret

与gcc生成的内置函数相比较：

#include <stdint.h>

int popcnt8_intrin(uint8_t x) { return __builtin_popcount(x); }

在支持SSE 4.2的x86平台上：

popcnt8_intrin:
movzbl  %dil, %eax
popcntl %eax, %eax
ret

这不是最佳的选择；clang 生成的代码如下：

popcnt8_intrin:
    popcntl %edi,%eax
    ret

将计算减少到一条指令。

在没有SSE 4.2的x86上：

popcnt8_intrin:
subq    $8, %rsp
movzbl  %dil, %edi
call    __popcountdi2
addq    $8, %rsp
ret

gcc基本上在这里调用它的库。不太优化。clang做得更好：

popcnt8_intrin:                         # @popcnt8_intrin
movl    %edi, %eax
shrl    %eax
andl    $85, %eax
subl    %eax, %edi
movl    %edi, %eax
andl    $858993459, %eax        # imm = 0x33333333
shrl    $2, %edi
andl    $858993459, %edi        # imm = 0x33333333
addl    %eax, %edi
movl    %edi, %eax
shrl    $4, %eax
addl    %edi, %eax
andl    $252645135, %eax        # imm = 0xF0F0F0F
imull   $16843009, %eax, %eax   # imm = 0x1010101
shrl    $24, %eax
ret

clang计算32位数字的popcnt。在我看来，这并不是最优的。