16

是否有任何有效且可移植的方法来检查在 C 中使用 int64_t 或 uint64_t 操作数的乘法运算何时溢出？

例如，添加 uint64_t 我可以这样做：

if (UINT64_MAX - a < b) overflow_detected();
else sum = a + b;

但我无法得到类似的简单乘法表达式。

我所想到的就是将操作数分成高和低 uint32_t 部分，并在检查溢出的同时执行这些部分的乘法，这确实很丑陋，而且可能效率也很低。

更新 1：添加了一些实现多种方法的基准代码

更新 2：添加了 Jens Gustedt 方法

基准测试程序：

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define N 100000000

int d = 2;

#define POW_2_64 ((double)(1 << 31) * (double)(1 << 31) * 4)

#define calc_b (a + c)
// #define calc_b (a + d)

int main(int argc, char *argv[]) {
    uint64_t a;
    uint64_t c = 0;
    int o = 0;
    int opt;

    if (argc != 2) exit(1);

    opt = atoi(argv[1]);

    switch (opt) {

    case 1: /* faked check, just for timing */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            if (c > a) o++;
            c += b * a;
        }
        break;

    case 2: /* using division */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            if (b && (a > UINT64_MAX / b)) o++;
            c += b * a;
        }
        break;

    case 3: /* using floating point, unreliable */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            if ((double)UINT64_MAX < (double)a * (double)b) o++;
            c += b * a;
        }
        break;

    case 4: /* using floating point and division for difficult cases */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            double m = (double)a * (double)b;
            if ( ((double)(~(uint64_t)(0xffffffff)) < m ) &&
                 ( (POW_2_64 < m) ||
                   ( b &&
                     (a > UINT64_MAX / b) ) ) ) o++;
            c += b * a;
        }
        break;

    case 5: /* Jens Gustedt method */
        for (a = 0; a < N; a++) {
            uint64_t b = a + c;
            uint64_t a1, b1;
            if (a > b) { a1 = a; b1 = b; }
            else       { a1 = b; b1 = a; }
            if (b1 > 0xffffffff) o++;
            else {
                uint64_t a1l = (a1 & 0xffffffff) * b1;
                uint64_t a1h = (a1 >> 32) * b1 + (a1l >> 32);
                if (a1h >> 32) o++;
            }
            c += b1 * a1;
        }
        break;

    default:
        exit(2);
    }
    printf("c: %lu, o: %u\n", c, o);
}

到目前为止，当假设溢出非常不寻常时，使用浮点过滤大多数情况的情况 4 是最快的，至少在我的计算机上它只比无操作情况慢两倍。

情况 5 比 4 慢 30%，但它始终执行相同的操作，没有任何特殊情况编号需要像 4 那样更慢的处理。

4

6 回答 6

9

实际上，同样的原理也可以用于乘法：

uint64_t a;
uint64_t b;
...
if (b != 0 && a > UINT64_MAX / b) { // if you multiply by b, you get: a * b > UINT64_MAX
    < error >
}
uint64_t c = a * b;

对于有符号整数，可以做类似的事情，您可能需要为每种符号组合提供一个案例。

于 2011-12-16T12:27:55.970 回答
5

如果您想避免像 Ambroz 的回答中那样的分裂：

首先，您必须看到两个数字中较小的一个，例如a2 32，否则结果无论如何都会溢出。让我们b分解为两个 32 位字，即b= c2 32 + d。

那么计算并不那么困难，我发现：

uint64_t mult_with_overflow_check(uint64_t a, uint64_t b) {
  if (a > b) return mult_with_overflow_check(b, a);
  if (a > UINT32_MAX) overflow();
  uint32_t c = b >> 32;
  uint32_t d = UINT32_MAX & b;
  uint64_t r = a * c;
  uint64_t s = a * d;
  if (r > UINT32_MAX) overflow();
  r <<= 32;
  return addition_with_overflow_check(s, r);
}

所以这是两次乘法，两次移位，一些加法和条件检查。这可能比除法更有效，因为例如两个乘法可以并行流水线化。您必须进行基准测试，看看什么对您更有效。

