c++ - 计算可能溢出的整数运算的最安全和最有效的方法

Question

假设我们有 2 个常量 A & B 和一个变量 i，都是 64 位整数。我们要计算一个简单的常见算术运算，例如:

i * A / B    (1)

为了简化问题，我们假设变量 i 总是在 [INT64_MIN*B/A, INT64_MAX*B/A] 范围内，所以最后算术运算 (1) 的结果不会溢出(即:fits 在 [INT64_MIN, INT64_MAX] 范围内)。

另外，i 被认为更可能在 friendly 范围 Range1 = [INT64_MIN/A, INT64_MAX/A](即:接近 0)，但是 i 可能(不太可能)超出此范围。在第一种情况下，i * A 的简单整数计算不会溢出(这就是我们称范围 friendly 的原因)；在后一种情况下，i * A 的简单整数计算会溢出，导致 (1) 的计算结果错误。

计算操作 (1) 的“最安全”和“最有效”的方式是什么(其中“最安全”的意思是:保持精确性或至少具有不错的精度，而“最有效”的意思是:平均计算时间最短)，前提是 i 更有可能在 friendly 范围 Range1。

目前，代码中目前实现的解决方案如下:

(int64_t)((double)A / B * i)

哪个解决方案非常安全(没有溢出)，但不准确(由于双有效位 53 位限制导致精度损失)并且非常快，因为双除法 (double)A/B 是在编译时预先计算的，只允许在运行时计算双倍乘法。

Answer 1

如果您无法在所涉及的范围上获得更好的界限，那么您最好遵循 iammilind's advice使用 __int128 .

原因是，否则您将必须实现字到双字乘法和逐字除法的完整逻辑。 Intel 和 AMD 处理器手册包含有用的信息和现成的代码，但它涉及到相当多的内容，并且使用 C/C++ 而不是汇编程序会使事情变得更加复杂。

所有优秀的编译器都将有用的原语公开为内在函数。 Microsoft's list似乎不包含类似 muldiv 的原语，但 __mul128 内在函数将 128 位乘积的两半作为两个 64 位整数提供。基于此，您可以执行两位数除以一位数的长除法，其中一位“数字”将是一个 64 位整数(通常称为“肢体”，因为大于一位数但仍然只是整体的一部分)。仍然相当复杂，但比使用纯 C/C++ 好得多。然而，就便携性而言，它并不比使用 __int128 好。直接地。至少这样编译器实现者已经为您完成了所有艰苦的工作。

如果您的应用程序域可以为您提供有用的界限，例如 (u % d) * v不会溢出就可以使用身份了

(u * v) / d = (u / d) * v + ((u % d) * v) / d

在哪里 /表示整数除法，只要 u 是非负数且 d 是正数(否则您可能会违反运算符 % 的语义所允许的余地)。

在任何情况下，您都可能必须分离出操作数的符号并使用无符号运算，以便找到可以利用的更有用的机制 - 或规避编译器的破坏，例如您提到的饱和乘法。有符号整数操作的溢出会调用未定义的行为，编译器可以自由地做任何他们想做的事情。相比之下，无符号类型的溢出是明确定义的。

此外，对于无符号类型，您可以使用 s = a (+) b 之类的规则。 (其中 (+) 可能是溢出的无符号加法)您将拥有 s == a + b或 s < a && s < b ，它可以让您通过廉价的操作在事后检测溢出。

但是，您不太可能在这条道路上走得更远，因为所需的努力很快就会接近(甚至超过)我之前提到的实现双肢手术的努力。只有对应用程序域进行彻底分析才能提供规划/部署此类快捷方式所需的信息。在一般情况下，在你给定的范围内，你几乎不走运。