[数据结构与算法]一种新的高效的寻找字节最低非0位的有效算法

追逐梦想就是追逐自己的厄运，在满地都是六便士的街上，他抬起头看见了月光。

毛姆 --《月亮与六便士》

一、前言

该文章见github仓库：https://github.com/Eureka1024/An-effective-method-for-finding-the-lowest-non-0bit-bit-of-byte

本文目的是介绍一种新的查找字节最低非0位的算法，该算法比一般的位图算法更省空间，同时对于 32bit以及更长的字节，该算法查找字节最低非0位的实现路径也更加高效。

该算法的原理为：假设 X 为 uint32_t 类型的变量， 则 X & (X - 1) ^ X 的算式可以得到仅含字节最低非0位的结果，也就是将所有的可能转变为仅有的32种可能，也就是32个 “1在不同bit位” 的数，接着将这32个数对 37 取余，能够得到互不相同的结果，利用这些结果建立一个位图表，就能实现在O(1)的时间复杂度上查找到目标结果。

我们知道，一个无符号变量，从二进制的角度来看，是由一连串的 0 和 1组成。

以 8 位的字符型变量，是由 8 位的 0 或者 1组成，比如十进制中的 124，在二进制中的表示为 0b01111100（从最低位到最高位分别为 bit0 ~ bit7）。

在一些场景中，比如一些操作系统的调度算法，需要快速求取某个数的字节最低非 0 位，比如上文的 124，其字节最低非 0 位为 bit2，如何快速得到这个位置关系是本文要探讨的问题。

很容易想到使用循环来实现，一个个位检查就行了，但是这样的方法查找效率比较低，时间复杂度达到 O(n)。

在一些 RTOS 中，使用位图的方式，可以在 O(1)的时间复杂度下找到字节最低非0位。

以 RT-Thread 为例，其实现方式如下：

const rt_uint8_t rt_lowest_bitmap[] =
{
    /* 00 */ 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 10 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 20 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 30 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 40 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 50 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 60 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 70 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 80 */ 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 90 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* A0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* B0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* C0 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* D0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* E0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* F0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};

只要将所要求解的值作为这个数组的索引参数，即可得到对应的值。

比如 124，字节最低非 0 位为 bit2，则 rt_lowest_bitmap[124] 的值就是 2。

这种实现方法的好处是可以保证在 O(1)的时间复杂度下，求取目标值。但是这种采取空间换取时间的策略意味着需要大量的空间来制作这个位图表，尤其当变量的类型越来越大时，需要的空间在一些资源比较小的 CPU 中根本无法提供。比如 32bit的变量，需要的空间就高达 2^32 B = 4 GB的大小，如果是 64bit，那就更恐怖了。

本文试图提供一种兼具时间效率与空间效率的查找最低位 1 所处位置的方法。

二、一种新的查找字节最低非0位的方法

2.1、原理分析

这种方法其实也是使用位图的方式实现，算是一般位图算法的优化。

位图的查找效率已经非常高了，只能将优化的重点放在优化算法使用的空间。

位图的方式之所以需要那么多空间，是因为考虑了该变量的所有情况，比如一个无符号 8bit 字符型有 256 种情况，所以我们的位图就得需要 256B 的空间。

如何优化空间效率呢？

注意到这样一种情况， 0b01001100 和 0b11111100 的字节最低非 0 位的结果是相同的，其实也和 0b00000100 相同，其实算法的目的（求取字节最低非 0 位）已经告诉了我们一个突破点：我们只需要注意字节最低非 0 位即可。这样说来，上文的位图方法就存在使用查找空间冗余的情况。比如我使用 0b00000100 就可以覆盖所有 0bxxxxx100 (x 代表0或1) 的情况。

那么问题来了，如何实现将 0bxxxxx100 转化为 0b00000100 呢？

假设一个无符号的变量名为 value。

通过 value & (value-1) 可以将 value 中最右边的 1 消去，比如：

  0b01001100 & (0b01001100 - 1)
= 0b01001100 & 0b01001011
= 0b01001000

将所得的结果再与之前的值异或，即可得到仅剩字节最低非 0 位的情况，即

(res & (res-1)) ^ res

  (0b01001100 & (0b01001100 - 1)) ^ 0b01001100
= (0b01001100 & 0b01001011) ^ 0b01001100
=  0b01001000 
 ^ 0b01001100
=  0b00000100

