精妙的算法3,4个循环就可以计算8位二进制中1的个数

cnxh

网上找的

如何计算二进制中1的个数？

全部遍历一遍？

不……不……这不是最优解……

下面看一段代码：

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

太巧啦~

刚看到这个代码的时候，觉得这个解法真是太巧啦、太精妙啦（不要怪我没见过世面 ）~

下面我们来理解一下这个代码，这个代码中核心的代码只有一行，就是 n &= (n - 1) ，我们分开看一下：
1. n-1：一个二进制的数减1，就是将这个二进制最右边的那个1变成0，然后它后边的所有位置都变成1~ 举例：0011 0100，减1(n-1)后变成：0011 0011。
2. n &= (n-1)，并操作就会将有0的位置都变成0，上面的例子的结果就是0011 0000，然后再赋值给n，这时n就去掉了一个1，或者叫做计数了一个1。以此类推，就可以得到1的个数。

0011 0100 - 1 = 0011 0011   
0011 0100 & 0011 0011 = 0011 0000  // 计数一个1
0011 0000 - 1 = 0010 1111
0011 0000 & 0010 1111 = 0010 0000  // 计数两个1
0010 0000 - 1 = 0001 1111
0010 0000 & 0001 1111 = 0000 0000  // 计数三个1，程序停止

这样只需要循环3次，而如果直接遍历就会循环6次，性能明显提高啦~

给个极端的例子 1000 0000，这个直接遍历得遍历8次，而通过上面的代码只需要遍历

1次~1次~~1次~~~

真是太精妙啦~

cnxh

1a2b3c 发表于 2022-8-17 01:44
比如说，在一些资源或者类似的缺乏的地方，用每个bit表示有多少个状态，例如一个字节的8bit代表了8个故障 ...
(引用自8楼)

现在用串口模拟发送,需要校验位计算