【位操作笔记】计算以2为底整数N的对数 查表法

计算以2为底整数N的对数$lo{g}_{2}N$ 查表法

用于计算以2为底整数N的对数$lo{g}_{2}N$。例如 $lo{g}_{2}8=3$，$lo{g}_{2}16=4$。

算法说明

该算法通过查表的方式来计算以2为底整数N的对数$lo{g}_{2}N$。以2为底整数N的对数$lo{g}_{2}N$，与最高有效位(most significant bit set，MSB)的位置相同，例如4 = 0x4 = 0b0100，最高有效位在第2位，与$lo{g}_{2}4=2$值相等。然后通过查表的方式来计算最高有效位在第几位。32 bit 数最多有 4294967296 种情况，所以生成 32 位数的表来进行查表是不合适的，由于 8 bit 数最多只有 256 个，也就是最多只有 256 种情况，所以通过建 8 bit 数表的方式，然后根据要计算的数的最高有效位在哪个区间，分成 4 种情况来查表计算 $lo{g}_{2}N$ 的值。四个区间分别为0 - 7 bit，8 - 15 bit， 16 - 23 bit， 24 - 31 bit 四个区间，我们只计算这 8 bit数的最高有效位是多少，然后将计算值加上对应区间的偏移值 0， 8， 16， 24，得到实际的最高有效位在第几位，也就得到了$lo{g}_{2}N$。

实现代码

实现方式为：

static const char LogTable256[256] =
{
    -1,
    0,
    1, 1,
    2, 2, 2, 2,
    3, 3, 3, 3, 3, 3, 3, 3,
    4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
    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,
    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, 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,
    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, 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, 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, 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
};

unsigned int bit_log2(unsigned int val)
{
    unsigned int ret;
    unsigned int tmpval1, tmpval2;

    if ((tmpval2 = (val >> 16)))
    {
        ret = (tmpval1 = tmpval2 >> 8) ? 24 + LogTable256[tmpval1] : 16 + LogTable256[tmpval2];
    }
    else 
    {
        ret = (tmpval1 = val >> 8) ? 8 + LogTable256[tmpval1] : LogTable256[val];
    }
    
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

注意，如果传入的参数val不是2的次幂，则返回值是val的值向下舍入到最近的2的次幂的对数值。例如 val的值为10，则返回值为$lo{g}_{2}10=3$。

测试程序：

int main(int argc, char* argv[])
{
    printf("%d\n", bit_log2(32));
    printf("%d\n", bit_log2(16));
    printf("%d\n", bit_log2(8));
    printf("%d\n", bit_log2(10));
    printf("%d\n", bit_log2(20));
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10

运行结果如下：

5
4
3
3
4
1
2
3
4
5

算法计算过程

该算法通过查表的方式来计算以2为底32 bit整数N的对数$lo{g}_{2}N$。根据要计算的数最高有效位在哪个范围，分成 4 种情况来查表计算 $lo{g}_{2}N$ 的值。

第一步，判断要计算的32 bit 整数的高16位(16 - 31 bit)是否有值，有值的话进入第二步，没有的话进入第三步

第二步，判断要计算的数是高8位(24 - 31 bit)是否有值，有值的话将这 8 bit 数进行查表计算，得到的值加上偏移值 24 得到实际的最高有效位；如果高8位(24 - 31 bit)没有值，则将低8位(16 - 23 bit)这 8 bit 数进行查表计算，得到的值加上偏移值 16 得到最高有效位。

第三步，判断要计算的数是32 bit 数的低16位中的高8位(8 - 15 bit)是否有值，有值的话将这 8 bit 数进行查表计算，得到的值加上偏移值 8 得到最高有效位；如果高8位(8 - 15 bit)没有值，则将低8位(0 - 7 bit)这 8 bit 数进行查表计算直接得到最高有效位。

计算示例

例如：

val = 16 = 0x10 = 0b10000，最高有效位在第4位，所以$lo{g}_{2}16=4$。

模拟这个计算的过程：

0b10000 >>= 16	=>	tmpval2 = 0

高16位(16 - 31 bit)没有值

0b10000 >>= 8	=>	tmpval1 = 0

高8位(8 - 15 bit)没有值

LogTable256[val] => LogTable256[16] => 4

1
2
3
4
5
6
7
8
9
10

结束计算，得到答案4。

---

[参考资料]

Bit Twiddling Hacks By Sean Eron Anderson

---

本文链接：https://blog.csdn.net/u012028275/article/details/126843708