Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Recursive Popcount:

    unsigned int popcount(unsigned int n) 
    {
        return (n &= n - 1u) ? (1u  + popcount(n)) : 0u;
    }
Clang 21.1 x64:

    popcount:
            mov     eax, -1
    .LBB0_1:
            lea     ecx, [rdi - 1]
            inc     eax
            and     ecx, edi
            mov     edi, ecx
            jne     .LBB0_1
            ret
GCC 15.2:

    popcount:
            blsr    edi, edi
            popcnt  eax, edi
            ret
Both compiled with -O3 -march=znver5


Because the function is not quite correct. It should be

    return n ? (1u  + popcount(n & n - 1u)) : 0u;
which both Clang and GCC promptly optimize to a single popcnt.


There should be testsuites, which are based on testing which compilation passes the compiler chose.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: