如何将非负变量整数除以常量浮点≥1而不冒太大溢出风险？

Question

假设我们希望将 int 𝑥（源自用户的输入，可能是 0 到 2·10⁹ 之间的任何位置）除以 65781.76，向下舍入并得到一个整数。如何在C中正确地做到这一点？ 显然，

𝑥/65781.76f

将涉及浮点运算（并且，根据http://www.h-schmidt.net/FloatConverter/IEEE754.html，65781.76，作为大多数常量，至少在我的机），而

100*𝑥/6578176L

=

25*𝑥/1644544

则存在溢出的风险太大。还有其他选择吗？我对仅涉及整数算术的解决方案和（最重要的是）正确的解释感兴趣。

PS。理想情况下，我们希望有一个精确且便携的解决方案；如果可能的话，让我们坚持使用 C89–C90 左右的某个地方，而不需要外部库。

Answer 1

这是一种从原始整数出发的方法：

            x
--------------------------
              7227
      65536 * ----
               100
      ------------
           72

           72x
--------------------------
              7227
      65536 * ----
               100

           7200x
--------------------------
        473628672

if(x < INT_MAX / 7200)                  // no overflow will happen
    res = 7200 * x / 473628672;
else                                    // overflow would happen
    res = x / (473628672 / 7200);

当然，在将

x

乘以 7200 的情况下，精度会导致溢出，因此您可以考虑在这些特殊情况下不除以

473628672 / 7200

(

65781

)，但实际上除以

473628672.0 / 7200.0

(

65781.76

）。

对于正常的、非溢出的情况，它将尽可能精确。

Answer 2

如何在不冒太多溢出风险的情况下将非负变量整数除以正常量浮点数？

你想多了。完成这项工作的方法是使用普通的 FP 除法。你对此的反对似乎是因为你的除数不能完全用二进制浮点数表示，但是当你将 65536 * 72.27 / 72 的结果四舍五入到 7 位有效十进制数字时，精密列车就离开了车站。

事实上，如果您使用

double

类型而不是

float

类型，那么您可以获得相对于理想 65536 * 72.27 / 72 股息的 更 精确结果，那么您可以使用以十进制数字 6578176 开头的任何方法. 在您可能遇到的任何机器上，每个

double

都有 53 位尾数，全部有效，而

int

最多有 32 位精度，只有一位有效（前导零不重要） 。此外，考虑到股息的大小，您的商最多有 16 个有效位。

只需执行相当于此操作：

const double scale_factor = 65536 * 72.27 / 72;

int compute result(int x) {
    return x / scale_factor;
}