c语言实现获取一个数中在内存中二进制中1的个数(正常方法和巧妙方法）

96 阅读 0 评论 64 点赞

我是靠谱客的博主着急草丛，最近开发中收集的这篇文章主要介绍c语言实现获取一个数中在内存中二进制中1的个数(正常方法和巧妙方法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

错误方法：

思路：

如果是一般方法，我们可能会借助进制转换的方法，一个数%2可以得到二进制的最后一位，然后再除二再%2就可以得到倒数第二位，以此类推制造一个循环，每次判断%2得到的数，如果是一就使得二进制总数＋1，最后就可以得出二进制中一的数：

#include<stdio.h>
int main()
{
	int n = 0;
	int count = 0;
	scanf("%d", &n);
	while (n / 2 != 0)
	{
		if (n % 2 == 1)
			count++;
		n /= 2;
	}
	if (n % 2 == 1)
		count++;
	printf("%d", count);
	return 0;
}

但是，这种方法真的行吗？如果是负数呢？

我们知道，负数在内存中是以补码的形式存在的，所以-1的二进制的1的个数应该是32，因此我们可以看出这种方法是不行，这时候，我们就想到了想对一个数中的二进制进行操作，那位操作是不是更好！这时，就引出了一般方法。

一般方法：

思路：

我们知道c语言有个按位与操作符，0按位与上1和0都是0，1只有按位与上1才是1，因此，我们可以依此将1和该数字就行按位与操作，然后就可以得出该数字二进制最后一位的值，这时候判断是否是1即可（这里运用了一个原理：位操作符不改变原值）,然后将该数使用>>(右移操作符）让该数右移1，然后用相同的方法判断该位是否为一，然后循环31次就可以获得二进制中一的个数了。

代码如下：

#include<stdio.h>
int main()
{
	int n = 0;
	int i = 0;
	int count = 0;
	scanf("%d", &n);
	for (i = 0;i < 32;i++)
	{
		if (((n >> i) & 1) == 1)
			count++;
	}
	printf("%d", count);
	return 0;
}

这里要注意，肯定有人会有以下写法：

int main()
{
	int n = 0;
	int i = 0;
	int count = 0;
	scanf("%d", &n);
	while (n != 0)
	{
		if (n & 1 == 1)
			count++;
		n >>= 1;//这样可以吗？
	}
	printf("%d", count);
	return 0;
}

但是，如果n为负数，这个方法仍旧不行，假设你输入一个负数，这个程序就会陷入死循环，为什么呢？

这里，我们要来普及一下，在程序中右移的方式有两种，算术右移和逻辑右移，这两种有什么差别呢？

算术右移：右移的过程中左边补零
逻辑右移：右移的过程中左边补符号位

如果想要深入了解，可以看下面的链接：

算术右移和逻辑右移详解

如今的大多数编译器都采取逻辑右移的方式，因此，如果我们输入了一个负数，在右移的过程中该数就一定不会变为0，因此程序最后就会进入死循环，因此这么做是不行的。

以上就是一般方法了，接下来我们来认识一个非常牛逼的方式。

精妙方法：

用上面这个代码来寻找一的个数，大家是不是会觉得效率不高，因为如果这个数是1，那这个数也要循环32次才能给出答案，是非常没有效率的（虽然32次还是可以忽略不记，但是如果是更多位数呢？），因此，经过一些大佬的思考，最后得出了一个新方法，先上代码然后进行解释：

int main()
{
	int n = 0;
	int count = 0;
	scanf("%d", &n);
	while (n)
	{
		count++;
		n &= (n - 1);//是不是很interesting？
	}
	printf("%d", count);
	return 0;
}

相信这里大家的疑惑只有一个也只能是一个，那就是n&(n-1)是什么意思？

这里的意思是使得该数二进制的最后一个1变成0；为什么呢？

通过这里就可以看到，n-1把最后一个1后面的0都变成了1，而把最后一位变成了0，而两者按位与之后，最后一个1就变成了0，其后面的数也变成了0，而最后一个1前面的数都不会变，因此，当该数不等于0时，每进行一此该计算，该数二进制中1的个数就少1，因此，只要计算该数进行了多少次计算变成了0，该次数就是该数二进制中1的个数。

妙用：

那么，有了这个结论还能用来干嘛呢？其实有很多中方法。

判断一个数是否是2的次方数，那么有了这个结论就很简单了，如果该数的二进制数只有一个1，这个数就只有一个二进制数是1，代码如下：

int main()
{
	int n = 0;
	int count = 0;
	printf("请输入你要计算二进制中1的个数的数:>");
	while(scanf("%d", &n)!=EOF)
	{
		count = 0;
		while (n)
		{
			count++;
			n &= (n - 1);
		}
		if(count==1)
			printf("是2的次方数n");
	}
	return 0;
}

知道了这个技巧，就可以运用在很多方面，大家还知道什么有趣的算法呢，欢迎评论区留言啊！