探索__builtin_popcount

g++提供了个内置的函数:__builtin_popcount,来统计整形数字的二进制表示中1的数量。我很好奇，就想看看库函数使用什么办法实现的。

一般我们自己来写这个函数，会是这样：

int popcount1(int x)
{
    int r = 0;
    while(x)
    {
        if(x&1)
            r++;
        x = x>>1;
    }
    return r;
}

或者是这样：

int popcount2(int x)
{
    int r = 0;
    while(x)
    {
        r++;
        x = x&(x-1);
    }
    return r;
}

那么g++中是怎么实现的呢？用gdb看看

测试函数如下：

#include <iostream>
using namespace std;
int main(int argc,char** argv)
{
    if(argc!=3)
        return -1;
    int c = stoi(argv[1]);
    int d = stoi(argv[2]);
    int a = __builtin_popcount(c^d);
    cout<<a<<endl;
    return 0;
}

在gdb中，运行到这个函数：

   0x5555555552de <main(int, char**)+217>:  xor    eax,DWORD PTR [rbp-0x18]
   0x5555555552e1 <main(int, char**)+220>:  mov    eax,eax
   0x5555555552e3 <main(int, char**)+222>:  mov    rdi,rax
=> 0x5555555552e6 <main(int, char**)+225>:  call   0x5555555550a0 <__popcountdi2@plt>
   0x5555555552eb <main(int, char**)+230>:  mov    DWORD PTR [rbp-0x1c],eax
   0x5555555552ee <main(int, char**)+233>:  mov    eax,DWORD PTR [rbp-0x1c]
   0x5555555552f1 <main(int, char**)+236>:  mov    esi,eax
   0x5555555552f3 <main(int, char**)+238>:  lea    rdi,[rip+0x2da6]        # 0x5555555580a0 <std::cout@@GLIBCXX_3.4>

看到这个函数了，叫__popcountdi2@plt，关于这个plt，涉及到了linux系统中dynamic shared objects的装载时重定位机制有关，这个plt（Procedure LInkage Table）涉及到延迟绑定机制的实现。具体的我后面应该会单独写一下。

下面看看popcount函数的内容：

=> 0x7ffff7ca50a0 <__popcountdi2>:      movabs rdx,0x5555555555555555
   0x7ffff7ca50aa <__popcountdi2+10>:   mov    rax,rdi
   0x7ffff7ca50ad <__popcountdi2+13>:   shr    rax,1
   0x7ffff7ca50b0 <__popcountdi2+16>:   and    rax,rdx
   0x7ffff7ca50b3 <__popcountdi2+19>:   movabs rdx,0x3333333333333333
   0x7ffff7ca50bd <__popcountdi2+29>:   sub    rdi,rax
   0x7ffff7ca50c0 <__popcountdi2+32>:   mov    rax,rdi
   0x7ffff7ca50c3 <__popcountdi2+35>:   shr    rdi,0x2
   0x7ffff7ca50c7 <__popcountdi2+39>:   and    rax,rdx
   0x7ffff7ca50ca <__popcountdi2+42>:   and    rdi,rdx
   0x7ffff7ca50cd <__popcountdi2+45>:   movabs rdx,0xf0f0f0f0f0f0f0f
   0x7ffff7ca50d7 <__popcountdi2+55>:   add    rdi,rax
   0x7ffff7ca50da <__popcountdi2+58>:   mov    rax,rdi
   0x7ffff7ca50dd <__popcountdi2+61>:   shr    rax,0x4
   0x7ffff7ca50e1 <__popcountdi2+65>:   add    rax,rdi
   0x7ffff7ca50e4 <__popcountdi2+68>:   and    rax,rdx
   0x7ffff7ca50e7 <__popcountdi2+71>:   movabs rdx,0x101010101010101
   0x7ffff7ca50f1 <__popcountdi2+81>:   imul   rax,rdx
   0x7ffff7ca50f5 <__popcountdi2+85>:   shr    rax,0x38
   0x7ffff7ca50f9 <__popcountdi2+89>:   ret

输入应该是edi，输出是rax

到这一步我就。。我太菜了，一时间看不懂。。不过应该还是很好翻译成c语言的。我在网上看到翻译过的代码，但是现在一时找不到了，听说是用了二分法？范增应该听巧妙地。整个函数都没有任何条件跳转语句，就完成了1的计数，厉害。

等我看懂了，就把这一章写完。。。