如何检测无符号整数乘法溢出？ [英] How do I detect unsigned integer multiply overflow?

问题描述

我正在用C ++编写程序，以找到 a ^b = c 的所有解决方案，其中 a ， b 和 c 一起使用所有数字0-9一次。程序循环遍历 a 和 b 的值，并且每次在 a ， b 和 a ^b 来检查数字条件是否满足。

I was writing a program in C++ to find all solutions of a^b = c, where a, b and c together use all the digits 0-9 exactly once. The program looped over values of a and b, and it ran a digit-counting routine each time on a, b and a^b to check if the digits condition was satisfied.

但是，可以生成虚假解当 a ^b 溢出整数限制时。我最终使用如下代码检查了这一点：

However, spurious solutions can be generated when a^b overflows the integer limit. I ended up checking for this using code like:

unsigned long b, c, c_test;
...
c_test=c*b;         // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test;      // No overflow

是否有更好的溢出测试方法？我知道有些芯片的内部标志会在发生溢出时设置，但是我从未见过通过C或C ++访问它。

Is there a better way of testing for overflow? I know that some chips have an internal flag that is set when overflow occurs, but I've never seen it accessed through C or C++.

请注意， 签名 int 溢出在C和C ++中是未定义的行为，因此您必须在没有实际造成的情况下进行检测。有关添加前已签名的int溢出的信息，请参见 在C / C ++中检测已签名的溢出 。

Beware that signed int overflow is undefined behaviour in C and C++, and thus you have to detect it without actually causing it. For signed int overflow before addition, see Detecting signed overflow in C/C++.

推荐答案

我看到您正在使用无符号整数。按照定义，在C 中（我对C ++不了解），无符号算术不会溢出...因此，至少对于C，您的观点很无聊：）

I see you're using unsigned integers. By definition, in C (I don't know about C++), unsigned arithmetic does not overflow ... so, at least for C, your point is moot :)

带符号整数，一旦溢出，不确定的行为（ UB）已发生，您的程序可以执行任何操作（例如：不确定性的渲染测试。）

With signed integers, once there has been overflow, undefined behaviour (UB) has occurred and your program can do anything (for example: render tests inconclusive). 

#include <limits.h>

int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* Unreliable test */
  /* ... */
}

要创建符合标准的程序，您需要在生成之前对溢出进行测试。该方法也可以与无符号整数一起使用：

To create a conforming program, you need to test for overflow before generating said overflow. The method can be used with unsigned integers too:

// For addition
#include <limits.h>

int a = <something>;
int x = <something>;
if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */;
if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */;

---

---

// For subtraction
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x < 0) && (a > INT_MAX + x)) /* `a - x` would overflow */;
if ((x > 0) && (a < INT_MIN + x)) /* `a - x` would underflow */;

---

---

// For multiplication
#include <limits.h>

int a = <something>;
int x = <something>;
// There may be a need to check for -1 for two's complement machines.
// If one number is -1 and another is INT_MIN, multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */
// general case
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;

---

除法（ INT_MIN 和 -1 的特殊情况），则不可能超过 INT_MIN 或 INT_MAX 。

---

For division (except for the INT_MIN and -1 special case), there isn't any possibility of going over INT_MIN or INT_MAX.

这篇关于如何检测无符号整数乘法溢出？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！