于 2011-12-16T15:50:02.783 回答
1

与一些（希望）有用的答案相关的问题：Best way to detect integer overflow in C/C++。加上它不仅涵盖uint64_t;）

于 2011-12-16T13:30:45.993 回答
1 
case 6:
    for (a = 0; a < N; a++) {
        uint64_t b = a + c;
        uint64_t a1, b1;
        if (a > b) { a1 = a; b1 = b; }
        else       { a1 = b; b1 = a; }
        uint64_t cc = b1 * a1;
        c += cc;
        if (b1 > 0xffffffff) o++;
        else {
            uint64_t a1l = (a1 & 0xffffffff) + (a1 >> 32);
            a1l = (a1 + (a1 >> 32)) & 0xffffffff;
            uint64_t ab1l = a1l * b1;
            ab1l = (ab1l & 0xffffffff) + (ab1l >> 32);
            ab1l += (ab1l >> 32);
            uint64_t ccl = (cc & 0xffffffff) + (cc >> 32);
            ccl += (ccl >> 32);
            uint32_t ab32 = ab1l; if (ab32 == 0xffffffff) ab32 = 0;
            uint32_t cc32 = ccl; if (cc32 == 0xffffffff) cc32 = 0;
            if (ab32 != cc32) o++;
        }
    }
    break;

此方法将正常乘法的结果（可能溢出）与不会溢出的乘法结果进行比较。所有计算都是模数 (2^32 - 1)。

它比 Jens Gustedt 的方法更复杂并且（很可能）不快。

经过一些小的修改后，它可能会以 96 位精度相乘（但没有溢出控制）。更有趣的是，这种方法的思想可以用来检查一系列算术运算（乘法、加法、减法）的溢出。

回答了一些问题

首先，关于"your code is not portable". 是的，代码不可移植，因为它使用uint64_t原始问题中要求的。严格来说，您无法获得任何便携式答案，(u)int64_t因为它不是标准要求的。

关于"once some overflow happens, you can not assume the result value to be anything". 标准说未签名的迭代器不能溢出。第 6.2.5 章，第 9 项：

涉及无符号操作数的计算永远不会溢出，因为无法由结果无符号整数类型表示的结果会以比结果类型可以表示的最大值大一的数字为模减少。

因此无符号 64 位乘法以 2^64 为模执行，不会溢出。

现在关于"logic behind". “哈希函数”在这里不是正确的词。我只使用计算模数(2^32 - 1)。乘法的结果可以表示为n*2^64 + m，哪里m是可见的结果，n表示我们溢出了多少。既然2^64 = 1 (mod 2^32 - 1)，我们可以计算一下[true value] - [visible value] = (n*2^64 + m) - m = n*2^64 = n (mod 2^32 - 1)。如果计算的值n不为零，则存在溢出。如果为零，则没有溢出。只有在 之后才有可能发生任何碰撞n >= 2^32 - 1。这永远不会发生，因为我们检查了被乘数之一是否小于2^32。

于 2011-12-20T11:15:05.710 回答
1

它可能无法检测到确切的溢出，但通常您可以在对数尺度上测试乘法的结果：

if (log(UINT64_MAX-1) - log(a) - log(b) < 0) overflow_detected(); // subtracting 1 to allow some tolerance when the numbers are converted to double
else prod = a * b;

这取决于您是否真的需要进行精确到 UINT64_MAX 的乘法运算，否则这是检查大数乘法的一种非常便携且方便的方法。

于 2011-12-22T13:46:20.980 回答
1

还可以考虑使用编译器的内置函数：

bool __builtin_mul_overflow (type1 a, type2 b, type3 *res)

这个函数/宏至少在 gcc 和 clang 中定义（我没有检查过其他的）：

Clang 提供了一组内置函数，它们以在 C 中快速且易于表达的方式为安全关键型应用程序实现检查算法

几周前这里的这个答案会帮助我，但我终于找到了一个很好的答案，它更详细地介绍了内置函数： https ://stackoverflow.com/a/20956705/7113685

于 2022-01-27T18:41:29.263 回答