编程之美1——一个数的二进制表示中1的个数

这里要介绍3种解法

第一种；（常规解法）

数在计算机内部都是用二进制表示的，所以可连续用数n除2

代码1：

#include <iostream>
using namespace std;
int main(void)
{
    int n,m;
    m=0;
    cin>>n;
    while(n)
    {
        if(n%2)    //如果n不能整除2，说明当前n的末尾数为1
            m++;
        n>>=1;    //n右移1位，即n/2
    }
    cout<< m <<endl;
    return 0;
}

第二种：使用位操作

&：若a为1，且b为1，则a&b为1，否则，a&b为0

这里初始化i=0x1；

n&i若为1，则n的末尾为1，否则为0

代码2：

#include <iostream>
using namespace std;
int main(void)
{
   //	使用位操作,1 和 二进制的最后一位进行 与(&) 运算
	int n,i,m;
	m=0;
	i=0x1;
	cin>>n;
	while(n)
	{
		m+=(n&i);
		n>>=1;
	}
	cout << m <<endl;
    return 0;
}

第三种：使用另一种位操作

若n的二进制表示为0010 0000，则第二种算法明显有待改进

可让n与n-1进行 & 运算，若n&(n-1)==0，则为上述情况(n的二进制表示中，只有一位是 0)。

代码3：

#include <iostream>
using namespace std;
int main(void)
{	
	int n,m;
	m=0;
	cin>>n;
	while(n)
	{
		n&=(n-1);
		m++;
	}
	cout << m <<endl;

	return 0;
}

本文出自 “hacker” 博客，请务必保留此出处http://anglecode.blog.51cto.com/5628271/1631155

编程之美1——一个数的二进制表示中1的个数

原文：http://anglecode.blog.51cto.com/5628271/1631155