如何使用二分查找猜32位float浮点值，仅32次询问是否可行？

仅需要32次调用is_greater_than函数就可以100%猜出任意32位float值，不需要考虑浮点值的实际分布是否均匀，实现逻辑和整数二分没有本质区别。

32位float本质上就是由32个bit组成的离散值，所有合法的32位float总共有2^32种不同的取值（包含NaN、正负无穷、正负零这类特殊值）。你不需要把二分的边界当成浮点数的实际数值，只要把所有float按IEEE 754标准的数值大小排序后，等价映射到0~2^32-1的无符号整数序列，直接对整数序列做二分即可，32个bit刚好对应最多32次二分查询就能定位到唯一值。

第一步：做float到有序整数的映射 #

IEEE 754的float的bit排序和数值大小排序不完全一致，只需要做一次简单转换就能让映射后的无符号整数大小顺序和float实际数值顺序完全匹配：

• 正数的bit模式转成uint32_t后，数值越大对应float值越大，只要把最高位的符号位设为1，就能保证所有正数都排在负数后面
• 负数的bit模式转成uint32_t后，数值越大对应float值越小，翻转除符号位外的所有bit即可修正顺序

// 将float转换为和数值大小顺序一致的uint32_t
uint32_t float_to_ordered_uint(float f) {
    uint32_t u = *reinterpret_cast<uint32_t*>(&f);
    if (u & 0x80000000) {
        return 0xFFFFFFFF ^ u;
    } else {
        return u | 0x80000000;
    }
}

// 将有序uint32_t转换回原float
float ordered_uint_to_float(uint32_t u) {
    if (u & 0x80000000) {
        u &= 0x7FFFFFFF;
    } else {
        u = 0xFFFFFFFF ^ u;
    }
    return *reinterpret_cast<float*>(&u);
}

第二步：执行整数二分 #

直接对0~2^32-1的整数范围做普通二分，每次取中值转换为float后调用is_greater_than判断即可：

float guess_float() {
    uint32_t left = 0, right = 0xFFFFFFFF;
    // 固定32次循环刚好覆盖所有bit的判断
    for (int i = 0; i < 32; i++) {
        uint32_t mid = left + (right - left) / 2;
        float mid_val = ordered_uint_to_float(mid);
        if (is_greater_than(mid_val)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return ordered_uint_to_float(left);
}

• 如果你的使用场景不需要覆盖NaN、正负无穷这类特殊值，可以提前把二分的左右边界限定在正常数值对应的uint32_t范围内，调用次数可以少于32次
• 上述逻辑可以正确区分IEEE 754中的正零和负零，不需要额外做兼容处理

内容的提问来源于stack exchange，提问作者Erel Segal-Halevi