计算一个整数有的二进制表示中多少个 1

很早以前记着有这么一个技巧，计算一个整数的二进制表示多少个 1 。

template <typename T>
int count(T a) {
  int ret = 0;
  for (T x = a; x; x &= ~(x - 1) ^ x) {
    ret++;
  }
  return ret;
}

例如输出结果

 0x0 -> 0
 0x1 -> 1
 0x2 -> 1
 0x3 -> 2
 0x4 -> 1
 0x5 -> 2
 0x6 -> 2
 0x7 -> 3
 0x8 -> 1
 0x9 -> 2
 0xa -> 2
 0xb -> 3
 0xc -> 2
 0xd -> 3
 0xe -> 3
 0xf -> 4

这个是怎么工作的呢？

如果 a 是零，程序返回零。这个很容易看得出来。 如果不是零，那么假设 x 可以表示成为 b1 b2 b3 b4 1 0 0 0 ... 结尾有 N 个 0 ，一个 1 。 b1 ... b4 有可能是 0 或者 1

那么 x-1 可以表示成为 b1 b2 b3 b4 0 1 1 1 ... 。

(x-1)^x 可以表示成为 0000 11111... 因为 b1 ^ b1 = 0 无论 b1 是 0 or 1 。

这样的我们得到一个 mask ， x&= ~mask 就可以消除掉 x 最低位的一个 1 。于是不停地重复，需要重复几次，就说明有多少个 1 。于是我们的返回值就是简单计数器，计算循环了多少次。

这个严格上来说，效率比较高。因为循环次数是 1 的个数。

这个技巧属于完全无用的技巧，如果从可读性的角度来说，下面的代码的可读性更好。

template <typename T>
int count2(T a) {
  int ret = 0;
  T pin = 1;
  for (size_t i = 0; i < sizeof(T); ++i, pin<<=1){
      if(pin&a) ret++;
  }
  return ret;
}

对于喜欢装 13 的，抗击打能力比较强的，不怕挨揍的，的那些人，可以考虑在生产代码里面采用第一种姿势。后果自负。