计算存储数字所需位数的最快方法是什么

Question

我正在尝试优化一些打包和解包例程.为了进行打包,我需要计算存储整数值所需的位数.这是当前的代码.

if (n == -1) return 32;
if (n == 0) return 1;
int r = 0;
while (n)
{
    ++r;
    n >>= 1;
}
return r;

Answer 1

非便携式,使用大多数现代架构上可用的位扫描反向操作码.它作为Visual C++中的内在函数暴露出来.

可以说,问题中的代码不需要边缘案例处理.为什么需要一位存储0？无论如何,我会忽略问题的边缘.胆量可以有效地完成:

if (n >> 16) { r += 16; n >>= 16; }
if (n >>  8) { r +=  8; n >>=  8; }
if (n >>  4) { r +=  4; n >>=  4; }
if (n >>  2) { r +=  2; n >>=  2; }
if (n - 1) ++r;

Answer 2

您正在寻找一个数字的整数对数基数2(l =最高位集).Sean Anderson的"Bit Twiddling Hacks"页面有几种方法,从循环中明显的计数位到使用表查找的版本.请注意,如果这种可移植性对您很重要,那么演示的大多数方法都需要稍微修改才能使用64位整数.

• http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

只需确保您使用的任何移位来计算最高位集需要unsigned在数字版本上完成,因为编译器实现可能会或可能不签署扩展>>对有符号值的操作.

Answer 3

你要做的是找到最重要的一点.有些架构只是为了这个目的而有一个特殊的指令.对于那些不这样做的人,使用表查找方法.

创建一个包含256个条目的表,其中每个元素标识最高位.

要么循环遍历数字中的每个字节,要么使用几个if语句来中断以找到最高阶非零字节.

我会让你从这里休息.