隨筆檔案

求整數 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.shnenglu.com/jake1036/archive/2011/05/18/146698.html