C语言——求一个数字的二进制中 1 的个数

69 阅读 0 评论 46 点赞

我是靠谱客的博主忧郁秋天，最近开发中收集的这篇文章主要介绍C语言——求一个数字的二进制中 1 的个数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

写一个程序打印指定数字的二进制中 1 的个数，比如：15 (0000 1111) 输出4

下面是三种方式：

①通过模2除2（%2、/2）的方法

num%2——取出二进制的最后一位

num/2——右移去掉二进制的最后一位

通过while循环，依次取出二进制的最后一位数字判断是否为1，若为1则count++，while（num）只有当num变为0时循环结束。

问题：在测试-1出现bug，-1的二进制中应该有32个1，输出却为0。我们将-1带入代码中发现-1%2=0，count不增，然后-1/2=0，循环结束，故输出count的值为0。

解决方案：将变量num的数据类型改为unsigned int （无符号整型），此时表示的是正的整型的最大值，所以当num=-1时，表示二进制为32个1的正数，通过循环可以输出正确的个数。

代码1：

#include <stdio.h>

int main()
{
	int num = 15;
      //unsigned int num = -1;
      //改为无符号整型消除bug，表示正的整型的最大值
        int count = 0;//计数
	while (num)
	{
		if (num % 2 == 1)
			count++;
		num = num / 2;
	}
	printf("二进制中1的个数为:%dn",count);
	return 0;
}

②通过右移操作符（>>）、按位与操作符（&）实现

Example：当num=10(1010)，通过右移操作num>>i，二进制向右移动i位。

//i=0，num>>0，右移0位，此时（1010）&（0001）=0

//i=1，num>>1，右移1位，此时（0101）&（0001）=1，count++

//i=2，num>>2，右移2位，此时（0010）&（0001）=0

//i=3，num>>3，右移3位，此时（0001）&（0001）=1，count++

……

因为二进制共32位，所以循环要执行32次后结束，得到count为2。

缺点：不够高效，必须循环32次

代码2(优化1)：

#include <stdio.h>

int count_one_bits(unsigned int value)
{
	int count = 0;
	int i = 0;
	for (i = 0; i < 32; i++)
	{
		if ((value>>i)&1 == 1)
			count++;
	}
	return count; // 返回1的位数 
}
int main()
{
	int number = 0;
	printf("Input:");
	scanf("%d",&number);
	printf("%dn",count_one_bits(number));
	return 0;
}

③通过按位与操作符（&）巧妙运算实现

Example: 当num=15时，

1//num&(num-1)=(1111)&(1110)=(1110)

2//num&(num-1)=(1110)&(1101)=(1100)

3//num&(num-1)=(1100)&(1011)=(1000)

4//num&(num-1)=(1000)&(0111)=0 ，循环停止。共执行4次while循环。

可以发现：每执行一次就去掉了最右边的1，so~循环执行几次就有几个1啦~

高效！有几个1就处理几次

代码3(优化2)：

#include <stdio.h>

int main()
{
	int num = 15;
	int count = 0;
	int i = 0;
	while (num)
	{
          num = num&(num - 1);
          count++;
 	}
	printf("二进制中1的个数为:%dn",count);
	return 0;
}