首页 > 代码库 > 位运算应用

位运算应用

2024-07-02 10:04:30   227人阅读

问题描述：

　　　　输入一个整数，返回其二进制表示中最低的一位为1的下标值。

　　　　很多CPU都在硬件层面直接提供该指令，例如，i386的BSF指令。但是，如果硬件没有提供该指令，又当如何。来看kernel中的算法：

　　　　应用分治思想进行依序判断.....

 1 int __ffs(int x)
 2 {
 3     int r = 0;　　　　　　　　　　//r：用来标记下标，初始化为0。
 4     
 5     if (!x)
 6         return 0;
 7     if (!(x & 0xffff)) {　　　　 //即0 1111 1111 1111 1111
 8         x >>= 16;
 9         r += 16;
10     }
11     if (!(x & 0xff)) {　　　　　　//即0 1111 1111
12         x >>= 8;
13         r += 8;
14     }
15     if (!(x & 0xf)) {　　　　　　 //即0 1111
16         x >>= 4;
17         r += 4;
18     }
19     if (!(x & 3)) {　　　　　　　　//0x03————即0011
20         x >>= 2;
21         r += 2;
22     }
23     if (!(x & 1)) {　　　　　　　　//0x01
24         x >>= 1;
25         r += 1;
26     }
27     return r;
28 }

 


联系
我们