c - 特殊情况的快速整数对数

Question

我有 32-8191 范围内的整数值，我想将其映射到大致对数刻度。如果我使用基数 2，我可以只计算前导零位并将它们映射到 8 个槽中，但这太粗略了；我需要 32 个槽(更多会更好，但我需要它们映射到 32 位值中的位)，结果得出对数的底数大约为 1.18-1.20。谁有一些技巧可以非常快速地计算此值或合理的近似值？

我的直觉是使用条件将范围分解为 2 或 3 个子范围，并为每个子范围使用一个小的查找表，但我想知道我是否可以使用 count-leading-zeros 做一些技巧然后改进结果，尤其是因为结果不必是精确的，而只是大致的对数。

Answer 1

为什么不使用前导位以外的下两位。您可以先将数字划分为 8 个 bin，接下来的两位将每个 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 即可得到范围 (0,32)。它保证所有元素都是对数均匀的。完成

注意:由于数值错误，任何一个元素都可能超出范围。具体值需要自己计算。

注2:log_a(b) = log(b)/log(a)