巧用位运算求解二进制中1的个数

位运算是将数字化为二进制后，对每一位的0或1进行的运算。一般的运算有与&、或|、异或^和移位等。

如何利用位运算来求解二进制中1的个数呢？

首先大多数人想到的是先判断最右边的一位是不是1，接着将其右移一位，知道数为0停止。将一个数与上1则可以解决这个问题。

代码如下：

int NumofOne1(int num)
{
	int count=0;
	while(num)
	{
		if(num&1)
		{
			count++;
		}
		num=num>>1;
	}
	return count;
}

仔细思考就会发现，其实上述代码是存在很多问题的。如果我们传入一个负数给这个函数，这个数将会变成0xFFFFFFFF的死循环。为了避免这种问题的发生，可以不进行右移运算。先将输入的数字与上1，判断最右边是否为1，然后将1进行左移一位，判断倒数第二位……以此类推。

修改代码如下：

int NumofOne2(int num)
{
	int count=0;
	unsigned int flag=1;
	while(flag)
	{
		if(num&flag)
		{
			count++;
		}
		flag=flag<<1;
	}
	return count;
}

这个解法虽然避免了死循环的问题，但是却要循环32次，可不可以让其有几个1就循环几次呢？

可以采用将一个整数减去1，再和原整数做与运算，这样可以把该整数最右边一个1变成0，那么就实现了我们所说的有多少个1就进行多少次循环。

代码如下：

int NumofOne3(int num)
{
	int count=0;
	while(num)
	{
		++count;
		num=(num-1)#
	}
	return count;
}

巧用位运算求解二进制中1的个数

原文：http://luminous.blog.51cto.com/10797288/1742334