程式設計之美---确定二進制中1的個數

要實作輸入一個十進制數，輸出這個十進制數轉化為二進制數後，'1'的個數，看起來題目不難，但是如何才能高效做到這一點呢？

test-1

對一個十進制數除以2，則對應的二進制數減少一位，除以2後，餘數即為二進制減少那一位對應的值。

例如：

十進制數：7  （0111） 

                   7%2=1，

                   7/2=3 （011）

十進制數：3 （011）

                   3%2=1，

                   3/2=1  （01）

十進制數：1 （01）

                    1%2=1，

                     1/2=0  （0）

得到‘1’的個數為3。

//test-1
int fun_1(int n)
{
	int sum=0;
	while(n)
	{
		if(n%2==1)
		{
			sum++;
		}
		n/=2;
	}
	return sum;
}
           

test-2

将二進制數按位右移同樣可以達到除的效果，是以，可以按照如下這樣做來得到'1'的個數。

//test-2
int fun_2(int n)
{
	int sum=0;
	while(n)
	{
		sum+=n&0X01;  
		n>>=1;       //右移   n=7,   (0111)，每次向右移一位,向右移操作同樣可以達到相除的目的
	}
	return sum;
}
           

上面對n先和0X01按位與，如果n最低位為 1 ，則按位與的結果為1，sum+=1；

然後對n按位移位，繼續判斷。

PS:按位與、移位都是針對二進制數（也就是将十進制對應的二進制數）進行的。

test-3

對于以下這種情況，我們不想做多次移位，

例如：1024 （100 0000 0000）

如何高效的找到類似這種數字中，'1'的個數呢？

//test-3
int fun_3(int n)
{
	int sum=0;
	while(n)
	{
		n&=(n-1);//隻計算n中‘1’的個數次
		sum++;
	}
	return sum;
}
           

上述方法舉例：

十進制數：12（1100）

第一次是：n=（1100）&（1011）；n=8；

第二次是：n=（1000）&（0111）；n=0；

即隻進行n中'1'的個數次。

擴充題目：

給定兩個正整數A與B，整數A與整數B二進制數表示中有多少位不同？

//A與B的二進制中有多少位不同
#include<iostream>

using namespace std;

int fun(int n,int m)
{
	int sum=0;
	while(n||m)
	{
		sum+=((0x01&n)^(0x01&m));
		n>>=1;
		m>>=1;
	}
	return sum;
}

int main()
{
	int n,m;
	cin>>n>>m;

	int sum=fun(n,m);

	cout<<sum<<endl;

	system("pause");
	return 0;
}