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

发布时间：2020-12-13 20:26:39 所属栏目：Windows 来源：网络整理

导读：当使用int64_t或uint64_t操作数的乘法运算在C中溢出时,是否有任何高效便捷的方式？例如,为了添加uint64_t,我可以做： if (UINT64_MAX - a b) overflow_detected();else sum = a + b; 但是我不能得到一个类似的简单的乘法表达式. 所有这一切发生在我身上,将

当使用int64_t或uint64_t操作数的乘法运算在C中溢出时,是否有任何高效便捷的方式？

例如,为了添加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: %un",c,o);
}

到目前为止,使用浮点过滤大多数情况的情况4是最快的,当假定溢出是非常不寻常的,至少在我的电脑上,它比无人操作的情况下慢两倍.

情况5比4慢了30％,但它总是执行相同的,没有任何特殊的案例编号需要较慢的处理,就像4发生的那样.

如果你想避免在Ambroz的答案中划分：

首先你必须看到两个数字中的较小的一个,比如a,小于232,否则结果会溢出.令b被分解为b = c 232 d的两个32位字.

那么计算不是那么难,我发现：

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);
}

所以这是两次乘法,两班,一些补充和条件检查.这可能比划分更有效率,因为例如两个乘法可以并行流水线.您必须进行基准测试,才能看到更适合您的功能.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!