计算二进制中1的个数

在计算机里，一个int整型的数据的二进制最多有32位，想要统计里面的1的个数，最基本的思路就是让n对2求余（基于10进制转换为二进制的方法）等于1，并实现累加。

//方法1，对二求余等于1
int NumOf1(int n){
	int count=0;
	while(n)
	{
		if(n%2==1)
		{
			count++;
		}
		n=n/2;
	}
	return count;
	
	
}

这种方法非常简单，但当一个数非常大时，进行了大量的取模以及除法运算，取模和除法运算的效率本来就比较低。有没有可以提高效率的方法呢？

第二种方法：遍历二进制位数

开头提到，对于32位的二进制数，如果直接遍历来计数1的话会更加方便，具体操作如下：

这里会用到&（按位与）和>>（右移操作符）进行实现，从最低位开始，每一位都和1按位与（同1为1，异1为0）并进行判断计数，完成后左移一位，既然有32位，就循环32次，重述上述操作。

//方法2，遍历32位
int NumOf1(int n){
	int count=0;
	for(int i=0;i<32;i++){
		if(((n>>i)&1)==1)
		count++;
	}
	return count;
	
	
}

二者对比起来，后者效率更高，但唯一的缺点是，不管这个数有多大，它都得遍历32次，这样多余的循环次数其实也会影响效率，可不可以将循环次数减少到最小呢？

第三种方法：让n与n-1按位与

前面提到过，按位与的思想是同1为1，异1为0，那如果我们让n与n-1进行按位与会发生什么呢？

举个例子，我们用一个循环来让n与n-1按位与，n设为15，二进制为1111，n-1=14=1110，这时候按位与，我们发现，1111&1110=1110，得到的值与15相比少了1个1，那可不可以将这个1计数呢，我们接着来，这时n=1110，n-1=1101，1110&1101=1100，欸，又少了一个1，继续，这时n=1100，n-1=1011，按位与=1000，最后再与n-1=0111得到0000，循环结束，我们发现，减少的1的个数刚好是15的二进制1的个数，同时也等于循环的次数，极大的提高了效率。

//方法3，n&n-1
int NumOf1(int n){
	int count=0;
	while(n)
	{
		n=n&(n-1);
		count++;
	}
	return count;
	
}