如何在C中无溢出精确计算非负整数÷≥1定点有理数的下取整？

精确计算⌊x÷c⌋的C89可移植实现 #

核心原理

由于c是两位小数的定点有理数，可精确转换为分数形式 ( c = \frac{K}{100} )（K为正整数，由c的十进制值乘以100得到，例如65781.76对应K=6578176）。根据数学定义：
[
\lfloor x \div c \rfloor = \lfloor \frac{x \times 100}{K} \rfloor
]
为避免直接计算x*100时的int溢出，我们将x拆分为 ( x = q \times K + r )（其中( q = x / K ) 是整数商，( r = x % K ) 是余数，满足( 0 \leq r < K )），代入后得到：
[
\lfloor \frac{x \times 100}{K} \rfloor = q \times 100 + \lfloor \frac{r \times 100}{K} \rfloor
]
该拆分将大乘法拆分为两个安全的计算步骤，完全规避溢出风险。

代码实现

#include <stdio.h>
#include <limits.h>

// 替换为对应c的K值：K = c * 100（取整数）
#define K 6578176L

int floor_div(int x) {
    // 拆分x为q*K + r，q为整数商，r为余数
    long q = (long)x / K;
    int r = x % K;
    
    // 计算(r*100)/K的商，用long存储中间结果避免溢出
    long r_div = ((long)r * 100L) / K;
    
    // 结果转换为int，不会溢出（q*100 ≤ INT_MAX，r_div < 100）
    return (int)(q * 100L + r_div);
}

int main() {
    // 测试示例：x取INT_MAX
    int x = INT_MAX;
    printf("⌊%d ÷ 65781.76⌋ = %d\n", x, floor_div(x));
    return 0;
}

关键细节解释

1. 精确性保障：将c转换为分数形式完全保留了其精确值，彻底避免浮点运算的精度损失（例如65781.76无法用IEEE754单精度浮点数精确表示的问题）。
2. 溢出规避：
   • (long)x / K：将int类型的x转为long后再做除法，确保即使x接近INT_MAX，计算也不会溢出。
   • (long)r * 100L：余数r小于K（因c是ddddd.dd格式，K最大为9999999，r最大为9999998），乘以100后结果为999999800，远小于32位long的最大值2147483647，完全安全。
   • 最终结果q*100 + r_div：由于K≥100，q = x/K ≤ INT_MAX/100，因此q*100 ≤ INT_MAX，加上r_div（最大为99）后仍不超过INT_MAX，可安全转换为int类型。
3. 可移植性：完全符合C89标准，仅依赖标准库头文件，利用C89规定的long类型最小宽度（至少32位），结合用户假设的int至少3字节宽的前提，确保所有计算步骤在不同平台上都能正确执行。

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