二進制中1的個數

方法一：判斷整數二進制表示中最右邊一位是否為1，接著把整數右移一位判斷倒數第二位是否為1，以此類推，直到整數變成0為止。

代碼：

[cpp]
#include "stdafx.h"  
#include <iostream>  
using namespace std; 
 
 int CountOf1(int n) 
 { 
    int nCount = 0; 
  
    while (n) 
    { 
        if (n & 1) 
        { 
            nCount++; 
        } 
  
        n = n >> 1; 
    } 
  
    return nCount; 
 } 
 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    cout << CountOf1(7) << endl; 
    system("pause"); 
    return 0; 
} 

#include "stdafx.h"
#include <iostream>
using namespace std;

 int CountOf1(int n)
 {
  int nCount = 0;
 
  while (n)
  {
   if (n & 1)
   {
    nCount++;
   }
 
   n = n >> 1;
  }
 
  return nCount;
 }

int _tmain(int argc, _TCHAR* argv[])
{
 cout << CountOf1(7) << endl;
    system("pause");
 return 0;
}

缺點：如果輸入的數為負數，若一直做右移運算，最終將陷入死循環。

方法二：為避免陷入死循環，可以不右移輸入的數字，先將輸入數字和1做與運算，判斷最低位是否為1，接著將1左移一位，判斷倒數第二位是否為1，以此類推。

代碼：

[cpp]
#include "stdafx.h"  
#include <iostream>  
using namespace std; 
 
 int CountOf1(int n) 
 { 
    int nCount = 0; 
    unsigned int flag = 1; 
    while (flag) 
    { 
        if (n & flag) 
        { 
            nCount++; 
        } 
  
        flag = flag << 1; 
    } 
  
    return nCount; 
 } 
 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    cout << CountOf1(7) << endl; 
    system("pause"); 
    return 0; 
} 

#include "stdafx.h"
#include <iostream>
using namespace std;

 int CountOf1(int n)
 {
  int nCount = 0;
  unsigned int flag = 1;
  while (flag)
  {
   if (n & flag)
   {
    nCount++;
   }
 
   flag = flag << 1;
  }
 
  return nCount;
 }

int _tmain(int argc, _TCHAR* argv[])
{
 cout << CountOf1(7) << endl;
    system("pause");
 return 0;
}

缺點：循環次數等於整數二進制的位數，32為的整數需要循環32次。

方法三：把整數減去1，在和原整數做與運算，會把整數最右邊的一個1變成0，那麼一個整數的二進制表示中有多少個1，就可進行多少次這樣的操作。顯然可以減少循環次數。

代碼：

[cpp]
#include "stdafx.h"  
#include <iostream>  
using namespace std; 
 
int CountOf1(int n) 
{ 
    int nCount = 0; 
 
    while (n) 
    { 
        nCount++; 
        n = n & (n -1); 
    } 
 
    return nCount; 
} 
 
 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    cout << CountOf1(7) << endl; 
    system("pause"); 
    return 0; 
} 

#include "stdafx.h"
#include <iostream>
using namespace std;

int CountOf1(int n)
{
 int nCount = 0;

    while (n)
    {
  nCount++;
  n = n & (n -1);
    }

 return nCount;
}

int _tmain(int argc, _TCHAR* argv[])
{
 cout << CountOf1(7) << endl;
    system("pause");
 return 0;
}