统计十进制数对应二进制数中1的个数

文章前瞻

实力很强的小伙伴可以先自己做一下这道题
题目来源：https://www.nowcoder.com/questionTerminal/8ee967e43c2c4ec193b040ea7fbb10b8
参考文章：http://t.csdn.cn/b4TUB
https://www.cnblogs.com/foremember/p/10472515.html

题目：
写一个函数返回参数二进制中 1 的个数。

比如： 15 0000 1111 4 个 1

三种方法拿下它(方法都很巧妙，但是重点是第二、三种方法)

一、除和取模法

#include

unsigned int CountBitOne(unsigned int n)
{
	int count = 0;
	for (int i = 0; i < 32; i++)
	{
		if (n % 2 == 1)
		{
			count++;
		}
		n /= 2;
	}
	return count;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int count = CountBitOne(n);
	printf("%d", count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法介绍：原理就是每次%2之后可以取到最后一位的1（如果不是1那if语句就不执行，n/2之后就可以把这一位除去），然后利用n/2把这一位除去，循环判断下一位。
下面是图解原理

这里估计有一些小伙伴会对上面的两个unsigned int感到困惑。
我来解释一下吧，第一个unsigned int是指函数返回值类型是无符号整形，符号位当成有效位，因此能够返回的数的范围更大了。
第二个unsigned int是针对函数参数为负数的时候，可以将其补码当成正数来处理，下图给函数传-1的时候，在函数里面看到的就是4294967295，4294967295=2^32-1也就是-1补码（32个1）看作正数源码时对应的值

这里的n就还是-1

二、移位操作符法

#include

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

int main()
{
	int n = 0;
	scanf("%d", &n);
	int count = CountBitOne(n);
	printf("%d", count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法介绍：这个右移操作符其实和第一种方法的%/作用是一样的，每次可以将该数的二进制数右移一位，然后和1按位与，由于1的特殊性，每次按位与时，如果最后一位是1，那么与完的结果也是1。
原理图解：

知识补充

常见的都是算术移位

三、位操作符法

#include

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

int main()
{
	int n = 0;
	scanf("%d", &n);
	int count = CountBitOne(n);
	printf("%d", count);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法介绍：这个不多说了，直接上原理图解

知识补充

ps：利用位操作符进行运算时，负数是以补码的形式进行的

题外延伸

看了第三种方法，我们还可以将其进行延伸，利用它判断一个非负数是不是2的正整数次方

#include

int IsIndex(int n)
{
	if (n == 0)
	{
		return 1;
	}
	else
	{
		return n & (n - 1);
	}
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = IsIndex(n);
	printf("输出0表示该数为2^n，输出其他数则不是(n大于等于0)\n");
	printf("%d", ret);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23