随笔档案

求整数 n 的二进制表示中 1 的个数

1.
采用除二取余法
while (n != 0)
{
 if (n % 2 == 1)
 {
  ++ret;
 }
 n /= 2;
}
这种方法对于 n 是正数的时候没有问题，而且需要是整数。
如果 n 是负整数，则需要与机器相关，如果 n = -3, 则 n % 2 有余 -1 ，这种情况下，得到的最终结果是 0，对于任何的负整数结果都是 0
也可以通过移位的方法做：
while (n != 0)
{
 ret += (n & 1);
 n >>= 1;
}
这种方法对于正数是可行的，并且不限于整数
但是对于负数，由于最高位是 1 ，做的意味是逻辑移位，移位后高位还是 1 ，程序进入了死循环。

2.
对 1 进行左移位，做位运算
int flag = 1;
int ret = 0;
while (flag != 0)
{
 if ((flag & n) != 0)
 {
  ++ret;
 }
 flag << 1
}

这种方法不是对 n 进行的移位，而是对 flag 移的位，不会造成 n 移位带来的死循环。当 flag 移到 sizeof (flag) * 8 位时，归零，循环终止。

3.
采用 n & (n - 1) 操作
以上两种方法都是做了 sizeof (type) * 8 次循环
采用 n & (n - 1) 的方式，只需做 n 的二进制中含有 1 的个数次循环即可。
while (n != 0)
{
 ++ret;
 n &= (n - 1);
}

http://www.cppblog.com/jake1036/archive/2011/05/18/146698.html