【位操作笔记】计算以2为底整数N的对数 普通方法

计算以2为底整数N的对数 l o g 2 N log_2N log2​N 普通方法

用于计算以2为底整数N的对数 l o g 2 N log_2N log2​N。例如 l o g 2 8 = 3 log_28=3 log2​8=3， l o g 2 16 = 4 log_216=4 log2​16=4。

算法说明

以2为底整数N的对数 l o g 2 N log_2N log2​N，与最高有效位(most significant bit set，MSB)的位置相同。

例如8 = 0x8 = 0b1000，最高有效位在第3位，与 l o g 2 8 = 3 log_28=3 log2​8=3值相等。

该算法就是使用该特性来计算 l o g 2 N log_2N log2​N的值。

实现代码

实现方式为：

unsigned int bit_log2(unsigned int val)
{unsigned int ret = 0;while (val >>= 1)ret++;return ret;
}

注意，如果传入的参数val不是2的次幂，则返回值是val的值向下舍入到最近的2的次幂的对数值。例如 val的值为10，则返回值为 l o g 2 8 = 3 log_28=3 log2​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;
}

运行结果如下：

5
4
3
3
4

算法计算过程

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

计算示例

例如：

val = 16 = 0x10 = 0b10000，最高有效位在第4位，所以 l o g 2 16 = 4 log_216=4 log2​16=4。

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

0x10000 >>= 1	=>	val = 0x1000ret++	=>	ret = 10x1000 >>= 1	=>	val = 0x100ret++	=>	ret = 20x100 >>= 1	=>	val = 0x100ret++	=>	ret = 30x10 >>= 1	=>	val = 0x1ret++	=>	ret = 40x1 >>= 1	=>	val = 0x0

结束循环，得到答案4。

[参考资料]

Bit Twiddling Hacks By Sean Eron Anderson

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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！