为什么浮点数的整数表示形式提供对数的分段线性近似？

我将把我的答案限制在这个问题上，“为什么 浮点数的整数表示形式提供 对数的分段线性近似？ 快速平方反比是一个引人入胜的话题，但我不这么认为 对它有足够的了解来谈论它。

但实际上很容易回答标题中的问题。首先，我将从“TL;DR“摘要：

这种近似之所以有效，是因为当一个数字是基数的精确幂时，当用指数表示法时，它的对数（微不足道地）正好是它的指数。像 IEEE-754 这样的浮点符号是以 2 为基数的指数符号，指数几乎占据了格式中精度最高的位，只有符号位除外，符号位为 0 表示正数，因此可以忽略不计。所有精度较低的位（即在指数下方）都形成一个完美的线性级数，名义上从 000 到 999，部分原因是 IEEE-754 格式使用具有“隐藏”前导 1 位的归一化有效。

较长的解释从回顾开始：我们对数是什么意思？ 嗯，它是指数或幂函数的倒数。 指数说，十的二次方 （10²） 是 100。所以（以 10 为底）对数函数 问诸如此类的问题，我们必须提高 10 个才能获得 数字 100？答案当然是2。

您还可以问诸如“我们必须提高 10 个才能获得 50号？这显然更难，因为 50 不是偶数 10 的幂。这背后有一些非常酷的数学，我就是这样 不打算试图解释，而是将事情提高到分数 幂的定义方式是 10^1.69897 是 50。 因此，50 的对数（以 10 为基数）是 1.69897。

然后你也不必将自己限制在 10 的幂。 数学家喜欢使用特殊数字 e （2.71828） 的幂，当然计算机程序员也喜欢（只是喜欢）来 使用 2 的幂。我们必须将 2 提高到什么功率才能 得到数字 32？每个计算机极客都知道它是 5。所以日志 32 的（基数 2）是 5。

然后是科学记数法。让我们以数字 12345 为例。 用科学记数法表示的一种方法是 1.2345 × 10⁴.事实证明，这给了我们一个提示 以 10 为底的 12345 对数是多少。这将是 大于或等于 4，小于 5。（实际上大约是 4.09149。 只要我们选择以某种方式归一化的科学表示，其中有效部分 （俗称“尾数”）被选为 介于 1 和 10 之间。（也就是说，我们无法得到一个很好的估计 以这种方式的对数，如果我们看一下其他等价物 符号 0.12345 × 10⁵ 或 12.345 × 10³.）

所以现在让我们转向计算机浮点表示。 这些通常使用（IEEE-754 肯定使用）base-2 （二进制）指数表示，即具有归一化 有效值乘以 2 的幂。例如 数字 1.125 表示为 1.125 × 2⁰， 数字 25.25 表示为 1.578125 × 2⁴， 数字 0.1875 表示为 1.5 × ^2-3。

而且，就像以 10 为基数一样，这些指数给了我们一个粗略的， 以 2 为底的对数的纯整数近似值 — 同样， 只要我们使用归一化有效数，在本例中介于 1 和 2 之间。 因此，对数₂（25.25） 将介于 4 和 5 之间。

这也是我伏笔的时候了 一个超级特殊的秘密事实，暗示着这样一个事实， 我们将自己限制在归一化有效值上。 我说他们将是“在 1 到 2 之间”，但更多 准确地说，它们的范围从 1.00000 到 1.99999。 但请注意，无论有效值是多少， 对于以 2 为基数，第一个数字始终为 1。 一会儿，我们将看到我们能用它做些什么。

IEEE-754 二进制浮点表示全部由 一个符号位，后跟一定数量的指数位，后跟 按一定数量的有效位。例如，对于我们的号码 25.25，我们将有一个 0 位代表一个正号， 后跟指数 4 的一些表示形式，后跟 有效数 1.578125 的一些表示。

但现在我们得到了一些原始位的曙光 浮点数的解释可能与 用对数做。对于正数，我们不必担心 关于符号位（因为它是 0），接下来我们看到的是 将成为指数，我们已经看到 指数是 对数。所以剩下要问的是，我们将如何 在具有精确 以 2 为底的对数 （对数₂（8） = 3，对数₂（16） = 4， log₂（32） = 5，以此类推） 以及介于两者之间的小数？

如果我给你等间距的数字，比如 100、200、300 并问 你填写中间的数字，你不会有麻烦： 您可以将 00 部分替换为 01、02、03、...，最多 99。 如果你对二进制数有所了解， 我问你对等间隔的二进制数做同样的事情，比如

00100000
01000000
01100000
10000000

你可以或多或少地做同样的事情，用连续的二进制数、、等替换部分。00000000010001000011

值得注意的是，我们即将看到一些东西 当我们在 IEEE-754 中编码有效值时，这种情况就会发生 浮点数。

让我们开始看一个实际的IEEE-754 浮点格式。我们将使用单精度 float32，以 保持数字合理的一半。此格式使用 1 位 符号 （S），指数 （e） 为 8 位，指数 （e） 为 23 位 significand （s）：

S e e e e e e e e s s s s s s s s s s s s s s s s s s s s s s s

