有没有好的公式. 能得出 一个byte中哪一位是1 如 00000100 得出3,(第三位是1),

zx_wing

原帖由 cookis 于 2008-8-25 13:01 发表
我想要的是公式..
不想用函数或循环之类的方法.

一句话搞定的方法.

一句可以搞定的方法？有，x86下一条指令就可以了，'bsf xxx, xxx'
看看内核是怎么做的：
封装了一下：

1. 
   
2. static inline unsigned long __ffs(unsigned long word)
   
3. {
   
4.     if ( !word )
   
5.         return -1;
   
6. 
   
7.     asm("bsf %1,%0"
   
8.             : "=r" (word)
   
9.             : "rm" (word));
   
10. 
    
11.     return word;
    
12. }
    

复制代码

不用指令的方法，就不是一句了，当然你可以可以把它们写成一句，不过我想没有这么多一句就搞定的事情。

1. 
   
2. 
   
3. /**
   
4. * __ffs - find first bit in word.
   
5. * @word: The word to search
   
6. *
   
7. * Undefined if no bit exists, so code should check against 0 first.
   
8. */
   
9. static inline unsigned long __ffs(unsigned long word)
   
10. {
    
11.         int num = 0;
    
12. 
    
13. #if BITS_PER_LONG == 64
    
14.         if ((word & 0xffffffff) == 0) {
    
15.                 num += 32;
    
16.                 word >>= 32;
    
17.         }
    
18. #endif
    
19.         if ((word & 0xffff) == 0) {
    
20.                 num += 16;
    
21.                 word >>= 16;
    
22.         }
    
23.         if ((word & 0xff) == 0) {
    
24.                 num += 8;
    
25.                 word >>= 8;
    
26.         }
    
27.         if ((word & 0xf) == 0) {
    
28.                 num += 4;
    
29.                 word >>= 4;
    
30.         }
    
31.         if ((word & 0x3) == 0) {
    
32.                 num += 2;
    
33.                 word >>= 2;
    
34.         }
    
35.         if ((word & 0x1) == 0)
    
36.                 num += 1;
    
37.         return num;
    
38. }
    
39. 
    

复制代码

zx_wing

原帖由 jamesr 于 2008-8-27 09:31 发表

事实上已经实验过了。
对某一确定值进行多次这个运算，switch是>>速度的4倍；对随机生成值switch是>>速度的1.6倍（没有除去rand()所需时间，实际结果应该更好）。

这个主要取决于CPU流水线的长度，switch ...

switch这个方法不好，只适用于只有一个bit为1的情形，不通用。

zx_wing

原帖由 jamesr 于 2008-8-28 12:25 发表


楼主的要求就是这样的啊？

有多个bit为1的也可以用switch，返回第一个为1的bit号
参看17楼

看了，还是用了循环。
还是内核里面这个逻辑最简单

1. 
   
2. /**
   
3. * __ffs - find first bit in word.
   
4. * @word: The word to search
   
5. *
   
6. * Undefined if no bit exists, so code should check against 0 first.
   
7. */
   
8. static inline unsigned long __ffs(unsigned long word)
   
9. {
   
10.         int num = 0;
    
11. 
    
12. #if BITS_PER_LONG == 64
    
13.         if ((word & 0xffffffff) == 0) {
    
14.                 num += 32;
    
15.                 word >>= 32;
    
16.         }
    
17. #endif
    
18.         if ((word & 0xffff) == 0) {
    
19.                 num += 16;
    
20.                 word >>= 16;
    
21.         }
    
22.         if ((word & 0xff) == 0) {
    
23.                 num += 8;
    
24.                 word >>= 8;
    
25.         }
    
26.         if ((word & 0xf) == 0) {
    
27.                 num += 4;
    
28.                 word >>= 4;
    
29.         }
    
30.         if ((word & 0x3) == 0) {
    
31.                 num += 2;
    
32.                 word >>= 2;
    
33.         }
    
34.         if ((word & 0x1) == 0)
    
35.                 num += 1;
    
36.         return num;
    
37. }
    

复制代码