如何检测无符号整数溢出？

我在C++写了一个程序来寻找一个b=c的所有解，其中一个、b和c一起使用所有数字0-9恰好一次。该程序循环一个和b的值，并在一个、b和b0上每次运行一个数字计数例程来检查数字条件是否满足。

但是，当一个b溢出整数限制时，可能会生成虚假解决方案。我最终使用以下代码检查了这一点：

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++访问。

注意EYZ0溢出是C和C++中未定义的行为，因此您必须在不实际导致它的情况下检测它。关于添加之前的签名int溢出，请参阅检测C/C++中的有符号溢出。

413614 次浏览
小开

内联汇编允许您直接检查溢出位。如果您要使用C++，您真的应该学习汇编。

小开

最简单的方法是将unsigned long转换为unsigned long long，进行乘法运算，并将结果与0x100000000LL进行比较。

您可能会发现这比您在示例中所做的除法更有效。

哦，它可以在C和C++中工作（因为你已经用两者标记了这个问题）。

刚刚看了一下glibc手册。有提到一个整数溢出陷阱（FPE_INTOVF_TRAP）作为SIGFPE的一部分。这将是理想的，除了手册中令人讨厌的部分：

FPE_INTOVF_TRAP 整数溢出（在C程序中不可能，除非您以特定于硬件的方式启用溢出捕获）。

真的有点可惜。

小开

无法从C/C++访问溢出标志。

一些编译器允许您在代码中插入陷阱指令。在GCC上，选项是-ftrapv。

您可以做的唯一可移植且独立于编译器的事情是自己检查溢出。就像您在示例中所做的那样。

然而，-ftrapv似乎在使用最新GCC的x86上什么也没做。我猜它是旧版本的残留物或特定于其他架构。我曾期望编译器在每次添加后插入INTO操作码。不幸的是它没有这样做。

小开

一些编译器提供对CPU中整数溢出标志的访问，然后您可以对其进行测试，但这不是标准的。

您还可以在执行乘法之前测试溢出的可能性：

if ( b > ULONG_MAX / a ) // a * b would overflow
小开

一种简单的方法是覆盖所有运算符（特别是+和*）并在执行操作之前检查溢出。

小开

无法从C/C++访问溢出标志。

我不同意这一点。假设您在x86上，您可以编写一些内联汇编语言并使用jo（跳转溢出）指令来捕获溢出。当然，您的代码将不再可移植到其他架构。

看看info as和info gcc。

小开

有是一种方法可以确定操作是否可能溢出，使用操作数中最有效的一位的位置和一些基本的二进制数学知识。

此外，任何两个操作数将导致（最多）比最大操作数的最高一位多一位。例如：

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函数中有循环，但它可能会（特别是如果您事先知道操作数中有多少位）。

小开

如果您的数据类型大于要测试的数据类型（假设您执行32位添加并且您有64位类型），那么这将检测是否发生溢出。我的示例是8位添加。但它可以按比例放大。

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

对于32位示例，0xFF变为0xFFFFFFFF，0x80变为0x80000000，最后uint16_t变为uint64_t。

注：这会捕获整数加减溢出，我意识到你的问题涉及乘法。在这种情况下，除法可能是最好的方法。这通常是calloc实现确保参数在乘以获得最终大小时不会溢出的一种方式。

小开

用双精度计算结果。它们有15位有效数字。您的要求在108的c上有一个硬上限-最多可以有8位数字。因此，如果结果在范围内，结果将是精确的，否则不会溢出。

小开

MSalter的回答是个好主意。

如果需要整数计算（为了精度），但浮点数可用，您可以执行以下操作：

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
}
}
小开

对于无符号整数，只需检查结果是否小于其中一个参数：

unsigned int r, a, b;
r = a + b;
if (r < a)
{
// Overflow
}

对于有符号整数，您可以检查参数和结果的符号。

不同符号的整数不能溢出，只有当结果是不同符号时，相同符号的整数才会溢出：

signed int r, a, b, s;
r = a + b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
// Overflow
}
小开

CERT开发了一种使用“好像”无限范围（AIR）整数模型检测和报告有符号整数溢出、无符号整数包装和整数截断的新方法。CERT发布了一个描述该模型的技术报告，并制作了一个基于GCC 4.4.0和GCC 4.5.0的工作原型。

AIR整数模型要么生成与使用无限范围整数获得的值等效的值，要么导致违反运行时约束。与以前的整数模型不同，AIR整数不需要精确的陷阱，因此不会破坏或抑制大多数现有的优化。

小开

我看到你使用的是无符号整数。根据定义，在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。

小开

在C中捕获整数溢出指出了一个比CERT讨论的更通用的解决方案（就处理类型而言，它更通用），即使它需要一些GCC扩展（我不知道它们的支持有多广泛）。

小开

测试溢出的简单方法是通过检查当前值是否小于之前的值来进行验证。例如，假设您有一个循环来打印2的幂：

