检测uint64_t整数溢出与C的乘法
是否有任何有效且可移植的方法来检查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 #include #include #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 a) o++; c += b * a; } break; case 2: /* using division */ for (a = 0; 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 UINT64_MAX / b) ) ) ) o++; c += b * a; } break; case 5: /* Jens Gustedt method */ for (a = 0; 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所示。
如果你想在Ambroz的答案中避免分裂：
首先你必须看到两个数字中较小的一个，比如a ，小于2 32 ，否则结果无论如何都会溢出。 令b被分解为两个32位字，即b = c 2 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); }
所以这是两次乘法，两次换档，一些加法和条件检查。 这可能比除法更有效，因为例如两个乘法可以并行流水线化。 您必须进行基准测试才能看到哪种方法更适合您。
实际上，相同的原理可用于乘法：
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;
对于类似的有符号整数，你可能需要为每个符号组合提供一个案例。
与一些（希望）有用的答案相关的问题： 在C / C ++中检测整数溢出的最佳方法 。 另外它不包括uint64_t ;）
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" 。 Standard表示无符号迭代不能溢出。 第6.2.5章，第9项：
涉及无符号操作数的计算永远不会溢出，因为无法通过生成的无符号整数类型表示的结果将以比结果类型可以表示的最大值大1的数量为模。
因此，无符号的64位乘法以2 ^ 64为模进行，没有溢出。
现在关于"logic behind"的"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 。
它可能无法检测到确切的溢出，但通常您可以在对数刻度上测试乘法的结果：
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，否则这是检查大数乘法的一种非常便携和方便的方法。