我用c++写了一个程序来寻找ab = C的所有解，其中a, b和C一起使用所有的数字0-9，只使用一次。程序循环遍历a和b的值，并每次对a、b和ab运行数字计数例程，以检查是否满足数字条件。
但是，当ab超出整数限制时，会产生伪解。我最终使用如下代码来检查这个:
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++访问它。
注意，有符号int溢出在C和c++中是未定义的行为，因此您必须在不实际引起它的情况下检测它。对于加法前的有符号整型溢出，请参见在C/ c++中检测有符号溢出。
当前回答
Clang现在支持有符号整数和无符号整数的动态溢出检查。参见-fsanitize=integer开关。目前，它是唯一完全支持用于调试目的的动态溢出检查的c++编译器。
其他回答
从C23开始，标准头文件<stdckdint.h>提供了以下三个类函数宏:
bool ckd_add(type1 *result, type2 a, type3 b);
bool ckd_sub(type1 *result, type2 a, type3 b);
bool ckd_mul(type1 *result, type2 a, type3 b);
其中type1, type2和type3是任何整数类型。这些函数分别以任意精度对a和b进行加、减或乘，并将结果存储在*result中。如果结果不能由type1精确表示，则函数返回true("计算已溢出")。(任意精确是一种错觉;计算速度非常快，自20世纪90年代初以来几乎所有可用的硬件都可以在一个或两个指令内完成。)
重写OP的例子:
unsigned long b, c, c_test;
// ...
if (ckd_mul(&c_test, c, b))
{
// returned non-zero: there has been an overflow
}
else
{
c = c_test; // returned 0: no overflow
}
C_test包含所有情况下可能溢出的乘法结果。
早在C23之前，GCC 5+和Clang 3.8+就提供了以同样方式工作的内置程序，除了结果指针是最后传递而不是第一个传递:__builtin_add_overflow， __builtin_sub_overflow和__builtin_mul_overflow。这些也适用于小于int的类型。
unsigned long b, c, c_test;
// ...
if (__builtin_mul_overflow(c, b, &c_test))
{
// returned non-zero: there has been an overflow
}
else
{
c = c_test; // returned 0: no overflow
}
Clang 3.4+引入了具有固定类型的算术溢出内置函数，但它们的灵活性要低得多，而且Clang 3.8现在已经可用很长时间了。如果你需要使用__builtin_umull_overflow，尽管有更方便的更新选项。
Visual Studio的cl.exe没有直接的等价物。对于无符号加减法，包括<intrin.h>将允许您使用addcarry_uNN和subborrow_uNN(其中NN是位数，如addcarry_u8或subborrow_u64)。他们的签名有点迟钝:
unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum);
unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);
C_in /b_in是输入的进位/借位标志，返回值是输出的进位/借位。它似乎没有符号运算或乘法的等价物。
另外，Clang for Windows现在已经可以投入生产(对于Chrome来说已经足够好了)，所以这也是一个选择。
我看到你用的是无符号整数。根据定义，在C中(我不了解c++)，无符号算术不会溢出…所以，至少对C来说，你的观点是没有意义的:)
对于有符号整数，一旦出现溢出，就会发生未定义行为(UB)，程序可以做任何事情(例如:使测试不确定)。
#include <limits.h>
int a = <something>;
int x = <something>;
a += x; /* UB */
if (a < 0) { /* Unreliable test */
/* ... */
}
要创建一个符合要求的程序，您需要在生成溢出之前测试溢出。该方法也可以用于无符号整数:
// 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 (x != 0 && a > INT_MAX / x) // `a * x` would overflow
if (x != 0 && a < INT_MIN / x) // `a * x` would underflow
对于除法(INT_MIN和-1特殊情况除外)，不可能超过INT_MIN或INT_MAX。
尝试这个宏来测试32位机器的溢出位(改编自Angel Sinigersky的解决方案)
#define overflowflag(isOverflow){ \
size_t eflags; \
asm ("pushfl ;" \
"pop %%eax" \
: "=a" (eflags)); \
isOverflow = (eflags >> 11) & 1;}
我将其定义为宏，因为否则溢出位将被覆盖。
下面是上面代码段的一个小应用程序:
#include <cstddef>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#if defined( _MSC_VER )
#include <intrin.h>
#include <oskit/x86>
#endif
using namespace std;
#define detectOverflow(isOverflow){ \
size_t eflags; \
asm ("pushfl ;" \
"pop %%eax" \
: "=a" (eflags)); \
isOverflow = (eflags >> 11) & 1;}
int main(int argc, char **argv) {
bool endTest = false;
bool isOverflow;
do {
cout << "Enter two intergers" << endl;
int x = 0;
int y = 0;
cin.clear();
cin >> x >> y;
int z = x * y;
detectOverflow(isOverflow)
printf("\nThe result is: %d", z);
if (!isOverflow) {
std::cout << ": no overflow occured\n" << std::endl;
} else {
std::cout << ": overflow occured\n" << std::endl;
}
z = x * x * y;
detectOverflow(isOverflow)
printf("\nThe result is: %d", z);
if (!isOverflow) {
std::cout << ": no overflow ocurred\n" << std::endl;
} else {
std::cout << ": overflow occured\n" << std::endl;
}
cout << "Do you want to stop? (Enter \"y\" or \"Y)" << endl;
char c = 0;
do {
c = getchar();
} while ((c == '\n') && (c != EOF));
if (c == 'y' || c == 'Y') {
endTest = true;
}
do {
c = getchar();
} while ((c != '\n') && (c != EOF));
} while (!endTest);
}
最简单的方法是将unsigned long转换为unsigned long，进行乘法运算，并将结果与0x100000000LL进行比较。
你可能会发现这比你在例子中做除法更有效。
哦，它在C和c++中都可以工作(因为你已经用这两种语言标记了问题)。
我在看glibc手册。这里提到了整数溢出陷阱(FPE_INTOVF_TRAP)作为SIGFPE的一部分。这将是理想的，除了手册中令人讨厌的部分:
FPE_INTOVF_TRAP 整数溢出(在C程序中不可能，除非您以特定于硬件的方式启用溢出捕获)。
真的有点遗憾。
I see that a lot of people answered the question about overflow, but I wanted to address his original problem. He said the problem was to find ab=c such that all digits are used without repeating. Ok, that's not what he asked in this post, but I'm still think that it was necessary to study the upper bound of the problem and conclude that he would never need to calculate or detect an overflow (note: I'm not proficient in math so I did this step by step, but the end result was so simple that this might have a simple formula).
重点是问题要求的a b c的上限是98.765.432。不管怎样，先把问题分成琐碎部分和非琐碎部分:
X0 == 1(9、8、7、6、5、4、3、2的所有排列都是解) X1 == x(无解) 0b == 0(不可能解) 1b == 1(无解) Ab, a > 1, b > 1(非平凡)
Now we just need to show that no other solution is possible and only the permutations are valid (and then the code to print them is trivial). We go back to the upper bound. Actually the upper bound is c ≤ 98.765.432. It's the upper bound because it's the largest number with 8 digits (10 digits total minus 1 for each a and b). This upper bound is only for c because the bounds for a and b must be much lower because of the exponential growth, as we can calculate, varying b from 2 to the upper bound:
9938.08^2 == 98765432
462.241^3 == 98765432
99.6899^4 == 98765432
39.7119^5 == 98765432
21.4998^6 == 98765432
13.8703^7 == 98765432
9.98448^8 == 98765432
7.73196^9 == 98765432
6.30174^10 == 98765432
5.33068^11 == 98765432
4.63679^12 == 98765432
4.12069^13 == 98765432
3.72429^14 == 98765432
3.41172^15 == 98765432
3.15982^16 == 98765432
2.95305^17 == 98765432
2.78064^18 == 98765432
2.63493^19 == 98765432
2.51033^20 == 98765432
2.40268^21 == 98765432
2.30883^22 == 98765432
2.22634^23 == 98765432
2.15332^24 == 98765432
2.08826^25 == 98765432
2.02995^26 == 98765432
1.97741^27 == 98765432
注意，例如最后一行:它说1.97^27 ~98M。因此，例如，1^27 == 1和2^27 == 134.217.728，这不是一个解决方案，因为它有9位数字(2 > 1.97，所以它实际上比应该测试的要大)。可以看到，用于测试a和b的组合非常小。对于b == 14，我们需要尝试2和3。对于b == 3，我们从2开始，到462结束。结果均小于~98M。
现在只需测试以上所有的组合，找出不重复任何数字的组合:
['0', '2', '4', '5', '6', '7', '8'] 84^2 = 7056
['1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481
['0', '1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481 (+leading zero)
['1', '2', '3', '5', '8'] 8^3 = 512
['0', '1', '2', '3', '5', '8'] 8^3 = 512 (+leading zero)
['1', '2', '4', '6'] 4^2 = 16
['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
['1', '2', '4', '6'] 2^4 = 16
['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
['1', '2', '8', '9'] 9^2 = 81
['0', '1', '2', '8', '9'] 9^2 = 81 (+leading zero)
['1', '3', '4', '8'] 3^4 = 81
['0', '1', '3', '4', '8'] 3^4 = 81 (+leading zero)
['2', '3', '6', '7', '9'] 3^6 = 729
['0', '2', '3', '6', '7', '9'] 3^6 = 729 (+leading zero)
['2', '3', '8'] 2^3 = 8
['0', '2', '3', '8'] 2^3 = 8 (+leading zero)
['2', '3', '9'] 3^2 = 9
['0', '2', '3', '9'] 3^2 = 9 (+leading zero)
['2', '4', '6', '8'] 8^2 = 64
['0', '2', '4', '6', '8'] 8^2 = 64 (+leading zero)
['2', '4', '7', '9'] 7^2 = 49
['0', '2', '4', '7', '9'] 7^2 = 49 (+leading zero)
没有一个匹配问题(这也可以通过缺少'0'，'1'，…“9”)。
下面是解决该问题的示例代码。还要注意，这是用Python编写的，不是因为它需要任意精确整数(代码不会计算任何大于9800万的数字)，而是因为我们发现测试的数量非常少，所以我们应该使用高级语言来利用其内置的容器和库(还要注意:代码有28行)。
import math
m = 98765432
l = []
for i in xrange(2, 98765432):
inv = 1.0/i
r = m**inv
if (r < 2.0): break
top = int(math.floor(r))
assert(top <= m)
for j in xrange(2, top+1):
s = str(i) + str(j) + str(j**i)
l.append((sorted(s), i, j, j**i))
assert(j**i <= m)
l.sort()
for s, i, j, ji in l:
assert(ji <= m)
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d' % (s, i, j, ji)
# Try with non significant zero somewhere
s = ['0'] + s
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)
