卧槽，20 年前的几行代码竟如此牛逼？！

拼搏现实的明天。 2023-02-17 03:41 23阅读 0赞

点击上方“**五分钟学算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

最近在知乎上看到了一个话题：世界上有哪些代码量很少，但很牛逼很经典的算法或项目案例？其中有一个回答是雷神之锤 3 中的快速逆平方根算法，我本以为是电影中雷神 3 中出现的代码，就特别好奇点进去看了一下，结果真是对应了代码注释中的一句话“what the fuck?”。

越不会越好奇，查过之后才知道这是一款游戏中的部分代码，1999年发布，2005 年开源，距离现在已经有 20 年了，据说这部分代码出现在公共场合时，几乎震住了所有人，也就是下面这几行代码：

float Q_rsqrt( float number )
    {
      long i;
      float x2, y;
      const float threehalfs = 1.5f;
      x2 = number * 0.5f;
      y  = number;
      i  = * ( long * ) &y;  // evil floating point bit level hacking
      i  = 0x5f3759df - ( i >> 1 ); // what the fuck?
      y  = * ( float * ) &i;
      y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
      // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
      return y;
    }

可能很多程序员老手都知道这段牛B的代码，但对于很多人应该是空白的。求一个数的平方根我们通常会用到库中的内置方法，也就是sqrt，比如C语言中求一个数的平方根倒数，利用float(1.0/sqrt(x))即可。

可能那个时候没有sqrt方法，作者被“被逼无奈”想到了这种方法，但是最牛逼的是这种方法要比sqrt方法快的多，据说在有的CPU上可以快4倍，也有说快20%的，但我的电脑上编译是要快接近30%，而快的很大原因之一是因为代码中的一串神秘的数字0x5f3759df。下面结合一些相关知识和推导来介绍作者几个骚操作，最终的目的都是为了得到这个神秘数字。

首先我们要先明确一个基础知识，即单精度浮点数在32位中是如何储存的。32bit可以共分为三个部分S、E、M，其中S只有1位，0表示正数、1表示负数；E表示小数，共有8位；M表示尾数，共有23位，如下图：

![format_png 2][]

以数字4.25为例，整数5的二进制表示为0100；与二进制表示整数同理，小数也是如此，比如右侧就是，那么4.25转化为二进制形式就是0100.01。将二进制形式转用科学计数法的形式可以表示为。

> 这里先用s、e、m表示，因为S、E、M另有含义

由于4.25是正数，那么s位就存储为0，然后可以将指数处的2+127以二进制形式存储至e中，加上127的理由是将指数的范围由(-127,128)移码至(0,255)，这样就可以用指数位置就不用考虑符号问题。最后将小数点后的0001存储至m中，因为后面的数足以确定小数点前为1，所以没有必要再存储1，综上就是一个单精度浮点数在32位内存中的存储方式，如下图：

![format_png 3][]

所以对于一个要开放的浮点数x，有以下表示形式，先暂称为存储表达式（这个表达式下文需要用到）：

虽然e和m表示的实际意义是浮点数，但是毕竟二进制是都可以转换成十进制的整数嘛，那么如果从整数的角度看，整数E和浮点数e、整数M和浮点数m有没有某种关系呢？答案是肯定有的，但是理由呢我不知道=.=

加127的原因上文已经介绍了，就是为了调整指数的符号范围；是m中1后所需补零的个数，因为当从浮点数角度看时，1左边的0是有起到占位作用的，而如果从整数角度看时，1右边的0才有实际意义，所以在原基础的m上乘以1后零个数的次幂就可以转化至整M。

我们再回到最初的问题，对于一个浮点数x,求它的逆平方根：

如果对等式两边同时取对数：

如果结合上面的存储表达式，又可以得到一个新的等式：

![format_png 4][]

对于上式中的可以绘制出一条平滑的曲线，我们可以用直线对比(如下图)，可以看到两条线在(0,1)之间非常相近，那么如果再将这条直线向上平移一点点，可以假设这个平移的距离为b，那么两条线就有一种近似相等的关系：。

![format_png 5][]

需要注意的是这种关系成立的前提是，经代入得到下面式子：

![format_png 6][]

如果对做相同处理，那么就有下面式子：

上面我们不是利用整数型的M和E分别表示m和e嘛，那么自然可以用整数型套用上式中的浮点型，对于不同数字，整数型和浮点型之间的关系也不同，所以这里统一用常量B和L表示，如下：

用整数型替换浮点型可以得到新式子：

![format_png 7][]

可以看到整理后的式子左右有一个相同的部分，我们已经知道了这三个字母代表的意思，但合在一起表达的又是一个新概念，合并两个整数是一个很简单的问题，比如合并33和55，，那么不就是这个道理嘛，只不过前者是十进制后者是二进制，所以的作用就是将M和E存储的数字捆绑在一起，用来表示储存的数字，有人想前面不是还有一位S吗？S的作用是表示存储数字的正负，根号下的数字一定为正，所以S这位一定为0，没有实际意义。有没有感觉真的秒！

既然这个组合用来表示一个数字，那么就可以用另一个变量I来表示：

其实代码中下面这条语句就是套用的这个公式。

![format_png 8][]

代码中利用了一个右移运算表示公式中的，而就是求出代码中这串神秘数字的基础，至于怎么求得的，只有作者知道。后面又有一位大佬对这串数字进行推导，经过精密的演算求得了一串新的数字0x5f375a86，它略优于原常数，大佬只管算，我们膜拜就好。

因为上文中含I的公式是从整型的角度计算的，所以需要强制类型转换将整形转回浮点型，紧接着最后一行代码是利用牛顿迭代法提高结果的精确度，没有什么惊奇之处，下面回顾一下上文过程中作者的几个骚操作：

