问特殊情况下的快速整数对数

EN

为什么不使用下两位而不是前导位。您可以首先将数字划分为8个bin，然后再将下两位进一步划分为4个bin。在这种情况下，您可以使用简单的移位操作，这是非常快的。

编辑：如果您认为使用对数是一个可行的解决方案。以下是通用算法：

设a为对数的底，取值范围为(b_min, b_max) = (32,8191)。您可以使用以下公式找到基数：

log(b_max/b_min) / log(a) = 32 bin

这就给了你a~1.1892026。如果使用这个a作为对数的底，则可以将范围(b_min, b_max)映射到(log_a(b_min), log_a(b_max)) = (20.0004,52.0004)。

现在，您只需要用20.0004减去all元素就可以得到范围(0,32)。它保证了所有元素都是对数一致的。完成

注意:任何一个元素都可能因为数值错误而超出范围。你应该自己计算出它的精确值。

日志: log_a(b) =Note2(B)/log(A)

表查找是一种选择，该表并不是那么大。如果一个8K表太大，并且您有一个计数前导零指令，您可以在最高的几位上使用表查找。

nbits = 32 - count_leading_zeros(v)  # number of bits in number
highbits = v >> (nbits - 4)          # top 4 bits.  Top bit is always a 1.
log_base_2 = nbits + table[highbits & 0x7]

您用log_2近似值填充的表

table[i] = approx(log_2(1 + i/8.0))

如果您想保持整数运算，请将最后一行乘以一个方便的因子。

我刚刚想出了一个基于IEEE754浮点的答案：

((union { float v; uint32_t r; }){ x }.r >> 21 & 127) - 16

它将32-8192大致对数地映射到0-31 (与hwlau的答案相同)。

改进版本(去掉无用的按位and)：

((union { float v; uint32_t r; }){ x }.r >> 21) - 528