如何在无除法和浮点运算下将分数分母转为1023并保持比例

问题本质 #

我们需要找到整数c，使得c/1023与原分数a/b比例一致（示例中为向下取整），核心是计算c = floor((a * 1023) / b)，且全程禁止浮点运算和除法指令。

优化后的二分查找（固定迭代次数） #

原二分法的迭代次数依赖于分母b的大小，优化后改为在0~1023区间内二分，迭代次数固定为10次（因为1023=2^10-1），效率显著提升，且避免除法：

int convert_fraction(int a, int b) {
    int low = 0, high = 1023;
    int result = 0;
    long long target = (long long)a * 1023; // 用64位避免溢出
    
    while (low <= high) {
        int mid = (low + high) >> 1; // 移位替代除法
        long long product = (long long)mid * b;
        
        if (product <= target) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

优势 #

• 固定10次循环，不受b大小影响，最坏情况也仅需10次迭代
• 仅用整数加法、移位、乘法，完全符合禁止浮点和除法的要求
• 通过64位整数存储中间结果，避免32位溢出问题

更快的乘法逆元法（近似O(1)） #

利用牛顿迭代计算b在模2^32下的乘法逆元，再通过乘法移位快速得到商，仅需少量调整即可得到精确结果：

// 牛顿迭代求b的模2^32逆元，无除法/浮点运算
unsigned int compute_inv(unsigned int b) {
    unsigned int inv = b;
    inv *= 2 - (unsigned long long)b * inv;
    inv *= 2 - (unsigned long long)b * inv;
    inv *= 2 - (unsigned long long)b * inv;
    inv *= 2 - (unsigned long long)b * inv;
    return inv;
}

unsigned int convert_fraction_fast(unsigned int a, unsigned int b) {
    unsigned long long target = (unsigned long long)a * 1023;
    unsigned int inv = compute_inv(b);
    unsigned int c = (unsigned long long)target * inv >> 32;
    
    // 验证并微调结果（最多1-2次调整）
    while ((unsigned long long)(c + 1) * b <= target) {
        c++;
    }
    while ((unsigned long long)c * b > target) {
        c--;
    }
    return c;
}

优势 #

• 绝大多数情况下无需调整，直接得到正确结果，效率接近常数时间
• 完全基于整数运算，无浮点和除法指令
• 适合对性能要求极高的场景

验证示例 #

用示例测试上述代码：

• a=1, b=7：1*1023=1023，1023//7=146 → 返回146
• a=47, b=100：47*1023=48081，48081//100=480 → 返回480
• a=223, b=230：223*1023=228129，228129//230=991 → 返回991
• a=234, b=567：234*1023=239382，239382//567=422 → 返回422

完全匹配示例结果。

内容的提问来源于stack exchange，提问作者郭岷源