Fastest way to count bits

Question

Possible Duplicate:
How to count the number of set bits in a 32-bit integer?

Give a unsigned char type value,count the total bits in it.What's the fastest way? I wrote three function as below,what's the best way,and can someone come up with a faster one?(I just want the extremely fast one)

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;
}

EDIT:

I have test all the method,the fastest one is to use the popcntl instruction.In platform without the instruction,I will use table look-up.

Have a look at [Wikipedia](http://en.wikipedia.org/wiki/Popcount) — fuz, Dec 23 '12 at 09:12

score 9 · Accepted Answer · answered Dec 23 '12 at 10:35

If you want to code it by hand, try this:

#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;
}

on x86, this compiles to (AT&T-syntax):

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

Compare this to what gcc generates with the intrinsic:

#include <stdint.h>

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

On x86 with SSE 4.2:

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

which is not optimal; clang generates:

popcnt8_intrin:
    popcntl %edi,%eax
    ret

reducing the calculation to one (!) instruction.

On x86 without SSE 4.2:

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

gcc essentially calls its library here. Not quite optimal. clang does a little better:

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 calculates popcnt for a whole 32 bit number. This is not optimal imho.

the "clang" variant I suppose presumes that the caller has zero-extended the byte, where gcc is doing that in the function. Does the compiler not inline these things anyways? — Mats Petersson, Dec 23 '12 at 11:20
@Mats Yes, it should. If I recall correctly the API states that a byte parameter that is register-passed must be extended correctly but not all compilers really do that. gcc is conservative in the sense that it validates the input first. — fuz, Dec 23 '12 at 11:22

Mats Petersson · Answer 2 · 2012-12-23T10:39:54.213

Your assembler code would be faster if you didn't do so many compares and branches that vary from taken and not taken.

But clearly, the fastest method is to do a byte lookup, particularly as you are only dealing with 256 values (you can use the naive method to write a list of the values, then just have a static const table[256] = { ... }; return table[value]; in your function.

Benchmark the different solutions.

I wouldn't be surprised if your assembler code is slower than the compiler generated code!

Edit: Your assembler code would be slight faster by doing:

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;
}

I removed the xor (res = 0 should do that anyways), and compare (sure, if val is zero, we execute a few extra instructions, but for anything with high bits set, it is much worse, since it's two extra instructions for every iteration, meaning potentially 16 extra instructions - and one of them a branch!), and changed the jump to a jnz at the end of the loop. It probably is roughly what the compiler generates in your first case. Trying to beat the compiler on simple code isn't that easy!

I've improved your assembler code by removing some superflous instructions. But I'm pretty certain the table method is faster. Particularly if the compiler is able to inline it — Mats Petersson, Dec 23 '12 at 10:41
Good code,thank you!I have test all the method,the fastest one is use `popcntl` instruction. — prehistoricpenguin, Dec 23 '12 at 11:16

Fastest way to count bits

EDIT:

2 Answers2

Linked