平方根联合和位移位

Question

我发现了这段获得平方根的代码，令我惊讶的是它的工作方式，使用联合和位移这是代码：

float sqrt3(const float x)  
{
  union
  {
    int i;
    float x;
  } u;

  u.x = x;
  u.i = (1<<29) + (u.i >> 1) - (1<<22); 
  return u.x;
}

首先保存在u.x中x的值然后赋值给u.i 然后这个数的平方根神奇地出现了 u.x

谁给我解释一下这个算法？

Answer 1

你可以在维基百科上找到完美的解释：

Methods of computing square roots

请参阅部分：依赖于浮点表示的近似值

So for a 32-bit single precision floating point number in IEEE format (where notably, the power has a bias of 127 added for the represented form) you can get the approximate logarithm by interpreting its binary representation as a 32-bit integer, scaling it by 2^{-23}, and removing a bias of 127, i.e.

To get the square root, divide the logarithm by 2 and convert the value back.

Answer 2

以上代码存在 UB（未定义行为），因此不应相信它可以在任何平台上运行。这是因为它写入 union 的成员并从与上次用于写入 union 的成员不同的成员读回。它还在很大程度上取决于字节顺序（多字节整数中字节的顺序）。

但是，它通常会按预期执行，要了解为什么值得您阅读 IEEE 754 binary32 floating-point format。

IEEE754 binary32 格式速成课程

IEEE754通常将一个32位的浮点数分成1个符号位、8个指数位和23个尾数位，从而得到

                   31 30-23           22-0
Bit#:               ||------||---------------------|
Bit Representation: seeeeeeeemmmmmmmmmmmmmmmmmmmmmmm
Value:              sign * 1.mantissa * pow(2, exponent-127)

数字基本上是“科学记数法，基数 2”。

作为一个细节，指数以“有偏差”的形式存储（也就是说，它的值高了 127 个单位）。这就是我们从编码指数中减去 127 以获得“真实”指数的原因。

简短说明

您的代码所做的是 将指数部分减半并损坏尾数 。这样做 因为一个数的平方根的指数大约是幅度的一半。

以 10 为基数的示例

假设我们想要 4000000 = 4*10^6 的平方根。

4000000 ~ 4*10^6  <- Exponent is 6
4000    ~ 4*10^3  <- Divide exponent in half

只需将指数 6 除以 2，得到 3，并将其作为新指数，我们就已经在正确的数量级内，并且更接近真相，

2000 = sqrt(4000000)

.

平方根联合和位移位

Square root union and Bit Shift

c

bit

unions

shift

IEEE754 binary32 格式速成课程

简短说明

以 10 为基数的示例