【三种方法】求一个整数存储在内存中二进制中的1的个数附两道课外练习题

admin管理员组

文章数量:1794759

【三种方法】求一个整数存储在内存中二进制中的1的个数附两道课外练习题

题目：求一个整数存储在内存中的二进制中的1的个数

法一：取模与取余

分析： 数据在内存中以补码形式存储 题目要求我们求一个数在内存中二进制中1的个数，从这里可以想到，我们需要定义一个变量count来计数，再得到二进制的每一位，并且再判断它是否为1，这道题就差不多解决了。但问题就是如何得到二进制的每一位？我们知道二进制的每一位要么是0要么是1，因此求二进制中1的个数，只需%2，看得到的余数是不是1，如果是1，count++，之后/2使得这个二进制去掉最后一位，如此循环往复，直到该数字为0，count的值就是1的个数。

代码语言：javascript代码运行次数：0运行复制

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

运行结果：

从运行结果来看，-1的输出是错的，因此，这种实现方法肯定有问题。

那是为什么呢？

现在，我们来找找问题：

输入-1时，由于num为负数，所以num/2的值为向下取整的结果，即-1/2=-1，此时num的值仍为-1，因此while循环不会结束，导致程序出现死循环。同时，由于num的值一直为负数，所以num % 2 的结果始终为0，导致count的值一直为0。 因此这个问题是由于-1是负数，那我们把num类型定为无符号整型，会整型会怎样呢？

修改后：

代码语言：javascript代码运行次数：0运行复制

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

运行结果：

答案正确。

这是因为将输入的无符号整数 num 强制转换为有符号整数 int 类型，导致输入的负数被解释为一个很大的正整数。当输入-1时，它被当作非常大的正整数（4294967295）来处理，然后计算其补码二进制表示中 1 的个数，最终输出结果为 32。

法二：按位与和移位操作符

这里先上代码，再分析

代码语言：javascript代码运行次数：0运行复制

int main()
{
	int num = -1;
    scanf("%d", &num);
	int i = 0;
	int count = 0; //计数
	for (i = 0; i < 32; i++)
	{
		if (num & (1 << i))
			count++;
	}
	printf("⼆进制中1的个数 = %d\n", count);
	return 0;
}

我们以-1来分析：

• 数据在计算机中的存储形式是补码，而程序打印数据是以二进制的原码形式转换成十进制
• -1的原码：10000000000000000000000000000001 -1的反码：11111111111111111111111111111110 -1的补码：11111111111111111111111111111111
• （1 << i) ：1向左移动 i 位

当 i 为0时，结果为0000......01； 当 i 为1时，1向左移动一位，最左边丢掉一位，右边补一个0，结果为0000.....10； 当 i 为2时，1左移两位，丢掉最左边两位，在最右边补两个0，结果为0000.......100 因此（1<<i）产生的效果就是让数字1存储在内存中唯一的二进制位 1 移动 i 位

• &按位与运算符：对应二进制位有0，则0
• num & （1 << i）：当 i 为0 时，1111....11& 0000....01结果为0000.....01,即1，为真，count++；

当 i 为1时，1111......11&0000....10结果为0000....10,即2，为真，count++； . . . 最终结果为32

法三：利用算法去掉二进制中最右边的1

一个数字与上这个数字减一的数，该数二进制最右边的1必然会消除掉，以此类推，从右往左，每一次进行按位与操作，都会取消掉一个1，直到该数字变为0，跳出循环，就得到了该数字二进制中1的个数。 以3(0000...0011)为例： num： 0000...0011 —> 3 num - 1: 0000...0010 —> 2 num = 3 & 2: 0000...0010 —> 2 num - 1: 0000...0001 —> 1 num = 2 & 1: 0000...0000 —> 0 跳出循环

代码语言：javascript代码运行次数：0运行复制

#include <stdio.h>
int main()
{
	int num = -1;
    scanf("%d",&num);
	int i = 0;
	int count = 0; //计数
	while (num)
	{
		count++;
		num = num & (num - 1);
	}
	printf("⼆进制中1的个数 = %d\n", count);
	return 0;
}

已经到这里了，来道课外练习巩固吧!

课外练习1：用位运算判断一个数是否是2的次方数

先自己思考动动手，再来看把！

代码语言：javascript代码运行次数：0运行复制

#include <stdio.h>
int isPowerOfTwo(int n) 
{
	if (n <= 0) 
	{
		return 0;
	}
	return (n & (n - 1)) == 0;
}
int main()
{
	int num;
	scanf("%d", &num);
	if (isPowerOfTwo(num))
	{
		printf("%d 是2的次方数。\n", num);
	}
	else 
	{
		printf("%d 不是2的次方数。\n", num);
	}
	return 0;
}

简单分析：一个数如果是2的次方数，则它的二进制表示中只有一位是1，例如：1、2、4、8、16等。

课外练习2：编写代码将13二进制序列的第5位修改为1，然后再改回0

13的2进制序列： 00000000000000000000000000001101 将第5位置为1后：00000000000000000000000000011101 将第5位再置为0：00000000000000000000000000001101

同样的，还是要先自己练习了，再来看！

二进制序列的第n位修改为1的公式：a = a | (1 << n - 1)

分析：以a = a | (1 << n - 1)为例 设 a = 2 // 0000...0010

• （1 << i) ：1向左移动 i 位

当 n为1时，结果为0000......01； 当 n 为2时，1向左移动一位，最左边丢掉一位，右边补一个0，结果为0000.....10； 当 n 为3时，1左移两位，丢掉最左边两位，在最右边补两个0，结果为0000.......100 因此（1<<n - 1）产生的效果就是让数字1存储在内存中唯一的二进制位 1 移动 n - 1 位

• | 按位或运算符：对应二进制位有1，则1
• a |（1 << n - 1）：设n为3时，0000....010 | 0000....100结果为 0000....110，这样就把第i位改为1了

以此类推，二进制序列的第n位修改为0的公式：a = a & ~ (1 << n - 1)

代码：

代码语言：javascript代码运行次数：0运行复制

#include <stdio.h>
int main()
{
	int a = 13;
	a = a | (1 << 4);
	printf("a = %d\n", a);
	a = a & ~(1 << 4);
	printf("a = %d\n", a);
	return 0;
}

运行结果：

只有一点小小归纳，希望能帮到大家！ 如果大家发现知识点错误的话，请帮忙指出，十分感谢！！ 也请大家帮忙点赞、评论，这将督促我前行，大家一起加油！！！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-03-23，如有侵权请联系 cloudcommunity@tencent 删除前往查看二进制内存数据存储int

本文标签： 三种方法求一个整数存储在内存中二进制中的1的个数附两道课外练习题