位运算应用之一——最低位为1的下标

问题描述：

　　　　输入一个整数，返回其二进制表示中最低的一位为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 }

附注：

 1 /*
 2 *描述：输入一个整数，返回其二进制表示中最低的一位为1的下标值。
 3 *分析：利用分治思想依序判断（移位判断）
 4 *BY： xymaqingxiang
 5 *Time：2014-05-01
 6 */
 7 #include <stdlib.h>
 8 #include <stdio.h>
 9 #include <windows.h>
10 int ffs(int x)
11 {
12     int r = 0;//r：用来标记下标，初始化为0。
13     
14     if (!x)
15         return 0;
16     if (!(x & 0xffff)) {    //即0 1111 1111 1111 1111
17         x >>= 16;
18         r += 16;
19     }
20     if (!(x & 0xff)) {        //即0 1111 1111
21         x >>= 8;
22         r += 8;
23     }
24     if (!(x & 0xf)) {        //即0 1111
25         x >>= 4;
26         r += 4;
27     }
28     if (!(x & 3)) {        //0x03————即0011
29         x >>= 2;
30         r += 2;
31     }
32     if (!(x & 1)) {//0x01
33         x >>= 1;
34         r += 1;
35     }
36     return r;
37 }
38 
39 void main()
40 {
41     int r;
42     int x;
43     printf("please input the x : 
");
44     scanf("%d",&x);
45     r=ffs(x);
46     printf("%d",r);
47     Sleep(100000);
48 
49 }

具体代码实现