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

retuor

插值

(x==1)*1+(x==2)*2+(x==4)*3+(x==8)*4+(x==16)*5+(x==32)*6+(x==64)*7+(x==128)*8

huangwei0413

原帖由 zx_wing 于 2008-8-25 13:32 发表

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

static inline unsigned long __ffs(unsigned long word)
{
    if ( !word )
        return - ...

内核的代码就是写得好，很值得学习！

huangwei0413

原帖由 emacsnw 于 2008-8-25 13:50 发表
这个如何？呵呵。


int foo[256];
foo[1] = 1; foo[2] = 2; foo[4] = 3; foo[8] = 4;
foo[16] = 5; foo[32] = 6; foo[64] = 7; foo[128] = 8;

int locate_set_bit(int x) {
  return foo[x];
}

如何减少空间的损耗？

cookis

原帖由 retuor 于 2008-8-25 13:55 发表
插值

(x==1)*1+(x==2)*2+(x==4)*3+(x==*4+(x==16)*5+(x==32)*6+(x==64)*7+(x==12*8

这个有创意..

cookis

static inline unsigned long __ffs(unsigned long word)
{
    if ( !word )
        return -1;

    asm("bsf %1,%0"
            : "=r" (word)
            : "rm" (word));

    return word;
}

这个好是好.. 不过本人不懂汇编. 不敢用啊.

jamesr

最好的就是依次与0x1,0x2,0x4,0x8,0x10,0x20,0x4,0x80比较，成功就返回对应结果。
平均只需比较４次，读一次内存。类似与查表，但这个表在指令的立即数里。

Roemer

原帖由 huangwei0413 于 2008-8-25 14:36 发表


如何减少空间的损耗？

hash table

feeling

直接给出对应公式即可，不就是8种情况嘛

yecheng_110

二分法就行了吧

1. 
   
2. int get_byte_bit(int x){
   
3.     static int arr[8] = {1,2,4,8,16,32,64,128};
   
4.     int low;
   
5.     int high;
   
6.     int index;
   
7. 
   
8.     low = 0;
   
9.     high = 7;
   
10.     do{
    
11.         index = (low + high) / 2;
    
12.         if(arr[index] == x){
    
13.             return index + 1;
    
14.         }
    
15.         if(arr[index] > x){
    
16.             high = index - 1;
    
17.         }
    
18.         else {
    
19.             low = index + 1;
    
20.         }
    
21.     }while(low <= high);
    
22. 
    
23.     return -1;
    
24. }
    

复制代码

[ 本帖最后由 yecheng_110 于 2008-8-25 18:05 编辑 ]

cookis

呵呵..算法用得不错..