博客

统计二进制中1的个数

题目要求

写一个函数返回参数二进制中1的个数。 //比如:15 00001111 4个1

首先,我们知道求十进制中的每一位数,是拿那个十进制数模10(%10),拿出最后一位.



那么,同理,二进制的每一位数,自然也可以通过二进制数模2(%2),每拿出一位判断.



因此这是第一种方法,也是最容易想到的一种,我也只能想到这一种:(

int sumone_first(unsigned int n)//这里是无符号数,因为要考虑负数的存在,如果写int,那么负数,例如-1,则会变成0.
{
	int count=0;
	
	while(n)
	{
		if(n%2==1)
		{
			count++;//统计1的个数
		}
		n/=2;
	}
	
	return count;
}

我们在学习操作符的时候,了解过关于与运算,或运算等对于二进制的运算操作,这里正好可以派上用场.



例如十进制14这个数在计算机中的32位二进制:00000000|00000000|00000000|00001100



不难发现:

1. 
   如果拿一个二进制0同1相与,得到的就是0,反之亦然,所以要求1的个数,只需要不停将最后一位同1相与即可
   
2. 
   在最后一个数比较完之后,理应将其移出,将前一位变成后一位,而二进制中实现这样的操作的操作符就是右移(>>).右移左边补零,右边多余丢弃
   

这就是第二种利用与运算的解法

int sumone_second(int n)
{
	int count=0,i=0;
	for(i=0;i<32;i++)
	{
		if(n>>i&1==1)
		{
			count++;
		}
	}
	return count;
}

既然了解了与运算,那么试着找下以下的规律呗.

• 13-1101
• 1101 n
• 1100 n-1
• 1101&1100=1100 n
• 1011 n-1
• 1100&1011 1000 n
• 0111 n-1
• 1000&0111 0000 n

没错,拿一个二进制数同它减1的数相与,每一次相与都能减少一位1,因此可以拿这种规律判断1的个数

这就是第三种利用与运算加找规律的解法

int sumone_third(int n)
{
	int count=0;
	
	while(n)
	{
		n=n&(n-1);
		count++;
	}
	
	return count;
}

																		 如有不足,欢迎指正