查找一个64位整数二进制第一个1

有时候用到位运算。需要快速找到一个整数的二进制第一个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

以上uint64_t和uint32_t是新C++标准可以支持的整型，分别相当于旧的unsigned long long和unsigned long类型。以上代码不是我的原创，而是来自国外某位朋友，我稍微加工了一下贴到这里，版权属于原作者，如果我没有记错的话应该是GNU。

补充：软件开发 , C语言 ,