请选择 进入手机版 | 继续访问电脑版
查看: 585|回复: 8

记录几个简单算法,以后用的着

[复制链接]
  • TA的每日心情
    奋斗
    5 小时前
  • 签到天数: 1902 天

    [LV.Master]伴坛终老

    61

    主题

    1万

    帖子

    3

    版主

    Rank: 7Rank: 7Rank: 7

    积分
    16894
    最后登录
    2024-3-19
    发表于 2022-12-7 16:08:48 | 显示全部楼层 |阅读模式
    本帖最后由 流水源 于 2022-12-16 16:13 编辑

    最近项目有用到一些简单问题求解算法,下面就这些算法记录下来。

    1、计算一个32位bit长整型数中bit 1的个数。这个算法主要用于在某些情况下,通过置位1标识不同位置的有或无,然后统计标志位有或无的数量。
    假设32位数为0x00005555 = 0000 0000 0000 0000 0101 0101 0101 0101B,那么bit 1的个数为8。
    下面就如何用程序算法解决方式。
    首先想到的是通过右移,后 & 0x00000001。
    1. uint32_t GetBit1Count(uint32_t flag)
    2. {
    3.     uint32_t i,n;
    4.     for(i=0,n=0;i<32;i++)
    5.     {
    6.         if(flag & 0x00000001)    n++;
    7.     }
    8.     return n;
    9. }
    复制代码
    不过觉得上面这种方法不够优美,所以搜索了一下找到了另一种方法。这种方法比上一种更好的在于当bit 1的个数越少时,循环次数就少。
    计算如下:
    1. uint32_t GetBit1Count(uint32_t flag)
    2. {
    3.     uint32_t n;
    4.     while(flag)
    5.     {
    6.         flag &= (flag-1);
    7.         n++;
    8.     }
    9.     return n;
    10. }
    复制代码
    再增加一种方法。也比较巧妙,主要是相邻bit位相加。
    1. uint32_t GetBit1Count(uint32_t flag)
    2. {
    3.     flag = (flag &0x55555555) + ((flag >>1) &0x55555555) ;
    4.     flag = (flag &0x33333333) + ((flag >>2) &0x33333333) ;
    5.     flag = (flag &0x0f0f0f0f) + ((flag >>4) &0x0f0f0f0f) ;
    6.     flag = (flag &0x00ff00ff) + ((flag >>8) &0x00ff00ff) ;
    7.     flag = (flag &0x0000ffff) + ((flag >>16) &0x0000ffff) ;
    8.     return flag ;
    9. }
    复制代码
    解析如下图:
    QQ截图20221216161022.jpg


    2、查找一个32位bit长整型数中bit 1,或者bit 0在从低到高顺序中首先出现的位置;bit 1或bit 0从高到低顺序首先出现的位置。










    该会员没有填写今日想说内容.
    回复

    使用道具 举报

  • TA的每日心情
    慵懒
    4 小时前
  • 签到天数: 1460 天

    [LV.10]以坛为家III

    203

    主题

    2万

    帖子

    64

    超级版主

    Rank: 8Rank: 8

    积分
    91715
    最后登录
    2024-3-19
    发表于 2022-12-8 09:20:11 | 显示全部楼层
    这种基础性问题其实用汇编又好写,效率也高。
    不过用C语言还是更省事儿。
    该会员没有填写今日想说内容.
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    慵懒
    4 小时前
  • 签到天数: 1460 天

    [LV.10]以坛为家III

    203

    主题

    2万

    帖子

    64

    超级版主

    Rank: 8Rank: 8

    积分
    91715
    最后登录
    2024-3-19
    发表于 2022-12-8 09:44:28 | 显示全部楼层
    本帖最后由 stm1024 于 2022-12-8 09:59 编辑

    第二个我来抛砖引玉吧。

    1. /// @brief 从低位查找出现第1个0或者第一个1所在的位置
    2. /// @param n 待检测的数
    3. /// @param x 指定是查找0还是1
    4. /// @return 0或1所在的下标,如果不存在则返回-1
    5. int firstIdx(uint32_t n,uint8_t x)
    6. {
    7.     int ret=0;
    8.     if(x==0)
    9.     {
    10.         if(n==0xffffffff)return -1;
    11.         while(n & 1)
    12.         {
    13.             ret++;
    14.             n>>=1;
    15.         }
    16.         return ret;
    17.     }
    18.     else//x==1
    19.     {
    20.         if(n==0) return -1;
    21.         while(!(n & 1))
    22.         {
    23.             ++ret;
    24.             n>>=1;
    25.         }
    26.         return ret;
    27.     }
    28. }
    复制代码

    该会员没有填写今日想说内容.
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    慵懒
    4 小时前
  • 签到天数: 1460 天

    [LV.10]以坛为家III

    203

    主题

    2万

    帖子

    64

    超级版主

    Rank: 8Rank: 8

    积分
    91715
    最后登录
    2024-3-19
    发表于 2022-12-8 09:56:19 | 显示全部楼层
    统计1的个数,用while(n>0){n&=(n-1);count++;}
    该会员没有填写今日想说内容.
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    奋斗
    5 小时前
  • 签到天数: 1902 天

    [LV.Master]伴坛终老

    61

    主题

    1万

    帖子

    3

    版主

    Rank: 7Rank: 7Rank: 7

    积分
    16894
    最后登录
    2024-3-19
     楼主| 发表于 2022-12-8 10:14:04 | 显示全部楼层
    stm1024 发表于 2022-12-8 09:56
    统计1的个数,用while(n>0){n&=(n-1);count++;}

    大佬牛逼。我上面的居然没显示出来。
    该会员没有填写今日想说内容.
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    慵懒
    4 小时前
  • 签到天数: 1460 天

    [LV.10]以坛为家III

    203

    主题

    2万

    帖子

    64

    超级版主

    Rank: 8Rank: 8

    积分
    91715
    最后登录
    2024-3-19
    发表于 2022-12-8 16:09:55 | 显示全部楼层
    再来一个有意思的,字节按位逆序,例如01010011B ,把bit0/7交换,bit1/6交换,...,
    你可以先想一下再搜索。循环是入门级,不用循环有各种骚操作。
    该会员没有填写今日想说内容.
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    奋斗
    5 小时前
  • 签到天数: 1902 天

    [LV.Master]伴坛终老

    61

    主题

    1万

    帖子

    3

    版主

    Rank: 7Rank: 7Rank: 7

    积分
    16894
    最后登录
    2024-3-19
     楼主| 发表于 2022-12-8 18:14:42 | 显示全部楼层
    stm1024 发表于 2022-12-8 16:09
    再来一个有意思的,字节按位逆序,例如01010011B ,把bit0/7交换,bit1/6交换,...,
    你可以先想一下再搜索 ...

    不错不错,还有4字节高低字节交换,1->4,2->3交换。哈哈哈。
    我有空试试。
    该会员没有填写今日想说内容.
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    慵懒
    4 小时前
  • 签到天数: 1460 天

    [LV.10]以坛为家III

    203

    主题

    2万

    帖子

    64

    超级版主

    Rank: 8Rank: 8

    积分
    91715
    最后登录
    2024-3-19
    发表于 2022-12-8 18:17:25 | 显示全部楼层
    流水源 发表于 2022-12-8 18:14
    不错不错,还有4字节高低字节交换,1->4,2->3交换。哈哈哈。
    我有空试试。 ...

    嗯,是的,还有什么汉明距离等,关于位操作有很多有趣的代码
    该会员没有填写今日想说内容.
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    奋斗
    昨天 19:50
  • 签到天数: 2002 天

    [LV.Master]伴坛终老

    17

    主题

    4776

    帖子

    5

    金牌会员

    Rank: 6Rank: 6

    积分
    9775
    最后登录
    2024-3-18
    发表于 2022-12-9 21:46:31 | 显示全部楼层
    佩服,都是大佬。。。
    该会员没有填写今日想说内容.
    回复 支持 反对

    使用道具 举报

    您需要登录后才可以回帖 注册/登录

    本版积分规则

    关闭

    站长推荐上一条 /4 下一条

    Archiver|手机版|小黑屋|恩智浦技术社区

    GMT+8, 2024-3-19 15:16 , Processed in 0.133121 second(s), 28 queries , MemCache On.

    Powered by Discuz! X3.4

    Copyright © 2001-2021, Tencent Cloud.

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