【位操作笔记】计算以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$，与最高有效位(most significant bit set，MSB)的位置相同。

例如8 = 0x8 = 0b1000，最高有效位在第3位，与$lo{g}_{2}8=3$值相等。

该算法就是使用该特性来计算$lo{g}_{2}N$的值。

实现代码

实现方式为：

unsigned int bit_log2(unsigned int val)
{
    unsigned int ret = 0;
    
    while (val >>= 1)
        ret++;
    
    return ret;
}
1
2
3
4
5
6
7
8
9

注意，如果传入的参数val不是2的次幂，则返回值是val的值向下舍入到最近的2的次幂的对数值。例如 val的值为10，则返回值为$lo{g}_{2}8=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

算法计算过程

因为$lo{g}_{2}N$与最高有效位(most significant bit set，MSB)的位置相同，所以这里是用最普通的方法，循环右移计算最高有效位在第几位。

计算示例

例如：

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

模拟这个循环计算的过程：

0x10000 >>= 1	=>	val = 0x1000

ret++	=>	ret = 1

0x1000 >>= 1	=>	val = 0x100

ret++	=>	ret = 2

0x100 >>= 1	=>	val = 0x100

ret++	=>	ret = 3

0x10 >>= 1	=>	val = 0x1

ret++	=>	ret = 4

0x1 >>= 1	=>	val = 0x0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

结束循环，得到答案4。

---

[参考资料]

Bit Twiddling Hacks By Sean Eron Anderson

---

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