让我们开始弄清楚数字的表示形式 16.000 = 2⁴ 和 32.000 = 2⁵ 看起来像。

16 是 1.0 × 2⁴。所以有效数是 1.0，而 指数为 4。这些将如何存储？我要 首先专注于意义。记住观察结果 第一个数字（小数点左边的数字） 总是 1？IEEE-754 的立场是，这个始终为 1 的前导位根本不需要存储。这 有效值为 1.0 的实际存储位将为 00000。 指数将是 4 的某种表示。所以我要去 像这样表示数字 16.000：

0 4 4 4 4 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

这些“4”是近似值;我还没来得及 解释指数是如何编码的。

数字 32.000 是相似的——实际上，它是相同的，除了 对于指数：

0 5 5 5 5 5 5 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

但我正在建立的关键点是 介于 — 大于 16.0 但小于 32.0 的那些将全部 是变体

0 4 4 4 4 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

除了 0 被所有连续的 23 位二进制文件替换 数字 — 所有 2^23 或 8388608 个 — 从 000 开始......001 到 111...111.

所以现在我们已经把所有的东西都准备好了，看看如何 “这 浮点数的整数表示形式提供 对数的分段线性近似”。我们已经展示了 16 到 32 之间的数字的二进制表示 从以某物开头的数字形成一个漂亮的线性斜坡 像 4 一样，到以 5 开头的数字。

我一直在回避指数如何编码的问题。 这是使用偏置方案完成的。对于 binary32，位模式 stored 是实际指数值加上 127。所以我们的指数 值 4 将存储为 4+127=131 的位模式，而 5 将存储为 132。所以 16.0 和 32.0 将是

0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

其中我填写了编码指数 131 和 132 的二进制值，即 和 .现在我们可以看到实际的原始值1000001110000100

01000001100000000000000000000000和 、 和 、 或 1098907648 和 1107296256。010000100000000000000000000000000x418000000x42000000

这些数字与基数 2 没有任何明显的关系 16 和 32 的对数（即 4 和 5），但它们实际上是 非常接近。它们被偏差的影响所抵消，并且 它们在量级上是完全错误的。但这并不奇怪： 通过获取 32 位量并将它们视为整数，我们可以 得到大数字（确实是整数），但实际 这些对数的值应该是 4.0 和 5.0，我们希望 小数部分的可能性。因此，如果我们要治疗 这些大整数是某些对数的一些再现 其他的，较小的数字，它将涉及非常多的东西 就像定点表示一样。

推导该定点表示的细节是 直截了当：比例因子显然是 2²³ = 8388608，还有一个偏移量，对应于偏差 内置于 binary32 格式。该偏移量将1065353216 （127 × 2²³） 如果在缩放前使用，或在缩放后使用 127。

让我们看看这是否有效。我们得出了整数值 1098907648 和 1107296256 对应于 16.0 和 32.0。所以：

(1098907648 - 1065353216) / 8388608 = 4
(1107296256 - 1065353216) / 8388608 = 5

或者相反：

1098907648 / 8388608 - 127 = 4
1107296256 / 8388608 - 127 = 5

所以它正在工作！

有人说，一张图片胜过1000个字，早就该用这种方式来解释了。这是一张图表，并非巧合，它看起来很像你从Mitchell 1961发布的图表：

红色曲线是实际的 base-2 对数函数。黑点是对数₂（X） 为整数的位置。在这些点上，binary32 浮点值的原始位（解释为整数并适当缩放）正好等于对数₂。然后，在蓝色中，我们有直接连接这些点的直线段。

回顾一下：如果我们取对应于 2 的精确幂的 binary32 浮点值的原始位，我们得到：

2 的精确幂的有效值为 1.0（也就是说，这些数字都是 1.0 × 2^N），这意味着它们在 IEEE-754 中被编码为所有 0（由于“隐藏的 1 位”属性）。 由于它们是正数，因此它们的符号位也是 0，唯一不是 0 的部分是指数。由于对于精确幂，指数是对数，因此对于这些数字，在移位和缩放之后，原始位模式的整数解释始终是正对数。（我认为“转移和缩放”的某些方面是神奇数字0x5f37642f的用武之地。

然后，对于所有不是 2 的精确幂，并且对数不是整数的数字，有效值的布局方式意味着原始值（如上图中的蓝线所示）在精确幂之间形成完美的线性插值。因此，在（几乎）所有情况下，原始位模式确实最终确实是“对数的分段线性近似”。（我说“几乎”是因为这个结果不适用于亚正态值以及特殊值 Inf 和 NaN。

对“为什么”这个问题的另一种解释是，“为什么IEEE-754的设计者要这样设置？我不认为这是故意的，也就是说，我不认为要求原始位模式（解释为整数）对应于以 2 为底的对数的分段线性近似。但是，鉴于以下三个相关事实：

• 指数符号的定义基本上是对数的分段近似
• IEEE-754 确实有一个目标，即保持正浮点值按其原始位值单调递增
• IEEE-754 隐藏了有效数字的高阶“1”位;所有有效符号的格式均为 1.xxx，但只有 xxx 部分被存储为这样

