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

ahui886

glibc 的一个ffs实现

1. int ffs ( int i)
   
2. {
   
3.   static const unsigned char table[] =
   
4.     {
   
5.       0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
   
6.       6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
   
7.       7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
   
8.       7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
   
9.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
   
10.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    
11.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    
12.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
    
13.     };
    
14.   unsigned int a;
    
15.   unsigned int x = i & -i;
    
16. 
    
17.   a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ?  16 : 24);
    
18. 
    
19.   return table[x >> a] + a;
    
20. }

复制代码

zylthinking

mark

zhangsuozhu

如果只有一个bit位为1可以省一步运算 unsigned int x = i & -i;

1. 
   
2. unsigned int ffs(unsigned i)
   
3. {
   
4.   static const unsigned char table[] =
   
5.     {
   
6.       0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
   
7.       6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
   
8.       7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
   
9.       7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
   
10.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    
11.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    
12.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    
13.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
    
14.     };
    
15. 
    
16.   int x = i <= 0xffff ? (i <= 0xff ? 0 : 8) : (i <= 0xffffff ?  16 : 24);
    
17.   return table[i>>x]+x;
    
18. }
    

复制代码

davelv

如果只有一个bit位为1可以省一步运算 unsigned int x = i & -i;
zhangsuozhu 发表于 2010-08-02 14:49

这个的结果是 x==i

看错了，抱歉。