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指令。在没有指令的平台上，我将使用查表。

4

2 回答 2

9

如果你想手动编码，试试这个：

#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

这不是最优的；铿锵生成：

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。这不是最佳的恕我直言。

于 2012-12-23T10:35:58.393 回答
2

如果您没有进行太多的比较和分支，这些比较和分支会因采用和未采用而有所不同，那么您的汇编代码会更快。

但显然，最快的方法是进行字节查找，特别是当您只处理 256 个值时（您可以使用 naive 方法编写值列表，然后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;
}

我删除了 xor（res = 0 无论如何都应该这样做），并比较（当然，如果 val 为零，我们执行一些额外的指令，但是对于任何设置了高位的东西，情况要糟糕得多，因为它是两个额外的指令每次迭代，这意味着可能有 16 条额外的指令——其中一条是分支！），并在循环结束时将跳转更改为 jnz。这可能是编译器在您的第一种情况下生成的大致内容。试图在简单的代码上击败编译器并不是那么容易！

于 2012-12-23T10:09:04.153 回答