统计二进制中1的个数（C语言）

待我称王封你为后i 2023-10-12 10:51 31阅读 0赞

**目录**

题目概述

方法一

方法二

方法三

--------------------

## 题目概述 ##

> 给定一个整数n，写一个函数输出32位二进制表示中1的个数（负数用补码表示）

## 方法一 ##

> 分析：当我们在计算1234的每一位数相加之和时，对于得到每一位数，我们的方法是用1234%10，得到4，再将1234/10，得到123，再用123%10，如此循环，直到1234变为0。
> 
> 同理，对于得到整数的每一个二进制位，我们可以通过%2，/2的方式，得到该整数的每一个二进制位

代码如下

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

测试

#include <stdio.h>
    
    int NumberOf1(int n)
    {
    	int count = 0;
    	while (n)
    	{
    		if (n % 2 == 1)
    		{
    			count++;
    		}
    		n /= 2;
    	}
    	return count;
    }
    
    int main()
    {
    	int n = 0;
    	scanf("%d", &n);
    	int ret = NumberOf1(n);
    	printf("%d的二进制中1的个数为%d", n, ret);
    	return 0;
    }

测试结果

![3dfdf76107f04fc2bb4dcac36a81b545.png][]

然而，当输入的整数为负数时，结果就会出问题

![dbcd130924e84386b734a7adf0d95578.png][]

**-1的补码为11111111111111111111111111111111**

**然而结果却为0，通过调试可以发现，当n为-1时，n%2的结果为-1，不等于1，count值不变，而-1/2的结果为0，此时循环退出。**

![6063dd27453e4491b4f90fa32c4f78bd.png][]

**对于这种情况，我们可以使用unsigned int类型来接收n，将n转换为无符号的整数**

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

再次测试

![408883bdd069410fb24a0cfff90ffee9.png][]

此时结果正确

**但是，对于这种方法，接收类型必须为unsigned int**

## 方法二 ##

> 若用n&1，则可以得到n的最后一位，再右移，移除已比较的位数，得到下一位，循环32次，得到二进制中每一位

代码如下

int NumberOf1(int n)
    {
    	int count = 0;
    	for (int i = 0; i < 32; i++)
    	{
    		//将n向右移动i位，再&1
    		if (((n >> i) & 1) == 1)
    		{
    			count++;
    		}
    	}
    	return count;
    }

测试

![31c4e8c9ec9440b298f508b1536c534e.png][]

**但是，对于这种方法，要取出二进制中的每一位，则必须循环32次**

## 方法三 ##

> 当n&(n-1)时，能够去除n的二进制中最后一位1
> 
> 例如
> 
> n = 10，二进制：1010
> 
> n - 1 二进制：1001
> 
> n&(n-1) = 1000
> 
> 每一次n&(n-1)，就去处二进制中一个1，则当n&(n-1)为0时，就去除了n中所有的1

代码如下

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

测试

![8645d8ee8b434d6794959454285e6412.png][]

[3dfdf76107f04fc2bb4dcac36a81b545.png]: https://img-blog.csdnimg.cn/3dfdf76107f04fc2bb4dcac36a81b545.png
[dbcd130924e84386b734a7adf0d95578.png]: https://img-blog.csdnimg.cn/dbcd130924e84386b734a7adf0d95578.png
[6063dd27453e4491b4f90fa32c4f78bd.png]: https://img-blog.csdnimg.cn/6063dd27453e4491b4f90fa32c4f78bd.png
[408883bdd069410fb24a0cfff90ffee9.png]: https://img-blog.csdnimg.cn/408883bdd069410fb24a0cfff90ffee9.png
[31c4e8c9ec9440b298f508b1536c534e.png]: https://img-blog.csdnimg.cn/31c4e8c9ec9440b298f508b1536c534e.png
[8645d8ee8b434d6794959454285e6412.png]: https://img-blog.csdnimg.cn/8645d8ee8b434d6794959454285e6412.png