long lng;
int n;
for (n = 0; n < 34; ++n)
{
lng = pow (2, n);
printf ("%li\n", lng);
}

按照我描述的方式添加溢出检查结果如下：

long signed lng, lng_prev = 0;
int n;
for (n = 0; n < 34; ++n)
{
lng = pow (2, n);
if (lng <= lng_prev)
{
printf ("Overflow: %i\n", n);
/* Do whatever you do in the event of overflow.  */
}
printf ("%li\n", lng);
lng_prev = lng;
}

它适用于无符号值以及正、负符号值。

当然，如果你想对递减值而不是递增值做类似的操作，你可以翻转<=符号使其成为>=，假设下限溢位的行为与溢出的行为相同。老实说，这与你在不访问CPU溢出标志的情况下获得的可移植性差不多（这需要内联汇编代码，无论如何都会使你的代码在实现之间不可移植）。

小开

这是一种非常快速的方法来检测至少加法的溢出，这可能会导致乘法、除法和幂。

这个想法是，正是因为处理器会让值返回零，并且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};
小开

警告：使用-O2编译时，GCC可以优化溢出检查。 选项-Wall在某些情况下会给你一个警告，比如

if (a + b < a) { /* Deal with overflow */ }

但不是在这个例子中：

b = abs(a);
if (b < 0) { /* Deal with overflow */ }

唯一安全的方法是在溢出发生之前检查它，如CERT论文中所述，这将是非常乏味的系统使用。

使用-fwrapv编译可以解决问题，但会禁用一些优化。

我们迫切需要一个更好的解决方案。我认为编译器在进行依赖于不发生溢出的优化时默认应该发出警告。目前的情况允许编译器优化掉溢出检查，这在我看来是不可接受的。

小开

对于浮点数，我需要回答同样的问题，其中位掩码和移位看起来不太有希望。我确定的方法适用于有符号和无符号、整数和浮点数。即使没有更大的数据类型可以推广到中间计算，它也有效。它不是所有这些类型的最有效方法，但因为它确实适用于所有这些类型，所以值得使用。

签名溢出测试，加法和减法：

  1. 获取表示类型的最大和最小可能值的常量， 最大值和最小值。

  2. 计算并比较操作数的符号。

    如果任一值为零，则加法和减法都不能溢出。跳过剩余的测试。

    如果符号相反，则加法不能溢出。跳过剩余的测试。

    c.如果符号相同，则减法不能溢出。跳过剩余的测试。

  3. 测试MAXVALUE的正溢出。

    a.如果两个符号都是正数并且MAXVALUE-A

    b.如果B的符号为负数并且MAXVALUE-A<-B，则减法将溢出。

  4. 测试MINVALUE的负溢出。

    a.如果两个符号都是负数并且MINVALUE-A>B，则加法将溢出。

    b.如果A的符号为负并且MINVALUE-A>B，则减法将溢出。

  5. 否则，没有溢出。

签名溢出测试、乘法和除法：

  1. 获取表示类型的最大和最小可能值的常量， 最大值和最小值。

  2. 计算并比较操作数的大小（绝对值）为1。（下面，假设A和B是这些大小，而不是有符号的原始值。）

    a.如果任一值为零，则乘法不能溢出，除法将产生零或无穷大。

    湾。如果任一值为一，乘除不能溢出。

    如果一个操作数的大小低于1，而另一个操作数的大小大于1，则乘法不能溢出。

    d.如果两个量值都小于1，除法不能溢出。

  3. 测试MAXVALUE的正溢出。

    a.如果两个操作数都大于1且MAXVALUE/A

    b.如果B小于1并且MAXVALUE*B

  4. 否则，没有溢出。

注意：MINVALUE的最小溢出由3处理，因为我们采用绝对值。但是，如果 ABS（MINVALUE）>MAXVALUE，那么我们将有一些罕见的误报。

下限溢位的测试类似，但涉及EPSILON（大于零的最小正数）。

小开

另一个有趣的工具是IOC： C/C++的整数溢出检查器。

这是一个打补丁的Clang编译器，它在编译时向代码添加检查。

输出看起来像这样：

CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1
小开

这是该问题的“不可移植”解决方案。Intel 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。此检查不意味着任何进一步的计算，因此应该相当快。

小开

Clang现在支持对有符号和无符号整数进行动态溢出检查。请参阅-fsanitize=整数开关。目前，它是唯一完全支持用于调试目的的动态溢出检查的C++编译器。

小开

为了扩展Head Geek的答案，有一种更快的方法来执行addition_is_safe；

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 );
}

这使用了机器架构安全，因为64位和32位无符号整数仍然可以正常工作。基本上，我创建了一个掩码，它将掩码除最有效位之外的所有整数。然后，我掩码两个整数，如果它们中的任何一个没有设置该位，那么加法是安全的。

如果您在某个构造函数中预初始化掩码，这将更快，因为它永远不会改变。

