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

我试图优化一些位打包和解包例程。为了进行打包，我需要计算存储整数值所需的位数。这是当前的代码。什么是计算存储数字所需位数的最快方法

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

来源

2010-04-27 Matt Wamboldt

我希望你不是试图压缩数据，并用数值中的位数计数每个值的前缀。 – Skizz 2010-04-27 13:01:58

当你写“32”时，我认为你的意思是sizeof（int）* CHAR_BIT。你想让你的代码在sizeof（int）== 8的地方工作吗？ – 2010-04-27 13:13:01

如果您正在使用>>，您确实希望n是无符号的。 – 2010-04-27 13:13:56

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

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

只要确保任何你使用制定出的最高位设置转移需要因为编译器实现要在一个unsigned版本号来完成”可能或不可能符号将扩展>>操作的签名值。

来源

2010-04-27 14:03:42

甚至没有意识到我想要做的是计算log base 2. Kinda在Math类中跳过对数。该网站有一些有用的东西。谢谢 – 2010-04-27 17:31:24

链接已损坏！ – 2016-07-08 00:18:09

不可移植地使用大多数现代体系结构上可用的位扫描反向操作码。它在Visual C++中作为intrinsic公开。

可移植的，问题中的代码不需要边缘处理。为什么你需要一位来存储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;

来源

2010-04-27 12:49:39

你必须要检查的执行时间，以图中的粒度，但我的猜测是，做一次4位，然后在同一时间恢复到一个位将使其更快。日志操作可能会比逻辑/位操作慢。

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

来源

2010-04-27 12:53:12 Ron

你想要做的是找到最重要的位。一些体系结构有专门的说明就是为了这个目的。对于那些不使用表查找方法。

创建256个表项，其中每个元素标识最高位。

循环遍历数字中的每个字节，或者使用一些if语句打破查找最高阶的非零字节。

我会让你从这里休息。

来源

2010-04-27 12:59:41 Sparky

在具有慢速RAM的快速CPU（a PC！）这可能比仅仅执行for循环慢。 for循环将持续在大约一百个左右的时钟周期内，而如果数据需要从磁盘中分页，则内存查找可能需要10s的毫秒数（然后你对高速缓存感到不安））。 – Skizz 2010-04-27 13:56:52

做一个二进制搜索，而不是一个线性搜索。

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

来源

2010-04-27 13:00:12 dan04

number_of_bits = log2(integer_number)

四舍五入至更大的整数。

来源

2010-04-27 13:11:50 tga

他想优化它，而不是让它变慢...... – 2010-04-27 13:17:56

@Matteo，当然他想优化代码，但这种挑剔的优化会导致代码混乱。采取log2是一个优雅，干净，可读和可维护的方法。 – Mahes 2011-05-18 18:55:36

@Mahes：这个问题特别指出了“比特打包/解包例程的最快方式”，可能在内部循环中调用，其中性能*是关键的。这个解决方案不需要组装移位/按位指令，而是将一个整数转换为浮点（这很慢），某种查表（可能触发缓存未命中）/截断的串行计算（用于日志）和一个转换回int（再次，很慢）。 Malus指出，如果它是一个没有硬件FP的嵌入式平台，那么每个FP操作都必须通过软件来模拟。 – 2011-05-18 19:12:06

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

回答

相关问题