如何求解一个无符号整形数是2的多少次方？

zbhddt6

就是一个unsigned整形数据只有一个bit位为1；求这个bit的位置；

问题背景，我用一个无符号整形数映射一个32个key值的使用情况；
现在需要求从后向前数，第一个0的bit位，用此bit生成一个特定的键值，键值本身有序；
所以我必须知道0bit位最低的那个字节，而且一定存在这个bit；

if (0xffffffff == unsignedi) return;

unsignedi = ~unsignedi;  转化为求从后向前数最低的一个为1的bit位；
unsignedj = unsignedi - (unsignedi & (unsignedi -1));
//如何继续进行计算unsignedj 对应bit的位置；------我不想一个一个bit找或者二分查找~~~
否则一开始就从后向前一个一个bit查找好的了~~~~~

bruceteen

你觉得 bsf bsr 这两个汇编指令怎么样？

假如你必须用C的话，可以折半查找，比如
((a&0xFFFF0000!=0) ? 16 : 0)
| ((a&0xFF00FF00!=0) ? 8 : 0)
| ((a&0xF0F0F0F0!=0) ? 4 : 0)
| ((a&0xCCCCCCC!=0) ? 2 : 0)
| ((a&0xAAAAAAAA!=0) ? 1 : 0)

sep

你觉得 bsf bsr 这两个汇编指令怎么样？

假如你必须用C的话，可以折半查找，比如
((a&0xFFFF0000!=0) ? ...
bruceteen 发表于 2010-08-01 10:45

    Mark

daybreakcx

1. #include <string.h>
   
2. int ffs(unsigned int i);

复制代码

这个可以不

bruceteen

这个可以不
daybreakcx 发表于 2010-08-01 11:23

类似于 _BitScanForward, _BitScanForward64 等其实就是 bsf 汇编指令，加上某个编译指令时，直接就用bsf替代了

zbhddt6

[quote]你觉得 bsf bsr 这两个汇编指令怎么样？

假如你必须用C的话，可以折半查找，比如
((a&0xFFFF0000!=0) ? ...
bruceteen 发表于 2010-08-01 10:45 [/quote]

蛮不错的，谢谢你；只是我不打算二分，也不打算一个一个找，就想看看有没有什么特殊的指令或者运算能达到此目的~~~~

zbhddt6

这个可以不
daybreakcx 发表于 2010-08-01 11:23

    就是为了效率，不会调用函数的，看来也只有汇编的效率要高的了，否则只能使用二分法~~~~~~~

daybreakcx

就是为了效率，不会调用函数的，看来也只有汇编的效率要高的了，否则只能使用二分法~~~~~~~
zbhddt6 发表于 2010-08-01 15:39

1. #ifndef _FFS_H_
   
2. #define _FFS_H_
   
3. 
   
4. /*
   
5. * A really hacky implementation copied from asm/bitops.h
   
6. * to make it compile
   
7. */
   
8. inline int ffs(int x)
   
9. {
   
10.         int r = 1;
    
11. 
    
12.         if (!x)
    
13.                 return 0;
    
14.         if (!(x & 0xffff)) {
    
15.                 x >>= 16;
    
16.                 r += 16;
    
17.         }
    
18.         if (!(x & 0xff)) {
    
19.                 x >>= 8;
    
20.                 r += 8;
    
21.         }
    
22.         if (!(x & 0xf)) {
    
23.                 x >>= 4;
    
24.                 r += 4;
    
25.         }
    
26.         if (!(x & 3)) {
    
27.                 x >>= 2;
    
28.                 r += 2;
    
29.         }
    
30.         if (!(x & 1)) {
    
31.                 x >>= 1;
    
32.                 r += 1;
    
33.         }
    
34.         return r;
    
35. }
    
36. 
    
37. #endif

复制代码

网上找的ffs的实现，个人觉得方法很巧，效率不错…………

zbhddt6

网上找的ffs的实现，个人觉得方法很巧，效率不错…………
daybreakcx 发表于 2010-08-01 15:57

    此二分法写的不错~~~~~~

davelv

你觉得 bsf bsr 这两个汇编指令怎么样？

假如你必须用C的话，可以折半查找，比如
((a&0xFFFF0000!=0) ? ...
bruceteen 发表于 2010-08-01 10:45

果真好指令