搜索
bottom↓
回复: 18

【求助】计算字节中1的个数

[复制链接]

出0入4汤圆

发表于 2022-11-3 20:44:07 | 显示全部楼层 |阅读模式
ARM 中, 我记得有条指令,可以直接求出字节中1的个数,不必一位一位查。还有第1次出现的1出现在第几位。

阿莫论坛20周年了!感谢大家的支持与爱护!!

一只鸟敢站在脆弱的枝条上歇脚,它依仗的不是枝条不会断,而是自己有翅膀,会飞。

出0入442汤圆

发表于 2022-11-3 20:53:53 来自手机 | 显示全部楼层
你可能记错了?x86有popcnt,bitscanforward/bitscanreverse。

出200入2554汤圆

发表于 2022-11-3 20:57:44 | 显示全部楼层
只有字节的话,用查表(size=256)岂不更快

出0入4汤圆

 楼主| 发表于 2022-11-3 21:00:48 | 显示全部楼层
两位大神,真有的,我忘记了,因为不怎么用

出0入0汤圆

发表于 2022-11-3 21:10:29 | 显示全部楼层
ARM-M3内核没有求出1的个数的指令,有计算前导0的数目指令

出200入2554汤圆

发表于 2022-11-3 21:11:39 | 显示全部楼层
SCREA 发表于 2022-11-3 21:00
两位大神,真有的,我忘记了,因为不怎么用
(引用自4楼)

查了下 M3 内核的指令表(thumb),只有一个 CLZ 指令满足类似的要求,计算前导0个数。
高级的 ARM 应该会有更具体的计数指令,不过没玩过也没具体手册...



本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x

出0入85汤圆

发表于 2022-11-3 21:13:28 | 显示全部楼层
软件实现的话,可以看看《高效算法的奥秘》中的第5章

出0入4汤圆

 楼主| 发表于 2022-11-3 21:22:04 | 显示全部楼层
谢谢楼上各位老师,哪天我想起来补上。 之前在IAR中找见的,也可能是IAR自带的库。

出0入8汤圆

发表于 2022-11-4 09:19:13 | 显示全部楼层
SCREA 发表于 2022-11-3 21:22
谢谢楼上各位老师,哪天我想起来补上。 之前在IAR中找见的,也可能是IAR自带的库。 ...
(引用自8楼)

CLZ 指令倒是见过,其他的就没见过了,
先占个位置听课。

出0入309汤圆

发表于 2022-11-4 09:58:43 | 显示全部楼层
本帖最后由 iamseer 于 2022-11-4 10:00 编辑

https://developer.arm.com/docume ... f-instructions/VCNT

需要支持neon才行,一般A系列的ARM上有,cortex-M没有。

出0入475汤圆

发表于 2022-11-4 16:51:40 来自手机 | 显示全部楼层
不是有个帖子专门讨论过这个吗?就是弄个一个简单的算法,可以只需要几步就得到结果,比通用的轮询和查表都快一些,

出0入0汤圆

发表于 2022-11-4 17:07:18 | 显示全部楼层
printf("%u\n", a ^ (a - 1));

出0入475汤圆

发表于 2022-11-4 22:51:14 来自手机 | 显示全部楼层
sbusr 发表于 2022-11-4 17:07
printf("%u\n", a ^ (a - 1));
(引用自12楼)

别欺负我没学过C语言,我可也是自学了if else 的:)

a=2时结果是多少?难道 =3吗?等于255时结果是多少?难道等于1吗?

出0入0汤圆

发表于 2022-11-5 12:05:48 | 显示全部楼层
本帖最后由 sbusr 于 2022-11-5 12:45 编辑
1a2b3c 发表于 2022-11-4 22:51
别欺负我没学过C语言,我可也是自学了if else 的:)

a=2时结果是多少?难道 =3吗?等于255时结果是多少 ...
(引用自13楼)


我记错了,是有个什么类似的算法的……

补充:
https://blog.csdn.net/weixin_67711401/article/details/123339380
下面这个应该是相对快的算法
int NumberOf1(int n)
{
        int count = 0;
        while (n)
        {
                n = n & (n - 1);
                count++;
        }
        return count;
}

出0入475汤圆

发表于 2022-11-5 13:03:11 来自手机 | 显示全部楼层
sbusr 发表于 2022-11-5 12:05
我记错了,是有个什么类似的算法的……

补充:

(引用自14楼)

