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

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 语句来中断以找到最高阶的非零字节。

我会让你把剩下的从这里拿走。

Answer 4

您必须检查执行时间才能确定粒度，但我的猜测是一次执行 4 位，然后一次恢复为一位会使其更快。日志操作可能会比逻辑/位操作慢。

if (n < 0) return 32;
int r = 0;
while (n && 0x7FFFFFF0) {
  r+=4;
  n >>= 4; }
while (n) {
  r++;
  n >>= 1; }
return r;

Answer 5

进行二分搜索而不是线性搜索。

if ((n >> 16) != 0)
{
    r += 16;
    n >>= 16;
}

if ((n >> 8) != 0)
{
    r += 8;
    n >>= 8;        
}

if ((n >> 4) != 0)
{
    r += 4;
    n >>= 4;        
}

// etc.

如果您的硬件具有位扫描反转功能，则更快的方法是用汇编语言编写您的例程。为了保持您的代码可移植性，您可以这样做

#ifdef ARCHITECTURE_WITH_BSR
   asm // ...
#else
   // Use the approach shown above
#endif

Answer 6

number_of_bits = log2(integer_number)

四舍五入到较高的整数。