“分段线性近似”结果相当整齐。

此答案讨论二进制浮点格式的正有限正态数。（该前提不适用于零、负数、无穷大、次正态数和 NaNs。

浮点数 y 表示为固定基数 b、整数指数 e 和有效数 s、0 ≤ s < b 的 ±b^es。对于正常形式，1 ≤ s < b。对于二进制格式，b 为 2。对于正数，符号当然是 +。对于任何特定的浮点格式，e 上都有边界，s 的大小和精度（s 中 b 基数）都有边界。对于这个答案的一般讨论，我们并不十分关心这些特定特征，尽管它们可能会在一些地方被引入。

给定 y = 2 e s，log 2 y = log 2 （2 e s） =^e + log ₂ s。

在 IEEE 754 的“单精度”格式中，binary32 通常用于 ，普通数字 2^es 被编码为 0 位表示符号，8 位编码为 e+127 的二进制，23 位编码为 （s−1）2²³ 的二进制。将这 32 位重新解释为二进制数字（按上面列出的顺序从最高有效到最低有效）得到值 （e+127）2²³+（s−1）2²³ = （e+126+s）2²³。float

我的问题是，浮点数是什么导致了这种特征？

正如我们在上面看到的，重新解释浮点数的编码，特别是 IEEE-754 二进制32，并不能给出对数的近似值，因为它完全超出了比例，并且偏向了偏移量。

但是，如果我们考虑调整 f（x） = x/2 23−127，则 f（y 重新解释为二进制） = f（（e+126+s）2 23） = （e+126+s）2 23/2 ²³−127 = e+s−1。现在我们看到我们有 y 的指数 e;该值 e+s−1 至少接近对数₂ y = e + 对数₂ s。因此，它是对数₂ y 的近似值。（另请注意，s−1 分别为 0 和 1，当 s = 1 和 2 时，与对数₂ s 相同。因此，它是有效数所覆盖的区间内对数₂ 秒的近似值。

如果我们将 e 的每个值作为分段线性近似的一个部分，则近似值 e+s−1 是线性的，因为它拟合线性模型 e+s−1 = ay + b，其中 a = 2−e 和 b = e−1，正如我们所看到的，因为 ay + b = 2−e y + e − 1 = 2^−e（2 ^e s） + e − 1 = e+s−1。

关于调整函数 f（x） = x/2²³−127，您经常会在操作浮点数编码的代码中看到这样的方面——它会以各种方式加法或减法以解释指数和有效数的前 1 位的偏差，并且它会以各种方式移动以将指数场移动到所需的位置。

问题中引用的文字与事实不符。更准确的版本是：正正向 IEEE-754 浮点数的位模式，解释为定点数并针对指数偏差进行调整，为二进制对数函数提供分段线性近似。

为了使该技术起作用，浮点格式必须是二进制的，并且有效位的最高有效位必须是隐式的，而不是实际存储的。此外，它必须将有效位存储在最低有效位的连续块中，并将指数存储在紧邻的连续高有效位块中。IEEE-754 之前的一些浮点格式满足这些要求，但许多格式不满足这些要求。

该技术之所以有效，是因为 IEEE-754 浮点格式使用半对数表示，指数提供对数刻度，但有效值提供它们之间的线性刻度细分。这与滑尺不同，滑尺是完全对数的，即主要分区和子分区都遵循对数刻度。

如果我们有一个正的正态IEEE-754数，它的存储指数是真正的指数加上指数偏差127。在 [1,2] 中的有效位中，只存储 [0， 1） 中的小数部分，即 ，因为有效位的最高有效位是隐式的。该数字的值为 2^e * （1 + f）。它的二进制对数是对数 2 （₂ e * （1 + f）） = 对数 2 （₂ ^e） + 对数₂ （1 + f）。给定 的域，一个非常简单和粗略的近似值是 log 2 （1 + f） = f（请注意，这与端点的数学结果匹配），因此 log 2 （₂ e * （1 + f）） ≈^e + f。binary32yEesfs = 1 + fyf

换言之：减去指数偏差后，该数字表示 的 s8.23 不动点表示，表示 的二元对数的粗略近似值。要将其转换为浮点数，请除以 2 23 或乘以 ^2-23。为了使这个过程在大多数现代处理器上更有效率，人们可以在过程的最后而不是一开始就减去指数偏差。这导致了以下示例性 ISO-C99 实现，最大绝对误差为 8.6e-2：yy

#include <stdint.h>
#include <string.h>

uint32_t float_as_uint32 (float x) 
{ 
    uint32_t r; 
    memcpy (&r, &x, sizeof r); 
    return r; 
} 

float fastest_log2 (float y)
{
    const int FP32_EXPO_BIAS = 127;
    const float two_to_m23 = 1.192092896e-7f; // 0x1.0p-23
    float x = (float)(int) float_as_uint32 (y);
    return x * two_to_m23 - (float) FP32_EXPO_BIAS;
}

在支持融合乘法加法运算且具有适当编译器设置的硬件上，最后一行应映射到某种风格的 FMA。fastest_log2()