amobbs.com 阿莫电子技术论坛

标题: 精妙的算法3,4个循环就可以计算8位二进制中1的个数 [打印本页]

作者: cnxh 时间: 2022-8-16 22:38
标题: 精妙的算法3,4个循环就可以计算8位二进制中1的个数
本帖最后由 cnxh 于 2022-8-16 22:40 编辑

网上找的

如何计算二进制中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次~~~

真是太精妙啦~

作者: wye11083 时间: 2022-8-16 22:52
业内广泛使用popcnt算法：a=((a&0xaaaaaaaa)>>1)+(a&0x55555555);
下面的换成0xcccccccc,2,0x33333333
0xf0f0f0f0,4,0x0f0f0f0f,
0xff00ff00,8,0x00ff00ff,
0xffff0000,16,0x0000ffff。
这是计算32位popcnt。新cpu都有popcnt指令。。

作者: kv2004 时间: 2022-8-16 23:06
对于8位数，最多也要8个循环。

作者: tomzbj 时间: 2022-8-16 23:23
这个我算过, 链接: https://zhuanlan.zhihu.com/p/129377700
就不复制粘贴过来了.

8位的话, 感觉查表法应该能再快一点.

作者: 我是一个大白菜 时间: 2022-8-17 00:09
谢谢分享，学习了

作者: zdg102 时间: 2022-8-17 00:11
上大学时搞过ACM，这个小意思了。印象中还有个利用状态转移计算1个数的，效率更高。全忘光了。记得树状数组也有个类似的牛叉位运算，当年也是被震惊的不行

作者: jetbo 时间: 2022-8-17 01:10
计算1的个数有什么目的？

作者: 1a2b3c 时间: 2022-8-17 01:44

jetbo 发表于 2022-8-17 01:10
计算1的个数有什么目的？
(引用自7楼)

比如说，在一些资源或者类似的缺乏的地方，用每个bit表示有多少个状态，例如一个字节的8bit代表了8个故障信息，而不需要8个字节，而你需要对外提供你当前有多少个故障，那么就要看一下这个故障字节里面有多少个1了。
我只是简单的说明他的意义，并不需要来确定难道不能再找一个字节来表示故障个数吗？
当然可能还有其他的比如数学方面的用途，我就不得而知了，

作者: sunliezhi 时间: 2022-8-17 08:38
循环次数跟1的个数有关

作者: xuekcd 时间: 2022-8-17 13:16
单字节查表最好用了，四个字节就查四次相加

作者: dellric 时间: 2022-8-17 14:40
8位循环3次太多了，可以考虑4个位一组进行查表，这样两次就搞定，
如果是8位机，FLASH够多，直接8位查表，32位也只需要4次

作者: graycker 时间: 2022-8-17 19:50
确实很精妙，最近写个二进制平均分配算法，给定长度，设任意一个数都能以二进制形式平均分布，开始以为很简单，结果写了一天也没调好。

作者: cnxh 时间: 2022-8-18 07:17

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

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

作者: tang_qianfeng 时间: 2022-8-18 07:36
谢谢分享。

欢迎光临 amobbs.com 阿莫电子技术论坛 (https://www.amobbs.com/)