你这个验证没有计算FF最快几个循环?我是看不懂,就是和8个循环相比
之前有个帖子,专门讨论这个,印象中好像是说最多只要4个循环,所以当时觉得是最优的,

出0入0汤圆

发表于 2022-11-5 16:04:15 | 显示全部楼层
之前讨论的帖子:https://www.amobbs.com/thread-5769455-1-1.html

出50入58汤圆

发表于 2022-11-5 16:11:35 | 显示全部楼层
  1. /*
  2. *********************************************************************************************************
  3. *                                                uC/OS-II
  4. *                                          The Real-Time Kernel
  5. *                                             CORE FUNCTIONS
  6. *
  7. *                              (c) Copyright 1992-2012, Micrium, Weston, FL
  8. *                                           All Rights Reserved
  9. *
  10. * File    : OS_CORE.C
  11. * By      : Jean J. Labrosse
  12. * Version : V2.92.07
  13. *
  14. * LICENSING TERMS:
  15. * ---------------
  16. *   uC/OS-II is provided in source form for FREE evaluation, for educational use or for peaceful research.
  17. * If you plan on using  uC/OS-II  in a commercial product you need to contact Micrium to properly license
  18. * its use in your product. We provide ALL the source code for your convenience and to help you experience
  19. * uC/OS-II.   The fact that the  source is provided does  NOT  mean that you can use it without  paying a
  20. * licensing fee.
  21. *********************************************************************************************************
  22. */

  23. #define  MICRIUM_SOURCE

  24. #ifndef  OS_MASTER_FILE
  25. #define  OS_GLOBALS
  26. #include <ucos_ii.h>
  27. #endif

  28. /*
  29. *********************************************************************************************************
  30. *                                      PRIORITY RESOLUTION TABLE
  31. *
  32. * Note: Index into table is bit pattern to resolve highest priority
  33. *       Indexed value corresponds to highest priority bit position (i.e. 0..7)
  34. *********************************************************************************************************
  35. */

  36. INT8U  const  OSUnMapTbl[256] = {
  37.     0u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x00 to 0x0F                   */
  38.     4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x10 to 0x1F                   */
  39.     5u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x20 to 0x2F                   */
  40.     4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x30 to 0x3F                   */
  41.     6u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x40 to 0x4F                   */
  42.     4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x50 to 0x5F                   */
  43.     5u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x60 to 0x6F                   */
  44.     4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x70 to 0x7F                   */
  45.     7u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x80 to 0x8F                   */
  46.     4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x90 to 0x9F                   */
  47.     5u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0xA0 to 0xAF                   */
  48.     4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0xB0 to 0xBF                   */
  49.     6u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0xC0 to 0xCF                   */
  50.     4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0xD0 to 0xDF                   */
  51.     5u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0xE0 to 0xEF                   */
  52.     4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u  /* 0xF0 to 0xFF                   */
  53. };
复制代码


第二个问题:UCOS-II中是查表

出15入178汤圆

发表于 2022-11-5 16:58:40 | 显示全部楼层
稍微相关的有:
CLZ: Count Leading Zeroes.

出0入71汤圆

发表于 2022-11-6 10:51:32 | 显示全部楼层
这位同学准备在程序中准备祭出汇编了么?如果被BOSS逼这么厉害,换个高速单片机用C语言查表可以吧
回帖提示: 反政府言论将被立即封锁ID 在按“提交”前,请自问一下:我这样表达会给举报吗,会给自己惹麻烦吗? 另外:尽量不要使用Mark、顶等没有意义的回复。不得大量使用大字体和彩色字。【本论坛不允许直接上传手机拍摄图片,浪费大家下载带宽和论坛服务器空间,请压缩后(图片小于1兆)才上传。压缩方法可以在微信里面发给自己(不要勾选“原图),然后下载,就能得到压缩后的图片】。另外,手机版只能上传图片,要上传附件需要切换到电脑版(不需要使用电脑,手机上切换到电脑版就行,页面底部)。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

手机版|Archiver|amobbs.com 阿莫电子技术论坛 ( 粤ICP备2022115958号, 版权所有:东莞阿莫电子贸易商行 创办于2004年 (公安交互式论坛备案:44190002001997 ) )

GMT+8, 2024-3-29 08:29

© Since 2004 www.amobbs.com, 原www.ourdev.cn, 原www.ouravr.com

快速回复 返回顶部 返回列表