C/C++中__builtin_popcount()的使用及原理

`__builtin_popcount()` 是一个 GCC 内置函数，用于计算一个无符号整数中二进制下为 1 的位数。在 C++11 标准中，也引入了 `std::bitset::count()` 函数，用于计算 bitset 类型中值为 1 的位数。

使用方法如下：

unsigned int x = 123456789;
int count = __builtin_popcount(x);

原理是通过查表的方式实现的，具体实现方式可以参考以下代码：

int popcount(uint32_t x) {
  const uint32_t m1 = 0x55555555; // 0101...
  const uint32_t m2 = 0x33333333; // 00110011..
  const uint32_t m4 = 0x0f0f0f0f; // 00001111...
  const uint32_t h01 = 0x01010101; // 1的位数
  x -= (x >> 1) & m1; // put count of each 2 bits into those 2 bits
  x = (x & m2) + ((x >> 2) & m2); // put count of each 4 bits into those 4 bits
  x = (x + (x >> 4)) & m4; // put count of each 8 bits into those 8 bits
  return (x * h01) >> 24; // 32 bits to 8 bits
}

这个函数先把每 2 个二进制位中的 1 的个数相加，然后把相邻的 2 个 2 位中的 1 的个数相加，再把相邻的 4 个 2 位中的 1 的个数相加，最后用一个表格把每个字节中的 1 的个数相加，得到总的 1 的个数。由于是使用位运算，所以这个函数非常快。