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

流水源

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

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. }

复制代码

解析如下图：



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

阅读全文

stm1024

这种基础性问题其实用汇编又好写，效率也高。
不过用C语言还是更省事儿。

stm1024

第二个我来抛砖引玉吧。

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. }

复制代码

stm1024

统计1的个数，用while(n>0){n&=(n-1);count++;}

流水源

stm1024 发表于 2022-12-8 09:56
统计1的个数，用while(n>0){n&=(n-1);count++;}

大佬牛逼。我上面的居然没显示出来。

stm1024

再来一个有意思的，字节按位逆序，例如01010011B ，把bit0/7交换，bit1/6交换，...，
你可以先想一下再搜索。循环是入门级，不用循环有各种骚操作。

流水源

stm1024 发表于 2022-12-8 16:09
再来一个有意思的，字节按位逆序，例如01010011B ，把bit0/7交换，bit1/6交换，...，
你可以先想一下再搜索 ...

不错不错，还有4字节高低字节交换，1->4,2->3交换。哈哈哈。
我有空试试。

stm1024

流水源 发表于 2022-12-8 18:14
不错不错，还有4字节高低字节交换，1->4,2->3交换。哈哈哈。
我有空试试。 ...

嗯，是的，还有什么汉明距离等，关于位操作有很多有趣的代码

超級稻草人

佩服，都是大佬。。。