有时候用到位运算。需要快速找到一个整数的二进制第一个1或0在哪个位(下标)？例如：十进制数100的二进制是1100100，那么它的第一个1在下标 为2的位置(bsf, bit scan forward)或6的位置(bsr, bit scan in reverse order)，由于只用于存储一个状态，至于用bsf还是bsr则无所谓。

解决这个问题的第一个想法就是用内联汇编的做法，使用特别的CPU指令去找，但汇编的可移植性比较差，不同的CPU型号使用的指令可能不一样，执行速度也不一样。
假设找一个64位无符号整数二进制的第一个1，用bsf, AT& T汇编(gcc汇编)可以这样做：

 1 // bit scan forward for 64 bit integral number
 2 /* ============================================ */
 3 inline int bsf_asm (uint64_t w)
 4 {
 5   int x1, x2;
 6   asm ("bsf %0,%0\n" "jnz 1f\n" "bsf %1,%0\n" "jz 1f\n" "addl $32,%0\n"
 7      "1:": "=&q" (x1), "=&q" (x2):"1" ((int) (w >> 32)),
 8      "0" ((int) w));
 9   return x1;
10 }

如果用C来实现的话，那就有点麻烦了，在此不讲复杂的数学原理，仅仅给出代码。

 1 // bit scan forward for 64 bit integral number
 2 /* ============================================ */
 3 inline int bsf_folded (uint64_t bb)
 4 {
 5      static const int lsb_64_table[64] =
 6    {
 7       63, 30,  3, 32, 59, 14, 11, 33,
 8       60, 24, 50,  9, 55, 19, 21, 34,
 9       61, 29,  2, 53, 51, 23, 41, 18,
10       56, 28,  1, 43, 46, 27,  0, 35,
11       62, 31, 58,  4,  5, 49, 54,  6,
12       15, 52, 12, 40,  7, 42, 45, 16,
13       25, 57, 48, 13, 10, 39,  8, 44,
14       20, 47, 38, 22, 17, 37, 36, 26
15    };
16    unsigned int folded;
17    bb ^= bb - 1;
18    folded = (int) bb ^ (bb >> 32);
19    return lsb_64_table[folded * 0x78291ACF >> 26];
20 }

如果想从后往前搜索一个整数的二进制第一个1的下标，用汇编可以这样做。

 1 // bit scan in reverse order for 64 bit integral number
 2 /* ============================================ */
 3 inline int bsr_asm (uint64_t w)
 4 {
 5   int x1, x2;
 6   asm ("bsr %1,%0\n" "jnz 1f\n" "bsr %0,%0\n" "subl $32,%0\n"
 7      "1: addl $32,%0\n": "=&q" (x1), "=&q" (x2):"1" ((int) (w >> 32)),
 8      "0" ((int) w));
 9   return x1;
10 }

如果用C来实现的话，也比较简单，用divide and conquer 的原理就不会太慢。

 1 // a logn (n == 32)algorithm for bit scan in reverse order
 2 /* ============================================ */
 3 inline int bsr32(uint32_t bb)
 4 {
 5      static const char msb_256_table[256] =
 6    {
 7       0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
 8       4, 4, 4, 4, 4, 4, 4, 4,4, 4, 4, 4,4, 4, 4, 4,
 9       5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
10       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,
11       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,
12       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,
13       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,
14       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,
15       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,
16    };
17    int result = 0;
18 
19    if (bb > 0xFFFF)
20      {
21       bb >>= 16;
22       result += 16;
23    }
24    if (bb > 0xFF)
25      {
26       bb >>= 8;
27       result += 8;
28    }
29 
30    return (result + msb_256_table[bb]);
31 }
32 
33 /* ============================================ */
34 inline int bsr_in_C(uint64_t bb)
35 {
36   const uint32_t hb = bb >> 32;
37   return hb ? 32 + bsr32((uint32_t)hb) : bsr32((uint32_t)bb);
38 
39 }
40 

下面这个似乎也可以，失败时返回-1023，至于速度快慢就要看编译器的嗜好了。

 1 // bit scan in reverse order for 64 bit integral number
 2 /* ============================================ */
 3 inline int bsr_double (uint64_t bb)
 4 {
 5    union
 6    {
 7       double d;
 8       struct
 9       {
10          unsigned int mantissal : 32;
11          unsigned int mantissah : 20;
12          unsigned int exponent : 11;
13          unsigned int sign : 1;
14       };
15    } ud;
16    ud.d = (double)(bb & ~(bb >> 32));
17    return ud.exponent - 1023;
18 }
19