即最终求得只有一个 1 的情况，利用这种方法，对于无符号字符型，就能够将所求取的情况由判断 256个数转换成判断 8 个数，如果是无符号32位变量，我们能够将 4,294,967,296 个数转换成判断 32个数，这样的差别实在是巨大的。

接下来的问题是如何让简化后要判断的数与字节最低非 0 位建立联系，同样想到使用位图的方式，如何建立位图？

以 8bit 无符号变量为例。

我们的目标是让 (res & (res-1)) ^ res 运算后的结果与字节最低非 0 位的数字建立联系，如下：

0b00000001 -> 1
0b00000010 -> 2
0b00000100 -> 3
0b00001000 -> 4
0b00010000 -> 5
0b00100000 -> 6
0b01000000 -> 7
0b10000000 -> 8

因为数组是连续的，如果我们直接使用运算之作为索引值来建立联系，那么空间就和上文提到的位图一样大了。

我们需要使用别的算式使运算结果坍缩到8附近即可。

想到常用的算式：取余操作。

我们对上表中的8个数对 11 进行取余操作，结果如下：

res = 1;
for (uint32_t i=0; i<SIZE; i++)
{
	a[i] = (res<<i)%11;
}

可以得到数组a的值为: 1,2,4,8,5,10,9,7。可以看到，这些数会不相同，可以用来建立联系：

	value		       	value%11
0b00000001 -> 1 	<-	1
0b00000010 -> 2		<-	2
0b00000100 -> 3		<-	4
0b00001000 -> 4		<-	8
0b00010000 -> 5		<-	5
0b00100000 -> 6		<-	10
0b01000000 -> 7		<-	9
0b10000000 -> 8		<-	7

我们可以利用这些数构造出新的位图：

const uint8_t lowest_bit_bitmap[] =
{
    /* #0   1   2   #3   4   */
       X,   1,  2,  X,   3,

	/* 5 	#6	7   8   9	10*/
       5,	X,	8,  4,  7, 	6
};

这个位图数组的大小为 11，所以会有三个成员是多余的（值为 X）。

所以最终得到求解 字节最低非 0 位 的算法如下：

const uint8_t lowest_bit_bitmap[] =
{
    /* #0   1   2   #3   4   */
       X,   1,  2,  X,   3,

	/* 5 	#6	7   8   9	10*/
       5,	X,	8,  4,  7, 	6
};

int tiny_ffs(uint8_t value)
{
    //res&(res-1）消去最右边的1
    //res^(res&(res-1)) 获取到仅剩最右边1的个数
    //结果对11取余，得到互不相等的数
    return __lowest_bit_bitmap[( (res & (res-1)) ^ res) % 11];
}

2.2、针对 16 bit 无符号整形变量

原理同2.1，取余的数为 19。

const uint8_t __lowest_bit_bitmap[] =
{
    /* 
    .......
    */
};

int tiny_ffs(uint16_t value)
{
    //res&(res-1）消去最右边的1
    //res^(res&(res-1)) 获取到仅剩最右边1的个数
    //结果对19取余，得到互不相等的数
    return __lowest_bit_bitmap[(res^(res&(res-1)))%19];
}

2.3、针对 32 bit 无符号整形变量

原理同2.1，取余的数为 37。

const uint8_t __lowest_bit_bitmap[] =
{
    /* 0    1   2   3   4   5   6   #7*/
       0,   1,  2,  27, 3,  24, 28, X,

    /* 8    9   10  11  12  13  #14  15*/
       4,   17, 25, 31, 29, 12, X,  14,

    /* 16   17  18  #19  20  21  22  23*/
       5,   8,  18, X,  26, 23, 32, 16,

    /* 24   25  26  27  #28  29  30  31*/
       30,  11, 13, 7,  X,  22, 15, 10,

    /* 32   33  34  35  36*/
       6,   21, 9,  20, 19
};

int tiny_ffs(uint32_t value)
{
    //res&(res-1）消去最右边的1
    //res^(res&(res-1)) 获取到仅剩最右边1的个数
    //结果对37取余，得到互不相等的数
    return __lowest_bit_bitmap[(res^(res&(res-1)))%37];
}

2.4、针对 64 bit 无符号整形变量

原理同2.1，取余的数为 67。

const uint8_t __lowest_bit_bitmap[] =
{
    /* 
    .......
    */
};

int tiny_ffs(uint64_t value)
{
    //res&(res-1）消去最右边的1
    //res^(res&(res-1)) 获取到仅剩最右边1的个数
    //结果对67取余，得到互不相等的数
    return __lowest_bit_bitmap[(res^(res&(res-1)))%67];
}