C语言冷知识：把浮点数“看作”整型数来排序

技巧来源于《深入理解计算机系统(第三版)》第二章81页

技巧原理

对于非负的四字节单精度浮点数，其值越大，其二进制码对应的无符号整型的值也就越大。

因此，可以用无符号整型指针去读取浮点数，把浮点数“看作”无符号整型来比较大小。

适用场景

• “浮点数比大小的开销”比“整型数比大小的开销”更大的机器。

不适用场景

1. 配备了专门处理浮点运算设备的硬件平台。
2. 含有正负0（同时出现）、正负Inf、NaN等特殊值的数据，它们也会参与到排序中。

注意事项

1. 现代CPU一般都有专门处理浮点数运算的FPU等设备，因此大多数情况下这个技巧并不会加速你的代码。
2. 浮点数负数的表示和正数是对称的，因此算法对负数的排序顺序与正数相反，请特别注意。
3. 对整型比大小请尽量使用关系运算符，而不是减法，以免溢出。

示例代码

#include <stdio.h>
#include <stdlib.h>

// 待排序的浮点数数组长度
#define LEN 10


// 用无符号整型指针去读取、比较浮点数大小
int cmp (const void * a, const void * b)
{
    const unsigned *aa = a;
    const unsigned *bb = b;
    
    // 使用关系运算符比大小，以防溢出风险
    if (*aa < *bb)
        return -1;
    else if (*aa > *bb)
        return 1;
    else 
        return 0;
}

int main()
{
    // 产生若干０～１之间的随机浮点数
    float farray[LEN];
    for (int i = 0; i < LEN; i++) {
        farray[i] = 1.f * rand() / RAND_MAX;
    }
    
    // 对它们进行快速排序
    qsort(farray, LEN, sizeof(farray[0]), cmp);
    
    // 输出排序结果，包括浮点数二进制码的浮点读取表示与无符号整型读取表示
    for (int i = 0; i < LEN; i++) {
        printf("float:%f\tread as uint:%u\n", farray[i], *(unsigned*)(farray+i));
    }
    return 0;
}


/*
参考输出：
float:0.197551	read as uint:1045056232
float:0.277775	read as uint:1049507965
float:0.335223	read as uint:1051435601
float:0.394383	read as uint:1053420687
float:0.553970	read as uint:1057870074
float:0.768230	read as uint:1061464754
float:0.783099	read as uint:1061714225
float:0.798440	read as uint:1061971601
float:0.840188	read as uint:1062672011
float:0.911647	read as uint:1063870905
*/