求二进制中1的个数的三种方法

求二进制中的1的个数

第一种方法：模2除2

首先明白如何得到一个数的十进制的每一位？
以123为例
123%10 = 3， 123/10 = 12
12%10 = 2，12/10=1
1%10 = 1，1/10 = 0
这样就得到了一个十进制的每一位

我们可以用这个方法类推到得到一个数的二进制的的每一位
以11为例，11的二进制为1011
11%2 = 1，11/2 = 5
5%2 = 1，5/2 = 2
2%2 = 0，2/2 = 1
1%2 = 1，1/2 = 0
顺序不重要，重要的是我们通过模2得到了三个1，说明11的二进制有三个1

以此为根据设计程序

int main()
{
	int n;
	scanf("%d", &n);
	int count = 0;
	while (n)
	{
		if (n % 2 == 1) count++;
		n /= 2;
	}
	printf("%d\n", count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

但是这种方法是有缺陷的，就是不能统计负数的补码中的二进制的1的个数

第二种方法：利用操作符右移后与1

代码如下：

int main()
{
	int n;
	scanf("%d", &n);
	int count = 0;
	for (int i = 0; i < 32; i++)
		if ((n >> i & 1) == 1) count++;
	printf("%d\n", count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10

但是这种方法也有缺陷，就是不管是什么数都必须要循环32次，效率并没有那么高

第三种方法：该数与上比它小1的数（最优的方法）

代码如下：

int main()
{
	int n;
	scanf("%d", &n);
	int count = 0;
	while (n)
	{
		count++;
		n = n & (n - 1);
	}
	printf("%d\n", count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14