【每日易题】求二进制中1的个数——三种非常巧妙的解题思路

目录

?一、题目介绍

二、解题思路?

1. 第一种解题方法

2. 第二种解题方法

3. 第三种解题方法

---

?一、题目介绍

原题链接：二进制中1的个数

二、解题思路?

1. 第一种解题方法

十进制数中，例如1479，只要通过不断的%10和/10操作，就可以得到1479的每一位。

而将这个方法推广到二进制中也是可行的。只要通过不断的%2和/2操作，也可以将二进制的每一位拿出来，从而对每一位进行判断，记录1的个数。

int count_num_of_1(int n)
{
	int count = 0;
	while (n)
	{
		if (n % 2 == 1)
			count++;
		n /= 2;
	}
	return count;
}

int main()
{
	int num = 0;
	scanf("%d", &num);
	int ret = count_num_of_1(num);
	printf("%d\n", ret);
	return 0;
}

? ? 当然，不要开心地以为到这里就完成了，当num为负数时，你会发现结果是错误的，例如num = -1。当num为-1时，num%2 != 0，因此会跳过if直接执行num /=2，结果num为0直接跳出循环并返回count=0。而真实情况下-1在内存中存储的是补码，即32个1。

? ? 不了解原码反码补码的可以看我往期博客，这里就不过多赘述。

【C语言】整数的二进制以及移位操作符_Hacynn的博客-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/132767057?spm=1001.2014.3001.5502

解决方法：在count_num_of_1函数参数中将int n 改成?unsigned int n，即无符号整型。这样当num = -1时，此时n会认为num不是-1而是一个二进制全是1的数（即4294967295），此时count就为32。

?

2. 第二种解题方法

第二种方法是通过移位的方式求出1的个数，将二进制序列的每一位都&1，当结果为1时count++。下面以15为例子：

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

3. 第三种解题方法

?前面两种解题方法其实都不太高效，这里介绍一个非常巧妙的方法，巧妙到我们难以想象得到，该方法的核心就是n = n & (n -?1)，下面以15为例子讲解：

n = n & (n -?1)就可以理解为：只要执行一次，n的二进制序列中的1就少一个。

那么求二进制中1的个数就变成了n = n & (n -?1)能够执行几次，只要知道执行几次n = n & (n -?1)就可以知道n的二进制序列中有多少个1。

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

---

?这次题目的讲解就到此为止了。如果觉得作者写的不错，求给作者一个大大的点赞支持一下，你们的支持是我更新的最大动力！

?