检测uint64_t整数溢出与C的乘法

Question

是否有任何有效且可移植的方法来检查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所示.

Answer 1

实际上,相同的原理可用于乘法:

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;

对于类似的有符号整数,你可能需要为每个符号组合提供一个案例.

Answer 2

如果你想在Ambroz的答案中避免分裂:

首先你必须看到两个数字中较小的一个,比如说a,小于2 ³²,否则结果无论如何都会溢出.让我们b分解为两个32位字b= c2 ³² + 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);
}

所以这是两次乘法,两次换档,一些加法和条件检查.这可能比除法更有效,因为例如两个乘法可以并行流水线化.您必须进行基准测试才能看到哪些更适合您.