小开

我看到很多人回答了关于溢出的问题，但我想解决他最初的问题。他说问题是找到一个b=c，使得所有数字都被使用而不重复。好吧，这不是他在这篇文章中问的，但我仍然认为有必要研究问题的上限，并得出结论，他永远不需要计算或检测溢出（注意：我不精通数学，所以我一步一步地做了这个，但最终结果很简单，这可能有一个简单的公式）。

要点是问题对a、b或c所需的上界是98.765.432。无论如何，从将问题分解为平凡和非平凡部分开始：

  • x==1（9,8,7,6,5,4,3,2的所有排列都是解）
  • x1==x（无解）
  • 0b==0（没有可能的解决方案）
  • 1b==1（无解）
  • ab， a>1， b>1（非平凡）

现在我们只需要证明没有其他解是可能的，只有排列是有效的（然后打印它们的代码是微不足道的）。我们回到上界。实际上，上界是c≤98.765.432。这是上界，因为它是最大的8位数字（a和b总共10位减去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

注意，例如最后一行：它说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)
小开

试试这个宏来测试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);
}
小开

这取决于你用它做什么。 执行无符号长（DWORD）加法或乘法，最好的解决方案是使用ULARGE_INTEGER。

ULARGE_INTEGER是两个DWORD的结构 在访问高DWORD时可以作为“QuadPart”访问 作为“HighPart”，低DWORD作为“LowPart”访问。

例如：

DWORD
My Addition(DWORD Value_A, DWORD Value_B)
{
ULARGE_INTEGER a, b;


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)


// Any overflow is stored in a.HighPart (up to 32 bits)
小开

从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来说已经足够好了），所以这也是一个选择。

小开

使用汇编语言的解决方案的另一个变体是外部过程。此示例用于在x64Linux下使用g++和fasm进行无符号整数乘法。

此过程将两个无符号整数参数（32位）相乘（根据产品规格 for amd64（第3.2.3参数传递节）。

如果类是INTEGER，则使用序列%rdi、%rsi、%rdx、%rcx、%r8和%r9的下一个可用寄存器

（edi和esi在我的代码中注册））并返回结果，如果发生溢出，则返回0。

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;
}

将程序与asm对象文件链接。在我的情况下，在qt创建者中，将其添加到. pro文件中的LIBS中。

小开 
#include <stdio.h>
#include <stdlib.h>


#define MAX 100


int mltovf(int a, int b)
{
if (a && b) return abs(a) > MAX/abs(b);
else return 0;
}


main()
{
int a, b;


for (a = 0; a <= MAX; a++)
for (b = 0; b < MAX; b++) {


if (mltovf(a, b) != (a*b > MAX))
printf("Bad calculation: a: %d b: %d\n", a, b);


}
}
小开

要以可移植的方式执行无符号乘法而不溢出，可以使用以下方法：

... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
zeroesMultiplicand = number_of_leading_zeroes( multiplicand );
zeroesMultiplier   = number_of_leading_zeroes( multiplier );
if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow;
productHalf = multiplicand * ( c >> 1 );
if( (int)productHalf < 0 ) goto overflow;
product = productHalf * 2;
if( multiplier & 1 ){
product += multiplicand;
if( product < multiplicand ) goto overflow;
}
..../* continue code here where "product" is the correct product */
....
overflow: /* put overflow handling code here */


int number_of_leading_zeroes( unsigned value ){
int ctZeroes;
if( value == 0 ) return 32;
ctZeroes = 1;
if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; }
if( ( value >> 24 ) == 0 ){ ctZeroes +=  8; value = value <<  8; }
if( ( value >> 28 ) == 0 ){ ctZeroes +=  4; value = value <<  4; }
if( ( value >> 30 ) == 0 ){ ctZeroes +=  2; value = value <<  2; }
ctZeroes -= x >> 31;
return ctZeroes;
}
小开

x86指令集包括一个无符号乘法指令，该指令将结果存储到两个寄存器。要使用C中的该指令，可以在64位程序（GCC）中编写以下代码：

unsigned long checked_imul(unsigned long a, unsigned long b) {
unsigned __int128 res = (unsigned __int128)a * b;
if ((unsigned long)(res >> 64))
printf("overflow in integer multiply");
return (unsigned long)res;
}

对于32位程序，需要将结果设置为64位，参数设置为32位。

另一种方法是使用编译器相关的内部检查标志寄存器。可以从6.56用于执行带有溢出检查的算术的内置函数中找到溢出内部的GCC留档。

小开

mozilla::CheckedInt<T>为整数类型T（在clang和gcc上使用编译器内部函数）提供了溢出检查的整数数学。该代码在MPL 2.0下，依赖于三个（IntegerTypeTraits.h、Attributes.h和Compiler.h）其他仅标头的非标准库标头以及Mozilla特定的断言机械。如果导入代码，您可能希望替换断言机制。


提交答案