我用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 ++中是未定义的行为，因此您必须检测它而不实际导致它。对于添加前的signed int overflow，请参阅Detecting signed overflow in C/C++。
我看到你正在使用无符号整数。根据定义，在C（不知道C ++）中，无符号算术不会溢出...所以，至少对于C来说，你的观点是没有意义的:)
对于有符号整数，一旦出现溢出，就会发生Undefined Behaviour并且您的程序可以执行任何操作（例如：渲染测试不确定）。
#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 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。
最简单的方法是将uint64_ts转换为callocs，进行乘法运算，并将结果与0x100000000LL进行比较。
你可能会发现这比你在你的例子中所做的更有效。
哦，它可以在C和C ++中工作（因为你用两者标记了问题）。
刚刚看了看unsigned long。有一个整数溢流陷阱（unsigned long long）作为glibc manual的一部分提到。除了手册中讨厌的内容之外，这将是理想的：
FPE_INTOVF_TRAP整数溢出（除非您以特定于硬件的方式启用溢出捕获，否则在C程序中是不可能的）。
真的有点遗憾。
虽然已经有两年了，但我觉得我还可以加入我的penithworth，以便以极快的速度检测溢出，至少可以添加，这可能会带来乘法，除法和幂
这个想法正是因为处理器只是让值回退到零并且C / C ++是从任何特定处理器中抽象出来的，你可以：
SIGFPE这两者都确保如果一个操作数为零而一个操作数不为零，则不会错误地检测到溢出，并且明显快于之前建议的许多NOT / XOR / AND /测试操作。
编辑：正如所指出的，这种方法虽然比其他更精细的方法更好，但仍然是可以优化的。以下是包含优化的原始代码的修订版：
FPE_INTOVF_TRAP对于无符号整数，只需检查结果是否小于其中一个参数：
uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);
对于有符号整数，您可以检查参数和结果的符号。不同符号的整数不能溢出，只有相同符号溢出的整数才会产生不同的符号：
uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < x; // Alternatively "value < y" should also work
您无法从C / C ++访问溢出标志。
某些编译器允许您将陷阱指令插入代码中。在海湾合作委员会，选项是-ftrapv（但我必须承认我从未使用过它。将在发布后检查）。
您可以做的唯一便携和编译器独立的事情是自己检查溢出。就像你在你的例子中所做的那样。
编辑：
刚检查：-ftrapv似乎在使用最新的GCC的x86上什么也没做。猜猜它是旧版本遗留下来的，或者特定于其他一些架构。我曾期望编译器在每次添加后插入INTO操作码。不幸的是，它没有这样做。
对于浮点数，我需要回答同样的问题，其中位掩码和移位看起来并不乐观。我确定的方法适用于有符号和无符号，整数和浮点数。即使没有更大的数据类型可用于中间计算，它仍然有效。对于所有这些类型而言，它并不是最有效的，但因为它确实适用于所有这些类型，所以值得使用。
签名溢出测试，加法和减法：
签名溢出测试，乘法和除法：
注意：MINVALUE的最小溢出由3处理，因为我们采用了绝对值。但是，如果ABS（MINVALUE）> MAXVALUE，那么我们将会有一些罕见的误报。
下溢测试类似，但涉及EPSILON（最大正数大于零）。
CERT开发了一种新方法，使用“as-if”无限范围（AIR）整数模型检测和报告有符号整数溢出，无符号整数包装和整数截断。 CERT发布了描述该模型的unsigned int r, a, b;
r = a+b;
if (r < a)
{
// overflow
}
，并根据GCC 4.4.0和GCC 4.5.0生成了一个工作原型。
AIR整数模型生成的值等于使用无限范围整数获得的值，或者导致运行时约束违规。与以前的整数模型不同，AIR整数不需要精确的陷阱，因此不会破坏或抑制大多数现有的优化。
另一个有趣的工具：signed int r, a, b, s;
r = a+b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
// overflow
}
这是一个修补的technical report编译器，它在编译时向代码添加检查。所以你得到的输出看起来像这样：
http://embed.cs.utah.edu/ioc/
使用汇编程序的另一种解决方案是外部程序。这个例子用于在linux x64下使用g ++和fasm进行无符号整数乘法。
此过程将两个无符号整数参数（32位）相乘（根据clang为amd64（第3.2.3节参数传递）
如果类是INTEGER，则使用序列％rdi，％rsi，％rdx，％rcx，％r8和％r9的下一个可用寄存器
（edi和esi在我的代码中注册））并返回结果，如果发生溢出则返回0。
CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1
测试：
specification
链接程序与asm目标文件。在我的Qt Creator中，将它添加到.pro文件中的LIBS
试试这个宏来测试32位机器的溢出位（改编了Angel Sinigersky的解决方案）
format ELF64
section '.text' executable
public u_mul
u_mul:
MOV eax, edi
mul esi
jnc u_mul_ret
xor eax, eax
u_mul_ret:
ret
我将其定义为宏，否则溢出位将被覆盖。
后续是上面代码段的一个小应用程序：
extern "C" unsigned int u_mul(const unsigned int a, const unsigned int b);
int main() {
printf("%u\n", u_mul(4000000000,2));//0
printf("%u\n", u_mul(UINT_MAX/2,2));//ok
return 0;
}
用双精度计算结果。他们有15位有效数字。你的要求在c的108上有一个硬上限 - 它最多可以有8位数。因此，如果它在范围内，结果将是精确的，否则它将不会溢出。
有一种方法可以确定操作是否可能溢出，使用操作数中最重要的一位的位置和一些基本的二进制数学知识。
另外，任何两个操作数将导致（最多）比最大操作数的最高一位多一位。例如：
bool addition_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
return (a_bits<32 && b_bits<32);
}
对于乘法，任何两个操作数将导致（最多）操作数的位总和。例如：
bool multiplication_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
return (a_bits+b_bits<=32);
}
同样，您可以将a结果的最大大小估计为b的幂，如下所示：
bool exponentiation_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a);
return (a_bits*b<=32);
}
（当然，替换目标整数的位数。）
我不确定以最快的方式确定数字中最高的一位的位置，这是一种强力方法：
size_t highestOneBitPosition(uint32_t a) {
size_t bits=0;
while (a!=0) {
++bits;
a>>=1;
};
return bits;
}
它并不完美，但是在你进行操作之前，这会让你知道任何两个数字是否会溢出。我不知道它是否比简单地以你建议的方式检查结果更快，因为highestOneBitPosition函数中的循环，但它可能（特别是如果你事先知道操作数中有多少位）。
您无法从C / C ++访问溢出标志。
我不同意这一点。您可以编写一些内联asm并使用#define overflowflag(isOverflow){ \
size_t eflags; \
asm ("pushfl ;" \
"pop %%eax" \
: "=a" (eflags)); \
isOverflow = (eflags >> 11) & 1;}
（跳转溢出）指令，假设您在x86上捕获溢出。当然，您的代码将不再可移植到其他架构。
看看#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);
}
和jo。
info as指出了一个比CERT讨论的更通用的解决方案（它在处理类型方面更为通用），即使它需要一些GCC扩展（我不知道它们有多广泛支持）。
为了扩展Head Geek的答案，有一个更快的方法来做info gcc;
Catching Integer Overflows in C
这使用机器架构安全，因为64位和32位无符号整数仍然可以正常工作。基本上，我创建了一个掩盖除了最重要的位之外的所有掩码。然后，我屏蔽了两个整数，如果其中任何一个没有设置该位，那么添加是安全的。
如果你在某个构造函数中预先初始化蒙版，这会更快，因为它永远不会改变。
x86指令集包括无符号乘法指令，用于将结果存储到两个寄存器。要使用C中的指令，可以在64位程序（gcc）中编写以下代码：
addition_is_safe对于32位程序，需要将结果设为64位，参数为32位。
另一种方法是使用编译器依赖本能来检查标志寄存器。关于溢出本能的GCC文档可以从bool addition_is_safe(unsigned int a, unsigned int b)
{
unsigned int L_Mask = std::numeric_limits<unsigned int>::max();
L_Mask >>= 1;
L_Mask = ~L_Mask;
a &= L_Mask;
b &= L_Mask;
return ( a == 0 || b == 0 );
}
找到
unsigned long checked_imul(unsigned long a, unsigned long b) {
__int128 res = (__int128)a * (__int128)b;
if ((unsigned long)(res >> 64))
printf("overflow in integer multiply");
return (unsigned long)res;
}
为整数类型https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html提供溢出检查整数数学（使用clang和gcc上的编译器内在函数）。代码在MPL 2.0下，依赖于三个（mozilla::CheckedInt<T>，T和IntegerTypeTraits.h）其他仅标头的非标准库头以及Mozilla特定的Attributes.h。如果导入代码，您可能希望替换断言机制。
一个干净的方法是覆盖所有运算符（特别是+和*）并在执行操作之前检查溢出。
内联汇编允许您直接检查溢出位。如果你打算使用C ++，你真的应该学习汇编。
这取决于你使用它。执行无符号长（DWORD）加法或乘法最佳解决方案是使用ULARGE_INTEGER。
ULARGE_INTEGER是两个DWORD的结构。完整值可以作为“QuadPart”访问，而hi DWORD作为“HighPart”访问，低DWORD作为“LowPart”访问
例如：
DWORD我的加法（DWORD Value_A，DWORD Value_B）{ULARGE_INTEGER a，b;
assertion machinery
//任何溢出都存储在a.HighPart中（最多32位）
要以可移植的方式执行无符号乘法而不溢出，可以使用以下内容：
uint64_t foo( uint64_t a, uint64_t b ) {
double dc;
dc = pow( a, b );
if ( dc < UINT_MAX ) {
return ( powu64( a, b ) );
}
else {
// overflow
}
}
Clang 3.4+和GCC 5+提供检查算术内置。它们为这个问题提供了一个非常快速的解决方案，特别是与比特测试安全检查相比。
对于OP问题中的示例，它可以这样工作：
unsigned long b, c, c_test;
if (__builtin_umull_overflow(b, c, &c_test))
{
// returned non-zero: there has been an overflow
}
else
{
// return zero: there hasn't been an overflow
}
如果发生溢出，Clang文档没有说明c_test是否包含溢出的结果，但是GCC文档说它确实存在溢出。鉴于这两个类似于__builtin兼容，可以安全地假设这也是Clang的工作方式。
每个算术运算都有一个__builtin，它可以溢出（加法，减法，乘法），有符号和无符号变量，适用于int尺寸，长尺寸和长长尺寸。名称的语法是__builtin_[us](operation)(l?l?)_overflow：
u签署无签名或s;add，sub或mul之一;l后缀意味着操作数是ints;一个l意味着long;两个ls意味着long long。因此对于经过检查的有符号长整数，它将是__builtin_saddl_overflow。完整列表可以在Clang documentation page上找到。
GCC 5+和Clang 3.8+还提供通用内置函数，无需指定值的类型即可工作：__builtin_add_overflow，__builtin_sub_overflow和__builtin_mul_overflow。这些也适用于比int小的类型。
内置程序降低到平台最佳状态。在x86上，它们检查进位，溢出和符号标志。
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);
qazxsw poi / qazxsw poi是输入的进位/借位标志，返回值是输出的进位/借位。它似乎没有签名操作或乘法的等价物。
否则，Clang for Windows现在可以投入生产（对Chrome来说已经足够了），所以这也是一个选择。
b.LowPart = Value_A; // a 32 bit value(up to 32 bit)
b.HighPart = 0;
a.LowPart = Value_B; // a 32 bit value(up to 32 bit)
a.HighPart = 0;
a.QuadPart += b.QuadPart;
// if a.HighPart
// Then a.HighPart contains the overflow(carry)
return (a.LowPart + a.HighPart)
有些编译器可以访问CPU中的整数溢出标志，然后可以测试，但这不是标准的。
您还可以在执行乘法之前测试溢出的可能性：
c_in警告：GCC可以在使用b_in进行编译时优化掉溢出检查。选项if ( b > ULONG_MAX / a ) // a * b would overflow
会在某些情况下给你一个警告
-O2但不是在这个例子中：
-Wall唯一安全的方法是在它发生之前检查溢出，如if (a + b < a) { /* deal with overflow */ }
中所述，系统使用这将是非常繁琐的。
使用b = abs(a);
if (b < 0) { /* deal with overflow */ }
进行编译可以解决问题，但会禁用一些优化。
我们迫切需要一个更好的解决方案。我认为编译器在进行依赖于不发生溢出的优化时应默认发出警告。目前的情况允许编译器优化掉溢出检查，这在我看来是不可接受的。
clang现在支持有符号和无符号整数的动态溢出检查。请参阅CERT paper开关。目前，只有一个C ++编译器具有完全支持的动态溢出检查以用于调试目的。
我看到很多人回答了关于溢出的问题，但我想解决他原来的问题。他说问题是找到ab = c这样所有的数字都可以使用而不重复。好吧，这不是他在这篇文章中提到的，但我仍然认为有必要研究问题的上限，并得出结论他永远不需要计算或检测溢出（注意：我不熟练）在数学中所以我一步一步地做了这一点，但最终的结果是如此简单，以至于这可能有一个简单的公式）。
重点是问题所需的a，b或c的上限是98.765.432。无论如何，首先将问题分解为琐碎和非平凡的部分：
现在我们只需要表明没有其他解决方案是可能的，只有排列是有效的（然后打印它们的代码是微不足道的）。我们回到上限。实际上，上限是c≤98.765.432。它是上限，因为它是8位数的最大数字（总共10位数，每个a和b减去1）。这个上限仅适用于c，因为a和b的界限必须低得多，因为我们可以计算出指数增长，b从2到上限变化：
-fwrapv注意，例如最后一行：它表示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。
现在只测试上面的所有组合，并寻找不重复任何数字的组合：
-fsanitize=integer
它们都不匹配问题（也可以通过缺少'0'，'1'，......，'9'来看到）。
解决它的示例代码如下。还要注意用python编写的，不是因为它需要任意精度整数（代码不能计算超过9800万的任何东西），但是因为我们发现测试的数量太少以至于我们应该使用高级语言来利用其内置容器和库（另请注意：代码有28行）。
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
这是一个问题的“非便携式”解决方案。 Intel x86和x64 CPU具有所谓的EFLAGS寄存器（ ['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)
），在每次整数算术运算后由处理器填充。我将在这里略过详细说明。相关标志是“溢出”标志（掩码0x800）和“进位”标志（掩码0x1）。要正确解释它们，应该考虑操作数是有符号还是无符号类型。
这是检查C / C ++标志的实用方法。以下代码适用于Visual Studio 2005或更高版本（32位和64位）以及GNU C / C ++ 64位。
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)
如果操作数相乘而没有溢出，则从query_intel_eflags（0x801）得到返回值0，即进位和溢出标志都没有设置。在提供的main（）示例代码中，发生溢出，并且两个标志都设置为1.此检查并不意味着任何进一步的计算，因此它应该非常快。
如果您的数据类型大于您要测试的数据类型（假设您执行32位添加并且您具有64位类型）。然后这将检测是否发生溢出。我的例子是8位加法。但可以扩大规模。
http://en.wikipedia.org/wiki/EFLAGS
它基于此页面上解释的概念：#include <cstddef>
#if defined( _MSC_VER )
#include <intrin.h>
#endif
inline size_t query_intel_x86_eflags( const size_t query_bit_mask )
{
#if defined( _MSC_VER )
return __readeflags() & query_bit_mask;
#elif defined( __GNUC__ )
// this code will work only on 64-bit GNU-C machines;
// Tested and does NOT work with Intel C++ 10.1!
size_t eflags;
__asm__ __volatile__(
"pushfq \n\t"
"pop %%rax\n\t"
"movq %%rax, %0\n\t"
:"=r"(eflags)
:
:"%rax"
);
return eflags & query_bit_mask;
#else
#pragma message("No inline assembly will work with this compiler!")
return 0;
#endif
}
int main(int argc, char **argv)
{
int x = 1000000000;
int y = 20000;
int z = x * y;
int f = query_intel_x86_eflags( 0x801 );
printf( "%X\n", f );
}
对于一个32位的例子，uint8_t x, y; /* give these values */
const uint16_t data16 = x + y;
const bool carry = (data16 > 0xff);
const bool overflow = ((~(x ^ y)) & (x ^ data16) & 0x80);
变成http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html，0xff变成0xffffffff，最后0x80变成0x80000000。
注意：这会捕获整数加法/减法溢出，我意识到你的问题涉及乘法。在这种情况下，划分可能是最好的方法。这通常是uint16_t实现确保params不会溢出的方式，因为它们相乘以获得最终大小。