删繁就简--0 bit位置查找

白丁

删繁就简--0 bit位置查找 [复制链接]

具体背景就不说了，有这么一种需求就是从一个32bit DWORD中找出第一个0的位置，从高位开始找或者从低位开始找
从高位开始查找如下：

1. unsigned int bit0search_msb(unsigned int x)
   
2. {
   
3.     unsigned int pos = 0;
   
4.     if(0xffffffff == x)
   
5.     {
   
6.         return 0xffffffff;
   
7.     }
   
8.     if(0xffff0000 != (x & 0xffff0000))
   
9.     {
   
10.         x >>= 16;
    
11.         pos += 16;
    
12.     }
    
13.     if(0xff00 != (x & 0xff00))
    
14.     {
    
15.         x >>= 8;
    
16.         pos += 8;
    
17.     }
    
18.     if(0xf0 != (x & 0xf0))
    
19.     {
    
20.         x >>= 4;
    
21.         pos += 4;
    
22.     }
    
23.     if(0xc != (x & 0xc))
    
24.     {
    
25.         x >>= 2;
    
26.         pos += 2;
    
27.     }
    
28.     if(0x2 != (x & 0x2))
    
29.     {
    
30.         pos += 1;
    
31.     }
    
32. 
    
33.     return pos;
    
34. }
    

复制代码

从地位开始查找如下：

1. unsigned int bit0search_lsb(unsigned int x)
   
2. {
   
3.     unsigned int pos = 0;
   
4.     if(0xffffffff == x)
   
5.     {
   
6.         return 0xffffffff;
   
7.     }
   
8.     if(0xffff  == (x & 0xffff))
   
9.     {
   
10.         x >>= 16;
    
11.         pos += 16;
    
12.     }
    
13.     if(0xff == (x & 0xff))
    
14.     {
    
15.         x >>= 8;
    
16.         pos += 8;
    
17.     }
    
18.     if(0xf == (x & 0xf))
    
19.     {
    
20.         x >>= 4;
    
21.         pos += 4;
    
22.     }
    
23.     if(0x3 == (x & 0x3))
    
24.     {
    
25.         x >>= 2;
    
26.         pos += 2;
    
27.     }
    
28.     if(0x1 == (x & 0x1))
    
29.     {
    
30.         pos += 1;
    
31.     }
    
32.     return pos;
    
33. }
    

复制代码

以上两段代码都是采用的二分法进行查找，为了验证该算法是否正确，与遍历bit方法进行对比

1. unsigned int bit0check_msb(unsigned int x)
   
2. {
   
3.     unsigned int i;
   
4.     for(i=31; i>=0; i--)
   
5.     {
   
6.         if(0 == ((x >> i) & 0x1))
   
7.         {
   
8.             return i;
   
9.         }
   
10.     }
    
11. 
    
12.     return 0xffffffff;
    
13. }
    
14. unsigned int bit0check_lsb(unsigned int x)
    
15. {
    
16.     unsigned int i;
    
17.     for(i=0; i<32; i++)
    
18.     {
    
19.         if(0 == ((x >> i) & 0x1))
    
20.         {
    
21.             return i;
    
22.         }
    
23.     }
    
24.     return 0xffffffff;
    
25. }
    
26. int main(void)
    
27. {
    
28.     unsigned int pos, pos1;
    
29.     unsigned int i;
    
30.     for(i=0; i<0xffffffff; i++)
    
31.     {
    
32.         pos = bit0search_lsb(i);
    
33.         pos1 = bit0check_lsb(i);
    
34.         if(pos != pos1)
    
35.         {
    
36.             printf("error!!!  i %d, pos %d, pos1 %d\n", i, pos, pos1);
    
37.             return -1;
    
38.         }
    
39.     }
    
40.     printf("all right\n");
    
41.     return 0;
    
42. }

复制代码

yl20084784

楼主，你这个程序在实际运行当中会有问题，虽然我不知道你具体的应用环境，如果数据出错成二进制00001011的样子，如果用等于判断1111就会出错，还是用大于，或者不小于什么的吧

白丁

yl20084784 发表于 2016-9-22 22:52
楼主，你这个程序在实际运行当中会有问题，虽然我不知道你具体的应用环境，如果数据出错成二进制00001011的 ...

不是很明白你的意思啊？这个我做过遍历的对比测试了没有问题啊，只要是32为无符号都没有问题啊

weizhongc

感觉不知道什么条件下需要， 没用过找bit位的

bobde163

楼主有测过哪个算法的效率更高吗，从代码量上看，逐位查找要更简洁明了，而二分法没有循环，代码复杂，执行效率可能更高，不知道效率怎么样