面試題10：二進制中1的個數

方法一：判斷整數二進制表示中最右邊一位是否為1，接著把整數右移一位判斷倒數第二位是否為1，以此類推，直到整數變成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;  
}  
#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，以此類推。

代碼：

#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，就可進行多少次這樣的操作。顯然可以減少循環次數。

代碼：

#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;
}