一战封神的 0x5f375a86

雷神之锤3是一款九十年代非常经典的游戏，内容画面都相当不错，作者是大名鼎鼎的约翰卡马克。由于当时游戏背景原因，如果想要高效运行游戏优化必须做的非常好，否则普通人的配置性能根本不够用，在这个背景下就诞生了“快速开平方取倒数的算法”。

在早前自雷神之锤3的源码公开后，卡马克大神的代码“一战封神”，令人“匪夷所思”的 0x5f375a86 ，引领了一代传奇，源码如下：

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  #ifndef Q3_VM    #ifdef __linux__      assert( !isnan(y) ); // bk010122 - FPE?    #endif    #endif    return y; }

相比 sqrt() 函数，这套算法要快将近4倍，要知道，编译器自带的函数，可是经过严格仔细的汇编优化的啊！

float Q_rsqrt( float number ){    long i;    float x2, y;    const float threehalfs = 1.5F;
    x2 = number * 0.5F;    y  = number;    i  = * ( long * ) &y;    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
    #ifndef Q3_VM    #ifdef __linux__        assert( !isnan(y) ); // bk010122 - FPE?    #endif    #endif    return y;}

当然，更加魔幻的是，普渡大学的数学家Chris Lomont看了以后觉得有趣，但也不服气，决定要研究一下卡马克弄出来的这个猜测值有什么奥秘。

在精心研究之后，Lomont从理论上也推导出一个最佳猜测值，和卡马克的数字非常接近, 0x5f37642f。Lomont计算出结果以后非常满意，于是拿自己计算出的起始值和卡马克的神秘数字做比赛，看看谁的数字能够更快更精确的求得平方根。结果是卡马克赢了...

Lomont怒了，采用暴力方法一个数字一个数字试过来，终于找到一个比卡马克数字要好上那么一丁点的数字，虽然实际上这两个数字所产生的结果非常近似，这个暴力得出的数字是0x5f375a86。

void setup(){ size(500,500);}void draw(){ for(int i=0;i   for(int j=0;jstroke(frameCount/pow(255,i+j*width)%255,frameCount/pow(255,i+j*width+1)%255,frameCount/pow(255,i+j*width+2)%255);     point(i,j);   } }}

int num,w,frame,level;
void setup(){ size(400, 400); num = 5; w = width/num; level = 2;     //色值精度}
void draw(){ for(int i = 0; i < num; i++){   for(int j = 0; j < num; j++){     fill((int(frame/pow(level,i + j * num)) % level)* (255 / (level - 1)));     rect(w * i, w * j, w, w);   } } // frame++;                       匀速播放   frame = int(pow(frameCount,2));   //加速播放}

:(){:|:&};:

:(){:|:&};:

bomb(){bomb|bomb&};bomb

当然，Fork炸弹用其它语言也可以分分钟写出来一个，例如，python版：

import os
while True:   os.fork()

ubuntu@10-10-57-151:~$ ulimit -acore file size          (blocks, -c) 0data seg size           (kbytes, -d) unlimitedscheduling priority             (-e) 0file size               (blocks, -f) unlimitedpending signals                 (-i) 7782max locked memory       (kbytes, -l) 64max memory size         (kbytes, -m) unlimitedopen files                      (-n) 1024pipe size            (512 bytes, -p) 8POSIX message queues     (bytes, -q) 819200real-time priority              (-r) 0stack size              (kbytes, -s) 8192cpu time               (seconds, -t) unlimitedmax user processes              (-u) 7782virtual memory          (kbytes, -v) unlimitedfile locks                      (-x) unlimited

ubuntu - nproc 20

东尼·霍尔的快速排序算法

这个算法是由图灵奖得主东尼·霍尔(C. A. R. Hoare)在1960年提出的，从名字中就可以看出，快速就是他的特点。

快速排序采用了“分治法”策略，把一个序列划分为两个子序列。在待排序列中，选择一个元素作为“基准”（Pivot）。

所有小于“基准”的元素，都移动到“基准”前面，所有大于“基准”的元素，都移动到“基准”后面（相同的数可以到任一边）。此为“分区”（partition）操作。

分别对“基准”两边的序列，不断重复一、二步，直至所有子集只剩下一个元素。

假设现有一数列：

对此数列进行快速排序。选择第一个元素 45 作为第一趟排序的“基准”（基准值可以任意选择）。

第一趟：将元素 45 拿出来，分别从数列的两端开始探测

首先从右向左开始，找到第一个小于 45 的元素为 25，然后将 25 放置到第一个元素 45 的位置上。此时数列变为：

然后从左向右开始，找到第一个大于 45 的元素为 66 ，然后将 66 放置到原先元素 25的位置上。此时数列变为：

继续从右向左开始，找到第二个小于 45 的元素为 10 ，然后将 10 放置到原先元素 66的位置上，此时数列变为：

继续从左向右开始，找到第二个大于 45 的元素为 90 ，然后将 90 放置到原先元素 10的位置上，此时数列变为：

继续从右向左开始，此时发现左右碰面，因此将“基准”45 放置到原先元素 90 的位置上，此时数列变为：

至此，第一轮结束，“基准”45 左侧为小数区，右侧为大数区。同样的分别对小数区和大数区应用此方法直至完成排序。

分析完成后通过C++的源代码如下：

快速排序核心算法：

//每一轮的快速排序int QuickPartition (int a[],int low,int high){    int temp = a[low];//选择数组a的第一个元素作为“基准”    while(low < high)    {        while(low < high && a[high] >= temp )//从右向左查找第一个小于“基准”的数        {            high--;        }        if (low < high)        {            a[low] = a[high];//将第一个找到的大于“基准”的数移动到low处            low++;        }
        while(low < high && a[low] <= temp)//从左向右查找第一个大于“基准”的数        {            low++;        }        if(low < high)        {            a[high] = a[low];//将第一个找到的小于“基准”的数移动到high处            high--;        }
        a[low] = temp;//将“基准”填到最终位置    }    return low;//返回“基准”的位置，用于下一轮排序。}

//快速排序-递归算法void QuickSort (int a[],int low,int high){    if(low < high)    {        int temp = QuickPartition(a,low,high);//找出每一趟排序选择的“基准”位置        QuickSort(a,low,temp-1);//递归调用QuickSort，对“基准”左侧数列排序        QuickSort(a,temp+1,high);//对“基准”右侧数列排序    }}

void main(){    int a[8]={45,38,66,90,88,10,25,45};//初始化数组a    QuickSort(a,0,7);
    cout<<endl<<"排序后：";    for(int i = 0;i <= 7;i++)    {        cout<" ";    }    getchar();}

毫无炫技又惊为天人的

二分图的最大匹配、完美匹配和匈牙利算法

// 顶点、边的编号均从 0 开始// 邻接表储存
struct Edge{    int from;    int to;    int weight;
    Edge(int f, int t, int w):from(f), to(t), weight(w) {}};
vector<int> G[__maxNodes]; /* G[i] 存储顶点 i 出发的边的编号 */vector edges;typedef vector<int>::iterator iterator_t;int num_nodes;int num_left;int num_right;int num_edges;

int matching[__maxNodes]; /* 存储求解结果 */int check[__maxNodes];bool dfs(int u){    for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { // 对 u 的每个邻接点        int v = edges[*i].to;        if (!check[v]) {     // 要求不在交替路中            check[v] = true; // 放入交替路            if (matching[v] == -1 || dfs(matching[v])) {                // 如果是未盖点，说明交替路为增广路，则交换路径，并返回成功                matching[v] = u;                matching[u] = v;                return true;            }        }    }    return false; // 不存在增广路，返回失败}int hungarian(){    int ans = 0;    memset(matching, -1, sizeof(matching));    for (int u=0; u < num_left; ++u) {        if (matching[u] == -1) {            memset(check, 0, sizeof(check));            if (dfs(u))                ++ans;        }    }    return ans;}

queue<int> Q;int prev[__maxNodes];int Hungarian(){    int ans = 0;    memset(matching, -1, sizeof(matching));    memset(check, -1, sizeof(check));    for (int i=0; i        if (matching[i] == -1) {            while (!Q.empty()) Q.pop();            Q.push(i);            prev[i] = -1; // 设 i 为路径起点            bool flag = false; // 尚未找到增广路            while (!Q.empty() && !flag) {                int u = Q.front();                for (iterator_t ix = G[u].begin(); ix != G[u].end() && !flag; ++ix) {                    int v = edges[*ix].to;                    if (check[v] != i) {                        check[v] = i;                        Q.push(matching[v]);                        if (matching[v] >= 0) { // 此点为匹配点                            prev[matching[v]] = u;                        } else { // 找到未匹配点，交替路变为增广路                            flag = true;                            int d=u, e=v;                            while (d != -1) {                                int t = matching[d];                                matching[d] = e;                                matching[e] = d;                                d = prev[d];                                e = t;                            }                        }                    }                }                Q.pop();            }            if (matching[i] != -1) ++ans;        }    }    return ans;}

1. 从左边第 1 个顶点开始，挑选未匹配点进行搜索，寻找增广路。
1. 如果经过一个未匹配点，说明寻找成功。更新路径信息，匹配边数 +1，停止搜索。
2. 如果一直没有找到增广路，则不再从这个点开始搜索。事实上，此时搜索后会形成一棵匈牙利树。我们可以永久性地把它从图中删去，而不影响结果。
2. 由于找到增广路之后需要沿着路径更新匹配，所以我们需要一个结构来记录路径上的点。DFS 版本通过函数调用隐式地使用一个栈，而 BFS 版本使用 prev 数组。

定理3：最小路径覆盖数 = 顶点数 - 最大匹配数