隨筆檔案

求整數(shù) n 的二進(jìn)制表示中 1 的個(gè)數(shù)

1.
采用除二取余法
while (n != 0)
{
 if (n % 2 == 1)
 {
  ++ret;
 }
 n /= 2;
}
這種方法對(duì)于 n 是正數(shù)的時(shí)候沒有問題，而且需要是整數(shù)。
如果 n 是負(fù)整數(shù)，則需要與機(jī)器相關(guān)，如果 n = -3, 則 n % 2 有余 -1 ，這種情況下，得到的最終結(jié)果是 0，對(duì)于任何的負(fù)整數(shù)結(jié)果都是 0
也可以通過移位的方法做：
while (n != 0)
{
 ret += (n & 1);
 n >>= 1;
}
這種方法對(duì)于正數(shù)是可行的，并且不限于整數(shù)
但是對(duì)于負(fù)數(shù)，由于最高位是 1 ，做的意味是邏輯移位，移位后高位還是 1 ，程序進(jìn)入了死循環(huán)。

2.
對(duì) 1 進(jìn)行左移位，做位運(yùn)算
int flag = 1;
int ret = 0;
while (flag != 0)
{
 if ((flag & n) != 0)
 {
  ++ret;
 }
 flag << 1
}

這種方法不是對(duì) n 進(jìn)行的移位，而是對(duì) flag 移的位，不會(huì)造成 n 移位帶來的死循環(huán)。當(dāng) flag 移到 sizeof (flag) * 8 位時(shí)，歸零，循環(huán)終止。

3.
采用 n & (n - 1) 操作
以上兩種方法都是做了 sizeof (type) * 8 次循環(huán)
采用 n & (n - 1) 的方式，只需做 n 的二進(jìn)制中含有 1 的個(gè)數(shù)次循環(huán)即可。
while (n != 0)
{
 ++ret;
 n &= (n - 1);
}

http://m.shnenglu.com/jake1036/archive/2011/05/18/146698.html