哈喽大家好啊，在今天的快乐刷题中，我遇到了一个很有意思的题目：
题目
统计二进制中1的个数
基本思路
没错……这道题的对象比较特殊。
不同于过去常见的题目，之前的题目的对象都是基本数据类型，而这道题的对象却是基本数据类型之下——bit，也就是位。
位（bit）
“bit”是“binary digit”的缩写，中文意思是位。它是计算机中表示数据的最小单位，每个0或1就是一个位，而8个bit组成一个字节（Byte）。
在C语言中，没有直接的bit型变量类型，但可以通过位域（bit fields）或位运算来模拟bit型变量的定义（通过结构体）。
想要进行对位的操作，就需要以位为对象的专用运算符。
常见位运算符
按位与（&）
功能：两个相应的二进制位都为1时，结果才为1，否则为0。按位或（|）
功能：两个相应的二进制位中只要有一个为1，结果就为1，否则为0。按位异或（^）
功能：两个相应的二进制位相异时，结果为1，相同则为0。
可以用于交换两个变量的值。
点击此处查看往期内容：整数交换的三种方式。按位取反（~）
功能：对二进制位取反，即0变1，1变0。左移（<<）
功能：将二进制位向左移动指定的位数，左边移出的位被丢弃，右边空出的位用0填充。
可以用于快速实现乘以2的幂次方的操作， x << n 相当于 x * 2^n。右移（>>）
功能：将二进制位向右移动指定的位数，对于无符号数，左边空出的位用0填充；对于有符号数，左边空出的位用符号位填充（即符号扩展）。
可以用于快速实现除以2的幂次方的操作，例如 x >> n 相当于 x / 2^n（对于无符号数）。
位运算在处理二进制数据时非常高效，能够直接对内存中的数据进行操作。
判断一个bit是否为1
要怎么样读取二进制的位数呢？
事实上，刚刚我们介绍的位运算符虽然能够对位进行操作，但是他们的对象依旧是基本数据类型。（A & B中，A、B都是基本数据类型）那到底要怎样实现遍历全部的bit呢？
答案是将bit的值用基本数据类型表示。
让我们看看下面这张图：
假如这张图代表一个二进制数据n，我们要做的事情是：
- 如果最后一个bit的值为1，那么这个数据用十进制的int表示为1。
- 反之，如果最后一个bit的值为0，那么这个数据用十进制的int表示为0.
十进制1和n的内存对比如下：
这时候，如果我们使用按位与（&）会怎么样？
没错！
n&1的值为1！
那如果最后一位为0呢？这时候我们再使用一次按位与（&）：
没错！是0！
使用按位与，我们可以实现判断最后一位是否为1
结合if，我们可以轻松实现这个判断：
if( n & 1 )
此时，我们实现了判断一个bit是否为1的程序。
遍历所有的bit
我们判断bit的条件是：这个bit是最后一位。
那么，我们只要每判断一次bit，我们把数据”往后移动一位“，就可以实现下一次判断的条件。
担当起这个任务的位运算符为: >>。
所谓右移运算符
右移运算符（>>）是一种位运算符，用于将一个数的二进制表示向右移动指定的位数。
- 基本概念
功能：将一个数的二进制位向右移动指定的位数，右边移出的位被丢弃，左边空出的位根据数的类型进行填充。
语法：number >> n，其中number是要进行右移操作的数，n是要移动的位数。 - 移动规则
对于无符号数：左边空出的位用0填充。例如，对于无符号整数10（二进制为 1010），10 >> 1的结果是5（二进制为101），左边空出的一位用0填充。
对于有符号数：左边空出的位用符号位（即最高位）填充，这种填充方式称为符号扩展。
例如，对于有符号整数-10（假设其二进制补码表示为11110110），-10 >> 1的结果是-5（二进制补码为11111011），左边空出的一位用符号位1填充。
具体实现
此时，我们只需建立这样一个语句，就可以轻松实现“往后移动一位”。
a = (unsigned int)a >> 1;
其中，（unsigned int）是强制类型转换，是确保左边空出的一位用0填充。
循环跳出方式
跳出循环？当全部的1都被“舍弃”，那么不就变成0了吗？使用while即可。
while (a != 0){}
全代码
我们将上面取得的成果全部结合起来，便得到了以下内容：
#include<stdio.h>
int sta_1(int a);
int main() {
int a = 0;
scanf_s("%d", &a);
printf("%d", sta_1(a));
return 0;
}
int sta_1(int a) {
int num = 0;
while (a != 0) {
if (a & 1) num++;
a = (unsigned int)a >> 1;
}
return num；
}
以上，是该题的一般解法。
但是，不要小看我和题目的羁绊啊喂！
Brian Kernighan算法
Brian Kernighan算法专门计算二进制中1的个数的算法。
内容
int countBits(int n) {
int count = 0;
while (n != 0) {
n &= n - 1; // 将n中最右边的1及其右边的所有位都置为0
count++; // 计数器加1
}
return count;
}
基本思想
利用n & (n-1)操作来消除一个整数n的二进制表示中最右边的1。
具体步骤
初始化一个计数器count为0。
当n不等于0时，执行以下操作：
执行n &= n-1，将n中最右边的1及其右边的所有位都置为0。
将计数器count加1。
返回计数器count的值，即二进制表示中1的个数。
辅助理解
对于循环退出条件：如果一个整数不为0，那么这个整数至少有一位是1。
对于n-1：如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
例子
对于整数n=7，其二进制表示为111：
- 第一次循环：n=7 & 6=6，count=1，此时n的二进制表示为110；
- 第二次循环：n=6 & 5=4，count=2，此时n的二进制表示为100；
- 第三次循环：n=4 & 3=0，count=3，此时n变为0，循环结束。
最终，count的值为3，即n的二进制表示中有3个1。
该算法的优势在于，它只需要执行与1的个数相等的循环次数，即执行次数等于二进制表示中1的个数，这使得该算法在时间复杂度上更加高效。
嘿嘿
今天的刷题分享就到这里~
通过这道题，我们深入探索了位运算的奥秘，从基础操作到高效算法。
希望这篇文章能让你在编程路上更进一步，在你下次遇到类似问题时，能轻松搞定。喜欢的话，别忘了点赞关注哦，我们下次再见！