[c语言日寄]（bit）位检查—

哈喽大家好啊，在今天的快乐刷题中，我遇到了一个很有意思的题目：

题目

统计二进制中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及其右边的所有位都置为0count++;     // 计数器加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的个数，这使得该算法在时间复杂度上更加高效。

嘿嘿

今天的刷题分享就到这里~
通过这道题，我们深入探索了位运算的奥秘，从基础操作到高效算法。
希望这篇文章能让你在编程路上更进一步，在你下次遇到类似问题时，能轻松搞定。喜欢的话，别忘了点赞关注哦，我们下次再见！