快速平方根逆算法中第一个类型双关语的确切值是多少？

Question

有了这个代码，（这是一个众所周知的快速平方根逆算法，在 Quake 3 中使用）我无法理解打印输出。我对整个算法的理解很肤浅，但想深入了解。 printf 打印时 i 的值是多少？这为我提供了 1120403456。它取决于计算机的体系结构吗？我在某处读到，像这样的类型双关会导致未定义的行为。在另一个网站上，我读到 i 此时的值是该变量使用的位的确切值。我对此感到困惑，并且老实说 i 的值是 100。我如何解释结果 1120403456？如何将此值转换为十进制 100？这些位是否以某种方式编码？这是代码摘录：

#include<stdio.h>

int main()
{
float x = 100;
float xhalf = 0.5f*x;
int i = *(int*)&x;
printf("%d", i);
i = 0x5f3759df - (i>>1);
x = *(float*)&i;
x = x*(1.5f-xhalf*x*x);
return x;

}

Answer 1

在int i = *(int*)&x;之后打印的i的值是浮点数100.0的位表示，这就是x被初始化的值。由于您在 printf 中使用 %d 格式，它将将该表示形式打印为十进制整数。

IEEE 32 位 float 中 100.0 的位模式是 0x42c80000，即十进制的 1120403456

Answer 2

要将 1120403456 或任何其他数字解释为 IEEE 基本 32 位二进制浮点数：

将数字写入 32 位，在本例中为 01000010110010000000000000000000。
第一位是符号。 0是+，1是-。
接下来的八位是指数的编码。它们是 10000101，即十进制的 133。指数用偏差 127 编码，这意味着表示的两个的实际幂为 2^133−127 = 2⁶。（如果指数为0或255，则为具有不同含义的特殊值。）
剩余的 23 位编码有效数字。对于普通指数（代码 1 到 254），它们编码以“1”开头的有效数字。并附加 23 位“10010000000000000000000”，组成二进制数字“1.100100000000000000000000”。在十进制中，这是 1.5625。
编码的完整值是符号的2次方乘以尾数：+ 2⁶ • 1.5625，等于64•1.5625，即100。

如果指数代码为0，则表示2⁻¹²⁶，尾数从“0”开始。而不是“1”。

如果指数代码为255，有效位为零，则对象表示无穷大（+∞或-∞，根据符号位）。如果指数代码为 255，并且有效位不为零，则该对象将表示一个非数字 (NaN)。此答案未涵盖 NaN 的其他语义。

Answer 3

它是 much older than Quake III，虽然确切的魔法常数有点不同。

根据 IEEE-754（这是大多数现代计算机使用的编码）对有限 single-precision floating point 数字的编码是

     31 30           23 22                                          0
     ├─┼─┬─┬─┬─┬─┬─┬─┬─┼─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┤
     │S│   Exponent    │                   Mantissa                  │
     └─┴───────────────┴─────────────────────────────────────────────┘

最高位，S为符号。如果设置则值为负，否则为正。

如果 Exponent 和 Mantissa 均为零，则该值为 0.0（如果 S 为零）或 -0.0（如果 S 为 1） .

如果 Exponent 为零，但 Mantissa 非零，则 非正规数 非常接近于零。

Exponent 为 255（所有位集）的表示保留为无穷大（如果 Mantissa 为零）和非数字（如果 Mantissa 为非零） .

对于从 1 到 254（含）的 Exponent 值，Mantissa 包含尾数的小数位，整数位置隐含 1 （这就是 (1) 在 0 10000001 (1)1011011011011011011011 中的意思。）换句话说，值 Mantissa 代表这些 Exponent 值，来自 1.000000000000000000000000₂（十进制的 1.0）到 1.11111111111111111111111₂（十进制的 1.99999994），包括在内。

现在，如果我们只考虑非负值（明确 S），E = Exponent（介于 1 和 254 之间，包括在内），而M是Mantissa的逻辑值（介于1.0和1.99999994之间），那么单精度浮点数表示的值V是

V = 2^{E - 127} × M

127 是指数偏差。 V的平方根是

√V = 2^{(E - 127)/2} × √M = 2^{E/2 - 127} × 2⁶³ × √2 × √M

和平方根倒数，也就是这里的目标操作，

1/√V = 2^{(127 - E)/2} × 1 /√M = 2^{-E/2 - 127} × 2⁶³×√2×1/√M

注意到 2^127/2 = 2^63.5 = 2⁶³ × √2 .

如果我们采用整数表示，并将其向右移动一位，我们实际上将 E 减半。要乘以 2⁶³，我们需要将指数加 63； 63×2²³。然而，对于平方根运算，我们实际上只是乘以 M/2，而不是乘以 √2 × √M。这意味着（将整数表示向右移动一位，然后将 63 加到指数）产生平方根的估计值，对于大于 1.0 的参数，误差在 0.7071067 和 0.75 之间，误差在 0.7071067 和 0.7071067 之间。 0 到 1 之间的值是 1448.155。（对于 √0 产生 5.421×10^-20，对于 √1 产生 0.75。）

请注意，对于平方根倒数运算，我们希望取反 E。

事实证明，如果将整数表示右移一位，然后从 (1 01111100 1101110101100111011111)₂ 中减去它（十进制为 1597463007，十六进制为 0x5f3759df， √2¹²⁷ ≈ 13043817825332782212 的单精度浮点近似值），你会得到一个非常好的平方根倒数的近似值（1/√V).对于所有有限正态参数，近似值与正确值相差 0.965624 到 1.0339603；一个很好的近似值！您所需要的只是 Newton's method 的一两次迭代，用于顶部的平方根倒数运算。（对于 f(X) = 0 当且仅当 X = 1/√V 你需要 f(X) = 1/X^2 - V。因此， 中的每次迭代X 是 X - f(X)/f'(X) = X × (1.5 - 0.5 × V × X × X。这看起来应该很眼熟。）

快速平方根逆算法中第一个类型双关语的确切值是多少？

What is the exact value of the first type-punning in fast square root inverse algorithm?

c

algorithm

floating-point

square-root