我正在使用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++中看到它被访问过。
请注意，在C和C++中，带符号int溢出是未定义行为，因此您必须在不实际引起溢出的情况下进行检测。关于加法之前的带符号整数溢出，请参见Detecting signed overflow in C/C++。
#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。
x >= 0，x > 0 就足够了（如果 x == 0，那么由于明显的原因 x + a 不会溢出）。 - caf(a < INT_MIN / x) 的测试过于晚了。首先需要一项 if (x == -1) 的测试。 - chux - Reinstate Monica15 * -6734，结果为-101010，但测试将表示它会溢出。 - dot_Sp0T从 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);
另外，现在 Windows 版本的 Clang 已经可以投入生产（足够好用，适合 Chrome），所以这也是一个选择。
INT_MIN / -1，因为在通常的二进制补码表示中，abs(INT_MIN) == INT_MAX + 1），但似乎没有相应的内置函数。 - j_random_hacker通过使用操作数的最高有效位的位置和一些基本的二进制数学知识，有一种方法可以确定操作是否可能溢出。
对于加法，任何两个操作数将导致结果比最大操作数的最高有效位多一个位。例如：
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);
}
（当然，将目标整数的位数替换为实际位数。）
我不确定确定一个数中最高位是1的位置最快的方法是什么，这里有一种蛮力的方法：
size_t highestOneBitPosition(uint32_t a) {
size_t bits=0;
while (a!=0) {
++bits;
a>>=1;
};
return bits;
}
虽然不完美，但这可以让你了解在进行操作之前是否会发生溢出。我不知道它是否比你建议的方式简单地检查结果更快，因为在 highestOneBitPosition 函数中有循环，但如果事先知道操作数中有多少位，它可能会更快。
log2是相同的，但对于没有数学背景的人来说，这可能不太明显。 - Head Geekmultiplication_is_safe函数，0x8000 * 0x10000会溢出（位数为16+17=33，大于32），尽管实际上并没有溢出，因为0x8000 * 0x10000 = 0x80000000，显然仍适用于无符号32位整数。这只是该代码无法处理的许多示例之一。例如：0x8000 * 0x10001... - Michiif ( b > ULONG_MAX / a ) // a * b would overflow
b == ULONG_MAX / a 呢？那么它仍然可以适合，只要 a 可以整除 ULONG_MAX。 - the swine警告：使用-O2编译时，GCC可能会优化掉溢出检查。选项-Wall在某些情况下会给你一个警告，比如：
if (a + b < a) { /* Deal with overflow */ }
但不适用于这个例子：
b = abs(a);
if (b < 0) { /* Deal with overflow */ }
唯一安全的方法是在溢出发生之前检查，就像CERT文件中所述，但这将极为繁琐而难以系统化地使用。
使用-fwrapv编译可以解决问题，但会禁用一些优化。
我们迫切需要更好的解决方案。我认为编译器在进行依赖于不发生溢出的优化时，默认情况下应发出警告。目前的情况允许编译器优化掉溢出检查，我认为这是不可接受的。
for(int k = 0; k < 5; k++) {...} 应该会引发一个警告吗？ - user253751k 的值可以在编译时轻松确定，编译器不必做出任何假设。 - MikeMBn的低5位的移位指令之前，编译器不会检查n是否小于32。 - user253751这是一种非常快速的检测加法溢出的方法，可能会为乘法、除法和幂提供线索。
这个想法是由于处理器会让值回环到零，并且C/C++与任何特定的处理器都太抽象，因此您可以：
uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);
这样做可以确保如果一个操作数为零，而另一个不是，那么不会错误地检测到溢出，并且比之前建议的许多NOT/XOR/AND/test操作快得多。
正如所指出的那样，尽管这种方法比其他更为复杂的方式要好，但仍然可以进行优化。以下是包含优化的原始代码修订版本：
uint32_t x, y;
uint32_t value = x + y;
const bool overflow = value < x; // Alternatively "value < y" should also work
检测乘法溢出更高效、成本更低的方法是：
uint32_t x, y;
const uint32_t a = (x >> 16U) * (y & 0xFFFFU);
const uint32_t b = (x & 0xFFFFU) * (y >> 16U);
const bool overflow = ((x >> 16U) * (y >> 16U)) +
(a >> 16U) + (b >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;
这会导致在溢出时返回UINT32_MAX，或者返回乘法的结果。 在此情况下允许有符号整数进行乘法运算是严格未定义的行为。
值得注意的是，这使用部分Karatsuba方法乘法分解来计算64位乘法的高32位，以检查它们中是否有任何一个应该被设置为知道32位乘法溢出。
如果使用C ++，您可以将其转换为一个小而简洁的lambda表达式来计算溢出，以隐藏掉检测器的内部工作：
uint32_t x, y;
const bool overflow
{
[](const uint32_t x, const uint32_t y) noexcept -> bool
{
const uint32_t a{(x >> 16U) * uint16_t(y)};
const uint32_t b{uint16_t(x) * (y >> 16U)};
return ((x >> 16U) * (y >> 16U)) + (a >> 16U) + (b >> 16U);
}(x, y)
};
uint32_t value{overflow ? UINT32_MAX : x * y};
x+y>=256 且 value=x+y-256。由于 y<256 总是成立，因此 (y-256) 为负数，因此 value < x 总是成立的。非溢出情况的证明也是相似的。 - Gunther Piezuint32_t x[N], y[N], z[N], carry=0; for (int i = 0; i < N; i++) { z[i] = x[i] + y[i] + carry; carry = z[i] < (x[i] | y[i]); } 如果您不使用or运算符来计算值，就不能区分其中一个操作数和进位位为零以及一个操作数为 0xffffffff 而进位位为 1 的情况。 - Mattx[i]和y[i]都是0xFFFFFFFF且carry为1时，这种方法会失败。在加上进位之前，您必须先测试是否溢出，而此时您可能会放弃使用|。 - yuri kilochek我看到很多人回答了关于溢出的问题，但我想解决他的原始问题。他说问题是要找到一个b=c的a，使得所有数字都不重复。好吧，在这篇文章中他没有问这个，但我仍然认为有必要研究问题的上限并得出结论，他永远不需要计算或检测溢出（注意：我不精通数学，所以我一步一步地做了这一步，但最终结果非常简单，可能有一个简单的公式）。
主要问题在于问题要求a、b或c的上限为98,765,432。无论如何，从将问题分为简单和非简单两部分开始：
现在我们只需要展示没有其他解决方案是可行的，只有排列是有效的（然后打印它们的代码是简单的）。我们回到上限。实际上，该问题的上限为c ≤ 98,765,432。这是上限，因为它是具有8位数字（总共10个数字减去每个a和b的1）的最大数字。这个上限仅适用于c，因为由于指数增长，a和b的范围必须要低得多，我们可以计算出，在将b从2变化到上限的情况下：
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
['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)
这是一个与平台不兼容的解决方案。英特尔x86和x64 CPU有所谓的EFLAGS寄存器，在每次整数算术运算后由处理器填充。这里我将跳过详细描述。相关标志是“溢出”标志（掩码0x800）和“进位”标志（掩码0x1）。为了正确解释它们，应考虑操作数是有符号还是无符号类型。
以下是从C/C++中检查标志的实用方法。以下代码适用于Visual Studio 2005或更新版本（32位和64位），以及GNU C/C++ 64位。
#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);
}
query_intel_eflags(0x801)中获得一个返回值为0，即既没有进位标志也没有溢出标志。在main()提供的示例代码中，发生了溢出，并且两个标志都设置为1。这个检查不意味着任何进一步的计算，因此应该非常快速。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);
0xFF变为0xFFFFFFFF，0x80变为0x80000000，最后uint16_t变为uint64_t。
注意：这会捕获整数加法/减法溢出，我意识到你的问题涉及乘法。在这种情况下，除法可能是最好的方法。这通常是 calloc 实现确保参数不会溢出，因为它们相乘来获取最终大小的一种方式。
-ftrapv将导致在（有符号）整数溢出时生成一个SIGABRT信号。详见此处。 - nibotclz指令或__clz(unsigned)函数来确定数字的等级（其最高位在哪里）。由于我不确定这是否适用于x86或x64，因此我假设它不可用，并且说找到最高有效位将需要最多log(sizeof(int)*8)条指令。 - nonsensickle