*  用整数型表示浮点型
 *  约等关系的替换
 *  捆绑二进制

也许作者利用的想法是已经存在了很久的理论，但是能把这些理论相组合并灵活运用创造出这种新兴高效的算法，真的不得不感叹一句NiuB，但需要注意的是这个算法依赖于浮点数的储存和字节顺序，所以在Mac上行不通。

上面代码可以再精简一些，但是原理一致，只是将一些变量简化：

float InSqrt(float x)
    {
     float xhalf = 0.5f * x;
     int i = *(int*)&x;
     i = 0x5f3759df - (i>>i);
     x = *(float*)&i;
     x = x*(1.5f-xhalf*x*x);
     return x; 
    }

可能你看到最后还是那句"what the fuck"，毕竟太多的公式推导都并没有相应的理论依据，只是靠着作者这些脑洞大开的想法，难道就是“我不要你觉得，我只要我觉得?”，关键还是要了解一下流程中几处很牛逼的想法，平时编程中不失为一种办法嘛，也可以当成一次知识拓展。

--------------------

### **推荐阅读** ###

• [完了！CPU一味求快出事儿了！][CPU]• [当你无聊时，可以玩玩 GitHub 上这个开源项目...][GitHub _...]• [剑指 offer 面试题精讲图解 | 03 . 数组中重复的数字][offer _ _ 03 .]• [炸裂！万字长文拿下HTTP 我在字节跳动等你！][HTTP]• [我在滴滴和头条的两年后端研发工作经验分享！][Link 1]• [太赞了，VSCode 上也能画流程图了！][VSCode]• [写给小白，从零开始拥有一个酷炫上线的网站！][Link 2]

--------------------

欢迎关注我的公众号“**五分钟学算法**”，如果喜欢，麻烦点一下“**在看**”~

![format_png 9][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vdzZwcnpadVBJRU5iMG01aWF3dXRJZjkwTjJVYjNkY1B1UDJLWEhKdmFSMUZ2MkZuaWNUdU95M0tjSHVJRUpiZDlsVXlPaWJlWHFXOHRFaG9KR0w5OHFPdy82NDA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVNmNHY2OG5DNWFhVjlJSDlBZWxmQ0tOa0ZEbFkwamlhYllPMjZhZFk4UU5hTkJMcnZMN00xQWRFM3N6eHg4NVZ3aWJ3NXRtU2w2R241US82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9SNG9yMzR1QlBHaWFkTDdGWWliaWFiQW5LWTVWTTIwaWF2bG1XR29MVjBpYVBRcGZNdE5VU1B1NXRKbHFFQnoyNnlVMkFoM0xUVGF1SUhIYXhacjV2c011aWJOQS82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9SNG9yMzR1QlBHaWFkTDdGWWliaWFiQW5LWTVWTTIwaWF2bG1pY1RuNWdkRjVTaWM2cWQyTnF1MnJ2TFRFSFVuYXpnMVVGSWtQemdzeGlia3FWSnp5Z245MXpnVWcvNjQw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9SNG9yMzR1QlBHaWFkTDdGWWliaWFiQW5LWTVWTTIwaWF2bG1ldWhUQ3g5enc3YTBQcDhHRTB5bEdzd0xDbXQxRGljR1lUcVVUR2ZWdXZRN2lhdGVpY1hpYnhUV3RnLzY0MA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9SNG9yMzR1QlBHaWFkTDdGWWliaWFiQW5LWTVWTTIwaWF2bG02MWN5V3FzaWEyUFJpYkVZaWJRbUV1NVVlN2xpY2hpYzI5VVZ0S2M4RUpaNGVIQVVocGw0OW5BaWFublEvNjQw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9SNG9yMzR1QlBHaWFkTDdGWWliaWFiQW5LWTVWTTIwaWF2bG1wSVhFbm1uTXpvcFZZazdwcTExUG1OU1dnWWljU1FCS3NsdmR2YUFHamU2OVp0dEo1U3VVN2R3LzY0MA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9SNG9yMzR1QlBHaWFkTDdGWWliaWFiQW5LWTVWTTIwaWF2bG1WNVpnNG9MYjZiTEIyaWE2T2tvTXhjTmhnSlRXN2swamVaUnpzNjBNbG9ERGZMaWFjZGZQZDJxdy82NDA?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9SNG9yMzR1QlBHaWFkTDdGWWliaWFiQW5LWTVWTTIwaWF2bG1hQ2FtTURnOWZMUFZFZmlhQ3RQQ0I3Q1Z5NHYwZ1phWWxkS2dad3ZjRkFmMmVSMmZtVFVIQmljZy82NDA?x-oss-process=image/format,png
[CPU]: https://blog.csdn.net/kexuanxiu1163/article/details/106368596
[GitHub _...]: https://blog.csdn.net/kexuanxiu1163/article/details/106345681
[offer _ _ 03 .]: https://blog.csdn.net/kexuanxiu1163/article/details/106324219
[HTTP]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e7a19cd79f30ffab43a658857adc435208a0bd3ce976293fc415d9097615549465b945fc2&idx=3&mid=2247488920&scene=21&sn=2e1cb06a868232e3f4eb01fcc1ffa9c5#wechat_redirect
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/106232922
[VSCode]: https://blog.csdn.net/kexuanxiu1163/article/details/106152421
[Link 2]: https://blog.csdn.net/kexuanxiu1163/article/details/105648532
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJodm5leUhtTURJTW1sOWtJYlVMUGlhUG5pYThpYW5ic1o3Q2trYlFGQTJLU3V3SzA2R3NuT3JMQ2tleHdwYUVoWU1aNHdac1BpY01Uc1ZBLzY0MA?x-oss-process=image/format,png