【剑指offer】一个数的二进制序列中1的个数

朴灿烈づ我的快乐病毒、 2024-05-25 17:32 18阅读 0赞

## ✨前言✨： ##

**算法是一个程序员的内功，能很好的体现程序员的编程思维，通过学习和掌握常见的算法，不仅能提高coding能力，还能更加容易在笔面试中脱颖而出。本专栏将记录博主刷算法题的过程，不定期的会更新一些优质的算法题。如果对大家有帮助，别忘了三连支持哟！**

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

**目录**

✨前言✨：

✨题目描述✨

✨题目分析✨

具体思路讲解：

图解第二种算法

?代码示例?

?：算法1

?：算法2

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

## ✨题目描述✨ ##

> **?:**
> 
> ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16][]

**牛客网题目链接：[二进制中1的个数][1]**

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

## ✨题目分析✨ ##

### 具体思路讲解： ###

**?：这题在我们分析后会发现题目的难点在于，我们要如何在二进制补码序列中找到1并记录1的个数。在这里我提供两种算法来解决这个难点。**

**? 1：我们知道一个数按位与上1得到的结果是除最低位外其它位全部变成0，那么我们可以说一个数按位与上1得到的结果是最后1位，那么我们可以通过按位与操作与右移操作，将二进制序列的每一位都拿下来再判断是不是1即可解决问题。**

**2：我们知道二进制序列肯定会存在最后一个1，那么如果我让这个数减一，原来的最后一个1的位置上会变成0，而原本在这最后一个1后面为0的位置上会出现1，那么如果我让这个数按位与本身减一就会把最低位的1去掉，每一次进行这样的操作就会少一个1，同样的也能够计算出1的个数。**

###  ###

### 图解第二种算法 ###

> **?：图解**
> 
> ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

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

## **?**代码示例**?** ##

### ?：算法1 ###

#include<stdio.h>
    int main()
    {
    	int n = 0;
    	scanf("%d", &n);
    	int i = 0;
    	int count = 0;
    	while (i < 32)
    	{
    		if ((n >> i) & 1)//如果为真，说明拿到的是1
    		{
    			count++;
    		}
    		i++;
    	}
    	printf("二进制序列1的个数为:%d", count);
    	return 0;
    }

### ?：算法2 ###

#include<stdio.h>
    int main()
    {
    	int n = 0;
    	scanf("%d", &n);
    	int count = 0;
    	while (n)//n为0的时候说明1已经拿完了，循环终止
    	{
    		n &= (n - 1);
    		count++;
    	}
    	printf("二进制序列中1的个数：%d", count);
    	return 0;
    }

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

**以上代码，还可做优化在此仅作参考，若有更好的算法，还望能够私信告知，多谢各位。**

**由于本人水平十分有限，若有错误请即使告知！如果有帮助别忘了，万分感谢。**

**点赞? 收藏✨ 关注✌**

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/8fe684ca07b447aca75b185adf8b986f.png
[1]: https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&&tqId=11164&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/495321230b364bf8acb69b95f3e0697f.png