#### [SOLVED] How do I detect unsigned integer multiply overflow?

I was writing a program in C++ to find all solutions of ab = 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 ab to check if the digits condition was satisfied.

However, spurious solutions can be generated when ab 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

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++.

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++.

#### @Pauli Nieminen 2015-11-18 19:29:54

The x86 instruction set includes an unsigned multiply instruction that stores the result to two registers. To use that instruction from C, one can write the following code in a 64-bit program (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;
}

For a 32-bit program, one needs to make the result 64 bit and parameters 32 bit.

An alternative is to use compiler-dependent intrinsic to check the flag register. GCC documentation for overflow intrinsic can be found from 6.56 Built-in Functions to Perform Arithmetic with Overflow Checking.

#### @chqrlie 2019-07-07 17:51:40

You should use the unsigned 128-bit type __uint128 to avoid signed overflow and right shifting a negative value.

#### @Peter Mortensen 2019-11-09 14:12:44

What are "compiler-dependent instincts" and "overflow instincts"? Do you mean "intrinsic functions"? Do you have a reference? (Please respond by editing your answer, not here in comments (as appropriate).)

#### @Tyler Durden 2015-01-21 21:28:11

To perform an unsigned multiplication without overflowing in a portable way the following can be used:

... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
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 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;
}

#### @bartolo-otrit 2014-01-10 17:15:46

Another variant of a solution, using assembly language, is an external procedure. This example for unsigned integer multiplication using g++ and fasm under Linux x64.

This procedure multiplies two unsigned integer arguments (32 bits) (according to specification for amd64 (section 3.2.3 Parameter Passing).

If the class is INTEGER, the next available register of the sequence %rdi, %rsi, %rdx, %rcx, %r8, and %r9 is used

(edi and esi registers in my code)) and returns the result or 0 if an overflow has occured.

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

Test:

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

Link the program with the asm object file. In my case, in Qt Creator, add it to LIBS in a .pro file.

#### @zneak 2014-01-06 18:28:39

Clang 3.4+ and GCC 5+ offer checked arithmetic builtins. They offer a very fast solution to this problem, especially when compared to bit-testing safety checks.

For the example in OP's question, it would work like this:

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
}

The Clang documentation doesn't specify whether c_test contains the overflowed result if an overflow occurred, but the GCC documentation says that it does. Given that these two like to be __builtin-compatible, it's probably safe to assume that this is how Clang works too.

There is a __builtin for each arithmetic operation that can overflow (addition, subtraction, multiplication), with signed and unsigned variants, for int sizes, long sizes, and long long sizes. The syntax for the name is __builtin_[us](operation)(l?l?)_overflow:

• u for unsigned or s for signed;
• operation is one of add, sub or mul;
• no l suffix means that the operands are ints; one l means long; two ls mean long long.

So for a checked signed long integer addition, it would be __builtin_saddl_overflow. The full list can be found on the Clang documentation page.

GCC 5+ and Clang 3.8+ additionally offer generic builtins that work without specifying the type of the values: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow. These also work on types smaller than int.

The builtins lower to what's best for the platform. On x86, they check the carry, overflow and sign flags.

Visual Studio's cl.exe doesn't have direct equivalents. For unsigned additions and subtractions, including <intrin.h> will allow you to use addcarry_uNN and subborrow_uNN (where NN is the number of bits, like addcarry_u8 or subborrow_u64). Their signature is a bit obtuse:

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 is the carry/borrow flag on input, and the return value is the carry/borrow on output. It does not appear to have equivalents for signed operations or multiplications.

Otherwise, Clang for Windows is now production-ready (good enough for Chrome), so that could be an option, too.

#### @Richard Cook 2015-11-03 17:18:22

__builtin_sub_overflow is definitely not in Clang 3.4.

#### @zneak 2016-03-26 02:34:58

@RichardCook, it took some time but Clang has the generic builtins as of version 3.9.

#### @zneak 2016-03-26 20:39:35

@tambre, I don't think there are.

#### @Lekensteyn 2016-04-18 19:17:50

According to the docs, __builtin_add_overflow and friends should already be available on Clang 3.8.

#### @Mudit Jain 2018-02-06 00:09:13

Thanks. This works great. Any idea what's the corresponding function for visual c++? Can't seem to find them.

#### @DrumM 2020-04-30 08:37:08

I think this answer should be selected as best answer and the C++ standard should introduce a generic way of doing this. @chris-johnson

#### @Spyros Panaoussis 2013-10-03 23:43:50

It depends what you use it for. Performing unsigned long (DWORD) addition or multiplication, the best solution is to use ULARGE_INTEGER.

ULARGE_INTEGER is a structure of two DWORDs. The full value can be accessed as "QuadPart" while the high DWORD is accessed as "HighPart" and the low DWORD is accessed as "LowPart".

For example:

DWORD
{
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;

// 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)

#### @Mysticial 2013-10-03 23:48:24

Unfortunately, this is a Windows-only solution. Other platforms do not have ULARGE_INTEGER.

#### @hdante 2013-03-11 01:57:31

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).

The main point is that the upper bound that the problem requires for either a, b or c is 98.765.432. Anyway, starting by splitting the problem in the trivial and non trivial parts:

• x0 == 1 (all permutations of 9, 8, 7, 6, 5, 4, 3, 2 are solutions)
• x1 == x (no solution possible)
• 0b == 0 (no solution possible)
• 1b == 1 (no solution possible)
• ab, a > 1, b > 1 (non trivial)

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

Notice, for example the last line: it says that 1.97^27 ~98M. So, for example, 1^27 == 1 and 2^27 == 134.217.728 and that's not a solution because it has 9 digits (2 > 1.97 so it's actually bigger than what should be tested). As it can be seen, the combinations available for testing a and b are really small. For b == 14, we need to try 2 and 3. For b == 3, we start at 2 and stop at 462. All the results are granted to be less than ~98M.

Now just test all the combinations above and look for the ones that do not repeat any digits:

['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)

None of them matches the problem (which can also be seen by the absence of '0', '1', ..., '9').

The example code that solves it follows. Also note that's written in Python, not because it needs arbitrary precision integers (the code doesn't calculate anything bigger than 98 million), but because we found out that the amount of tests is so small that we should use a high level language to make use of its built-in containers and libraries (also note: the code has 28 lines).

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)

#### @Tom Roggero 2018-03-13 19:46:34

why are you not using 9.876.543.210 as the upper limit?

#### @hdante 2018-03-17 01:27:12

Because 2 digits must be used for the left hand side of the equation.

#### @Paul Childs 2018-09-27 05:02:22

Not that it makes a difference, but the upper limit can actually be taken as 98765410 as you have stated the values on the LHS are > 1

#### @ZAB 2013-01-28 17:51:30

Clang now supports dynamic overflow checks for both signed and unsigned integers. See the -fsanitize=integer switch. For now, it is the only C++ compiler with fully supported dynamic overflow checking for debug purposes.

#### @Angel Sinigersky 2012-12-07 13:48:39

Here is a "non-portable" solution to the question. The Intel x86 and x64 CPUs have the so-called EFLAGS-register, which is filled in by the processor after each integer arithmetic operation. I will skip a detailed description here. The relevant flags are the "Overflow" Flag (mask 0x800) and the "Carry" Flag (mask 0x1). To interpret them correctly, one should consider if the operands are of signed or unsigned type.

Here is a practical way to check the flags from C/C++. The following code will work on Visual Studio 2005 or newer (both 32 and 64 bit), as well as on GNU C/C++ 64 bit.

#include <cstddef>
#if defined( _MSC_VER )
#include <intrin.h>
#endif

{
#if defined( _MSC_VER )

#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"
);

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

If the operands were multiplied without overflow, you would get a return value of 0 from query_intel_eflags(0x801), i.e. neither the carry nor the overflow flags are set. In the provided example code of main(), an overflow occurs and the both flags are set to 1. This check does not imply any further calculations, so it should be quite fast.

#### @Willem Hengeveld 2012-10-04 12:08:10

Another interesting tool is IOC: An Integer Overflow Checker for C/C++.

This is a patched Clang compiler, which adds checks to the code at compile time.

You get output looking like this:

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

#### @ZAB 2013-10-31 07:00:03

This patch is now merged to clang codebase among other sanitizers, see my answer.

#### @A Fog 2011-07-25 21:40:17

Warning: GCC can optimize away an overflow check when compiling with -O2. The option -Wall will give you a warning in some cases like

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

but not in this example:

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

The only safe way is to check for overflow before it occurs, as described in the CERT paper, and this would be incredibly tedious to use systematically.

Compiling with -fwrapv solves the problem, but disables some optimizations.

We desperately need a better solution. I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring. The present situation allows the compiler to optimize away an overflow check, which is unacceptable in my opinion.

#### @SamB 2012-02-02 03:39:01

Note that compilers may only do this with signed integer types; overflow is completely defined for the unsigned integer types. Still, yes, it's quite a dangerous trap!

#### @user253751 2016-01-16 11:01:28

"I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring." - so for(int k = 0; k < 5; k++) {...} should raise a warning?

#### @MikeMB 2016-05-03 05:49:00

@immibis: Why should it? The values of k can easily be determined at compile time. The compiler doesn't have to make any assumptions.

#### @user253751 2016-05-03 05:51:02

@MikeMB So for(int k = 0; k < 5; k++) {...} should raise a warning when optimizations are disabled (so the compiler hasn't gone to the effort to prove that k is bounded)?

#### @MikeMB 2016-05-03 06:09:56

@immibis: To quote the above: "I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring."

#### @user253751 2016-05-03 11:33:59

@MikeMB Oh, I confused that with "the compiler should issue a warning whenever overflow could occur".

#### @user253751 2016-05-03 11:35:31

@MikeMB So what you mean is: the compiler should issue a warning by default when making an optimization that relies on overflow not occurring unless it can prove that overflow won't occur. Then you end up with warnings for things like 1 << n.

#### @MikeMB 2016-05-03 23:12:41

@immibis: I'm not really in favor of those kinds of warnings in general, because a) I fear they would become quite noisy and b) would probably only produce a meaningful message in trivial cases. But I really don't see how your particular examples would produce a warning. What optimization would rely on a leftshift not overflowing? Actually, besides the classical example posted by A Fog, I know very few optimizations that are based on the assumption that integers won't overflow.

#### @user253751 2016-05-03 23:13:50

@MikeMB The optimization where the compiler doesn't bother to check that n is less than 32, before emitting a shift instruction that only uses the lower 5 bits of n?

#### @supercat 2019-12-16 04:44:22

@MikeMB: Most of the optimizations I'd regard as useful would effectively involve allowing integer operations to behave as though the upper bits were indeterminate, but gcc will sometimes generate nonsensical code when overflows occur even in cases where the upper bits would be totally ignored.

#### @DX-MON 2011-06-24 19:44:22

Here is a really fast way to detect overflow for at least additions, which might give a lead for multiplication, division and power-of.

The idea is that exactly because the processor will just let the value wrap back to zero and that C/C++ is to abstracted from any specific processor, you can:

uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);

This both ensures that if one operand is zero and one isn't, then overflow won't be falsely detected and is significantly faster than a lot of NOT/XOR/AND/test operations as previously suggested.

As pointed out, this approach, although better than other more elaborate ways, is still optimisable. The following is a revision of the original code containing the optimisation:

uint32_t x, y;
uint32_t value = x + y;
const bool overflow = value < x; // Alternatively "value < y" should also work

A more efficient and cheap way to detect multiplication overflow is:

uint32_t x, y;
const bool overflow = (x >> 16U) * (y >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;

This results in either UINT32_MAX on overflow, or the result of the multiplication. It is strictly undefined behaviour to allow the multiplication to proceed for signed integers in this case.

#### @DX-MON 2012-07-20 20:40:56

I disagree due to computation theory.. consider the following: y > x, value overflows, y is only bigger than x due to the sign bit being set (1 + 255, for example, for unsigned chars) testing value and x would result in overflow = false - hence the use of logical or to prevent this broken behaviour..

#### @Gunther Piez 2012-07-20 21:33:23

The test works for the numbers you give (x:=1, y:=255, size = uint8_t): value will be 0 (1+255) and 0<1 is true. It works indeed for every number pair.

#### @DX-MON 2012-07-22 00:39:37

Hmm, you make a good point. I still stick on the side of safety using the or trick though as any good compiler would optimise it out provider you are indeed correct for all inputs, including non-overflowing numbers such as "0 + 4" where the result would not be overflow.

#### @Gunther Piez 2012-07-22 01:21:10

If there is an overflow, than x+y>=256 and value=x+y-256. Because y<256 always holds true, (y-256) is negative and so value < x is always true. The proof for the non overflowing case is quite similar.

#### @DX-MON 2012-07-23 22:12:52

+1 - you make a valid point. I accept your argument for the simplification and will create an amendment to my original posting containing the amendment.

#### @Matt 2015-02-20 01:34:42

@DX-MON: Your first method is necessary if you also have a carry bit from a previous add. uint32_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]); } If you don't or the values, you will not be able to distinguish between one operand and the carry bit being zero and one operand being 0xffffffff and the carry bit being one.

#### @DX-MON 2015-05-22 16:29:06

You make a fine point, @Matt, for the summation/accumulation case. well caught.

#### @pmg 2009-10-03 17:15:16

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 :)

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:

#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 */;

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

#### @Chris Johnson 2009-10-03 18:47:20

Unsigned integers don't strictly overflow in C++ either (ISO/IEC 14882:2003 3.9.1.4). My use of 'overflow' in the question was the more colloquial meaning, intended to include the well-defined wrapping of unsigned types, since I was interested in unsigned ints representing mathematical positive integers, not positive integers mod 2^32 (or 2^64). The distinction between overflow as a deviation from mathematical infinite-sized integer behaviour, and overflow as an undefined behaviour in the language seems rarely to be made explicit.

#### @caf 2010-04-26 00:20:14

That test doesn't need to be x >= 0 - x > 0 will suffice (if x == 0, then x + a can't overflow for obvious reasons).

#### @Pacerier 2013-09-22 17:39:04

@pmg, is there a supporting quote from the standard?

#### @Franz D. 2016-11-16 16:31:34

I like this approach... However, be careful: the multiplication overflow detection assumes a posiive x. For x == 0, it leads to divide by zero detection, and for negative x, it always erroneously detects overflow.

#### @chux - Reinstate Monica 2017-01-11 19:11:40

if ((a < INT_MIN / x)) test is too late. A if (x == -1) test is needed first.

#### @Andrey Portnoy 2019-01-10 22:11:08

Who needs these complex rearrangements, just use if (a + x > INT_MAX) instead ;)

#### @pmg 2019-01-11 09:13:44

@AndreyPortnoy: a + x (a value of type int) cannot ever be greater than INT_MAX! Much as, in a 24-hour clock, hour1 + hour2 cannot ever be greater than 23 (eg: 18 + 10 overflows to 04)

#### @Andrey Portnoy 2019-01-11 18:19:52

@pmg I was kidding, note the ;) ;) But someone with a math background might have that instinct to simplify and rearrange.

#### @user1593842 2019-04-27 08:56:17

the top voted answer is an excellent answer to something that was not asked. pmg even acknowledged that. If unsigned integer overflow is something that may offend language lawyers (even though the intent is quite clear and I bet is a term incorrectly used by many), I think the best answer would have been "unsigned int does not overflow. Please ask a new question about how to detect if an operation would wrap around".

#### @dot_Sp0T 2019-10-15 20:05:45

@pmg it seems that the general case test for overflows of multiplication doesn't work properly. E.g. take the multiplication 15 * -6734, it will result in -101010 but the test will say it'll overflow

#### @pmg 2019-10-15 21:09:14

good catch @dot_Sp0t, I wrote those conditions erroneously assuming a and x have the same sign.

#### @anonymous 2009-02-09 14:06:39

For unsigned integers, just check that the result is smaller than one of the arguments:

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

For signed integers you can check the signs of the arguments and of the result.

Integers of different signs can't overflow, and integers of the same sign overflow only if the result is of a different sign:

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

#### @primfaktor 2012-12-13 09:55:58

Well the first method would also work for signed integers, wouldn't it? char result = (char)127 + (char)3; would be -126; smaller than both operands.

#### @primfaktor 2012-12-13 10:01:26

Oh I see, the problem is the fact that it's undefined for signed types.

#### @Voo 2012-12-16 19:48:24

-1 overflow of signed numbers results in undefined behavior (hence the test is too late to be actually useful).

#### @phuclv 2014-02-19 11:46:30

@primfaktor it doesn't work for signed int: char((-127) + (-17)) = 112. For signed int you must check the sign bit of the arguments and result

#### @davidbak 2015-05-28 18:29:19

Yes, and find this solution plus more (signed add/sub, unsigned add/sub, and multiplication, in the very excellent Hacker's Delight, 2nd ed., by Henry Warren, Jr.

#### @Marwan Burelle 2016-11-23 14:37:49

As already stated, the solution for signed integer doesn't work because of the undefined behavior of a + b in case of overflow. Checking for overflow with signed integer must be done before the operation.

#### @Frank Szczerba 2008-10-14 18:43:06

MSalter's answer is a good idea.

If the integer calculation is required (for precision), but floating point is available, you could do something like:

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

#### @Toby Speight 2017-01-20 09:07:16

Usually, I'd say that repeating the calculation in floating point is a bad idea, but for this specific case of exponentiation a^c, it may well be more efficient. But the test should be (c * log(a) < max_log), where const double max_log = log(UINT_MAX)

#### @Evan Teran 2008-10-14 01:05:15

If you have a datatype which is bigger than the one you want to test (say you do a 32-bit add and you have a 64-bit type), then this will detect if an overflow occurred. My example is for an 8-bit add. But it can be scaled up.

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

For a 32-bit example, 0xFF becomes 0xFFFFFFFF and 0x80 becomes 0x80000000 and finally uint16_t becomes a uint64_t.

NOTE: this catches integer addition/subtraction overflows, and I realized that your question involves multiplication. In which case, division is likely the best approach. This is commonly a way that calloc implementations make sure that the parameters don't overflow as they are multiplied to get the final size.

#### @Peter Mortensen 2019-11-09 13:01:15

The link is broken: HTTP 403: Forbidden

#### @Tarski 2008-10-13 23:25:45

You can't access the overflow flag from C/C++.

I don't agree with this. You could write some inline assembly language and use a jo (jump overflow) instruction assuming you are on x86 to trap the overflow. Of course, your code would no longer be portable to other architectures.

Look at info as and info gcc.

#### @Nils Pipenbrinck 2008-10-13 23:32:01

inline assembler is no C/C++ feature and platform independent. On x86 you can use the into instruction istead of branches btw.

#### @Brian R. Bondy 2008-10-13 23:07:19

A clean way to do it would be to override all operators (+ and * in particular) and check for an overflow before performing the operations.

Except that you can't override operators for builtin types. You'd need to write a class for that and rewrite client code to use it.

#### @Nils Pipenbrinck 2008-10-13 22:59:37

You can't access the overflow flag from C/C++.

Some compilers allow you to insert trap instructions into the code. On GCC the option is -ftrapv.

The only portable and compiler independent thing you can do is to check for overflows on your own. Just like you did in your example.

However, -ftrapv seems to do nothing on x86 using the latest GCC. I guess it's a leftover from an old version or specific to some other architecture. I had expected the compiler to insert an INTO opcode after each addition. Unfortunately it does not do this.

#### @Nate Kohl 2011-02-15 15:45:31

Maybe it varies: -ftrapv seems to work fine using GCC 4.3.4 on a Cygwin box. There's an example at stackoverflow.com/questions/5005379/…

#### @ZAB 2013-10-31 07:11:18

You both are right. -ftrapv do the job but only for signed integers

#### @hsivonen 2018-03-15 15:55:58

mozilla::CheckedInt<T> provides overflow-checked integer math for integer type T (using compiler intrinsics on clang and gcc as available). The code is under MPL 2.0 and depends on three (IntegerTypeTraits.h, Attributes.h and Compiler.h) other header-only non-standard library headers plus Mozilla-specific assertion machinery. You probably want to replace the assertion machinery if you import the code.

#### @Dustin 2010-05-01 19:01:54

The simple way to test for overflow is to do validation by checking whether the current value is less than the previous value. For example, suppose you had a loop to print the powers of 2:

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

Adding overflow checking the way that I described results in this:

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

It works for unsigned values as well as both positive and negative signed values.

Of course, if you wanted to do something similar for decreasing values instead of increasing values, you would flip the <= sign to make it >=, assuming the behaviour of underflow is the same as the behaviour of overflow. In all honesty, that's about as portable as you'll get without access to a CPU's overflow flag (and that would require inline assembly code, making your code non-portable across implementations anyway).

#### @David Stone 2017-05-13 15:44:28

If a signed value overflows, the behavior of your program is undefined. It is not guaranteed to wrap around.

#### @Scott Franco 2014-06-20 19:22:43

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

}
}

Catching Integer Overflows in C points out a solution more general than the one discussed by CERT (it is more general in term of handled types), even if it requires some GCC extensions (I don't know how widely supported they are).

#### @Markus Demarmels 2013-08-05 15:47:25

Try this macro to test the overflow bit of 32-bit machines (adapted the solution of Angel Sinigersky)

#define overflowflag(isOverflow){   \
size_t eflags;                      \
asm ("pushfl ;"                     \
"pop %%eax"                    \
: "=a" (eflags));               \
isOverflow = (eflags >> 11) & 1;}

I defined it as a macro because otherwise the overflow bit would have been overwritten.

Subsequent is a little application with the code segement above:

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

#### @Ben Voigt 2015-01-22 18:10:40

Not all 32-bit machines are Intel x86-compatible, and not all compilers support gnu assembly syntax (I find it funny that you post code which tests _MSC_VER although MS compiles will all reject the code).

#### @Steztric 2013-02-13 17:34:18

bool addition_is_safe(unsigned int a, unsigned int b)
{
unsigned int L_Mask = std::numeric_limits<unsigned int>::max();

return ( a == 0 || b == 0 );
}

This uses machine-architecture safe, in that 64-bit and 32-bit unsigned integers will still work fine. Basically, I create a mask that will mask out all but the most significant bit. Then, I mask both integers, and if either of them do not have that bit set, then addition is safe.

This would be even faster if you pre-initialize the mask in some constructor, since it never changes.

#### @the swine 2014-04-08 15:04:47

This is not correct. Carry might bring bits from lower positions that will cause overflow. Consider adding UINT_MAX + 1. After masking, a will have the high bit set, but 1 will become zero and therefore the function will return true, addition is safe - yet you are headed directly for overflow.

#### @Paul Chernoch 2012-05-21 14:53:50

I needed to answer this same question for floating point numbers, where bit masking and shifting does not look promising. The approach I settled on works for signed and unsigned, integer and floating point numbers. It works even if there is no larger data type to promote to for intermediate calculations. It is not the most efficient for all of these types, but because it does work for all of them, it is worth using.

Signed Overflow test, Addition and Subtraction:

1. Obtain the constants that represent the largest and smallest possible values for the type, MAXVALUE and MINVALUE.

2. Compute and compare the signs of the operands.

a. If either value is zero, then neither addition nor subtraction can overflow. Skip remaining tests.

b. If the signs are opposite, then addition cannot overflow. Skip remaining tests.

c. If the signs are the same, then subtraction cannot overflow. Skip remaining tests.

3. Test for positive overflow of MAXVALUE.

a. If both signs are positive and MAXVALUE - A < B, then addition will overflow.

b. If the sign of B is negative and MAXVALUE - A < -B, then subtraction will overflow.

4. Test for negative overflow of MINVALUE.

a. If both signs are negative and MINVALUE - A > B, then addition will overflow.

b. If the sign of A is negative and MINVALUE - A > B, then subtraction will overflow.

5. Otherwise, no overflow.

Signed Overflow test, Multiplication and Division:

1. Obtain the constants that represent the largest and smallest possible values for the type, MAXVALUE and MINVALUE.

2. Compute and compare the magnitudes (absolute values) of the operands to one. (Below, assume A and B are these magnitudes, not the signed originals.)

a. If either value is zero, multiplication cannot overflow, and division will yield zero or an infinity.

b. If either value is one, multiplication and division cannot overflow.

c. If the magnitude of one operand is below one and of the other is greater than one, multiplication cannot overflow.

d. If the magnitudes are both less than one, division cannot overflow.

3. Test for positive overflow of MAXVALUE.

a. If both operands are greater than one and MAXVALUE / A < B, then multiplication will overflow.

b. If B is less than one and MAXVALUE * B < A, then division will overflow.

4. Otherwise, no overflow.

Note: Minimum overflow of MINVALUE is handled by 3, because we took absolute values. However, if ABS(MINVALUE) > MAXVALUE, then we will have some rare false positives.

The tests for underflow are similar, but involve EPSILON (the smallest positive number greater than zero).

#### @Chris Johnson 2012-05-24 22:04:55

On POSIX systems at least, the SIGFPE signal can be be enabled for floating point under/overflows.

#### @JanKanis 2014-03-11 01:43:44

While converting to floating point and back works, it is (according to my testing on a 32bit machine) much slower than the other solutions.

#### @Paul Chernoch 2015-11-04 13:58:09

A reviewer detected a missing case for subtraction part 2. I agree that 0 - MINVALUE would overflow. So testing for this case should be added.

#### @Arne Vogel 2018-06-13 15:42:57

<pedantic>Integers do not underflow (= become too close to zero to be represented with any accuracy). 1.0e-200 / 1.0e200 would be an example of an actual underflow, assuming IEEE doubles. The correct term here, instead, is negative overflow.</pedantic>

#### @Arne Vogel 2018-06-13 15:46:36

To be precise, the reason why integers are not considered to underflow is because of defined truncation behavior, e.g. 1/INT_MAX could well be considered underflow, but the language simply mandates truncation to zero.

#### @MSalters 2008-10-14 07:30:00

Calculate the results with doubles. They have 15 significant digits. Your requirement has a hard upper bound on c of 108 — it can have at most 8 digits. Hence, the result will be precise if it's in range, and it will not overflow otherwise.

#### @Robert C. Seacord 2009-10-03 16:46:47

CERT has developed a new approach to detecting and reporting signed integer overflow, unsigned integer wrapping, and integer truncation using the "as-if" infinitely ranged (AIR) integer model. CERT has published a technical report describing the model and produced a working prototype based on GCC 4.4.0 and GCC 4.5.0.

The AIR integer model either produces a value equivalent to one that would have been obtained using infinitely ranged integers or results in a runtime constraint violation. Unlike previous integer models, AIR integers do not require precise traps, and consequently do not break or inhibit most existing optimizations.

#### @supercat 2019-03-05 16:38:12

I didn't see anything useful at the link, but that sounds like a model I've long advocated. It supports the vast majority of useful optimizations, while also supporting useful semantic guarantees that most implementations can provide at essentially no charge. If code knows that the inputs to a function will be valid in all cases where the output matters, but doesn't know in advance whether the output will matter, being able to let overflows happen in cases where they won't affect anything may be easier and more efficient than having to prevent them at all costs.

#### @Andrew Edgecombe 2008-10-13 22:59:20

The simplest way is to convert your unsigned longs into unsigned long longs, do your multiplication, and compare the result to 0x100000000LL.

You'll probably find that this is more efficient than doing the division as you've done in your example.

Oh, and it'll work in both C and C++ (as you've tagged the question with both).

Just been taking a look at the glibc manual. There's a mention of an integer overflow trap (FPE_INTOVF_TRAP) as part of SIGFPE. That would be ideal, apart from the nasty bits in the manual:

FPE_INTOVF_TRAP Integer overflow (impossible in a C program unless you enable overflow trapping in a hardware-specific fashion).

A bit of a shame really.

#### @Chris Johnson 2008-10-13 23:59:22

Heh... what I didn't say was that I'm asking this question in preparation for writing a program to solve a problem with larger numbers, in which I'm already using long long int. Since long long int is not (allegedly) in the C++ standard, I stuck with the 32-bit version to avoid confusion.

#### @jw013 2013-01-16 20:39:04

I'd advise using ULONG_MAX which is easier to type and more portable than hard-coding 0x100000000.

#### @interjay 2013-04-10 08:48:46

This doesn't work when long and long long are the same size (e.g. on many 64-bit compilers).

#### @SamB 2014-12-31 06:54:58

Relying on signals to tell you about overflows would be really slow anyway.

#### @user253751 2016-01-16 11:02:33

@SamB Only if overflows were expected to be frequent.

There is a way to determine whether an operation is likely to overflow, using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge.

For addition, any two operands will result in (at most) one bit more than the largest operand's highest one-bit. For example:

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

For multiplication, any two operands will result in (at most) the sum of the bits of the operands. For example:

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

Similarly, you can estimate the maximum size of the result of a to the power of b like this:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a);
return (a_bits*b<=32);
}

(Substitute the number of bits for your target integer, of course.)

I'm not sure of the fastest way to determine the position of the highest one-bit in a number, here's a brute-force method:

size_t highestOneBitPosition(uint32_t a) {
size_t bits=0;
while (a!=0) {
++bits;
a>>=1;
};
return bits;
}

It's not perfect, but that'll give you a good idea whether any two numbers could overflow before you do the operation. I don't know whether it would be faster than simply checking the result the way you suggested, because of the loop in the highestOneBitPosition function, but it might (especially if you knew how many bits were in the operands beforehand).

#### @Oliver Hallam 2010-01-25 18:14:30

and of course you could rename highestOneBitPosition to log :)

Yes, it's the same operation as log2, but that wouldn't necessarily be as obvious to someone who didn't have a mathematical background.

#### @clahey 2010-04-15 17:51:56

Doesn't this algorithm underestimate the safe answers? 2^31 + 0 would detect as unsafe since highestOneBitPosition(2^31) = 32. (2^32 - 1) * 1 would detect as unsafe since 32 + 1 > 32. 1 ^ 100 would detect as unsafe since 1 * 100 > 32.

Not quite sure where you're coming from. Those functions are meant to determine whether a mathematical operation is safe from overflowing. Unless the code explicitly checks for a zero or one multiplicand, (2^32 - 1) * 1 can't be determined as safe without doing the entire operation.

#### @jww 2011-06-19 05:54:59

"highestOneBitPosition" - count leading zeros? publib.boulder.ibm.com/infocenter/aix/v6r1/index.jsp?topic=/‌​…

#### @Michi 2013-08-09 09:46:57

according to your multiplication_is_safe 0x8000 * 0x10000 would overflow (bit positions are 16 + 17 = 33 which is > 32), although it doesn't because 0x8000 * 0x10000 = 0x80000000 which obviously still fits into a unsigned 32 bit int. This is just one out of may examples for which this codes does not work. 0x8000 * 0x10001, ...

@GT_mh: Your point? As I said, it's not perfect; it's a rule-of-thumb that will definitively say when something is safe, but there's no way to determine whether every calculation would be okay without doing the full calculation. 0x8000 * 0x10000 isn't "safe," by this definition, even though it turns out to be okay.

#### @Pacerier 2013-09-22 17:38:14

@HeadGeek, as for detecting overflow for addition a + b, why not simply use if(b > max - a)?

#### @nonsensickle 2013-10-03 23:54:56

To find out the position of the most significant bit you can use the clz instruction in ARM (infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui049‌​1c/…). I'm not sure about x86 or x64 but I suspect the most efficient way is to do some form of a binary search with shift operators.

#### @nonsensickle 2013-10-04 00:02:36

However, for multiplication the solution he has given is already optimal. Multiplication and division are single instruction operations where finding the number of leading zeroes (the position of the highest bit) are not necessarily (excluding the ARM example I gave earlier).

@Pacerier: That should work too, I believe. There's also an even more efficient way to do it (for addition only) by using bit-manipulation operators to test the high-bit. I only included the addition part to show how addition fits into the theory I was trying to explain.

#### @Gareth Rees 2013-12-11 23:17:20

The multiplication a_bits*b in exponentiation_is_safe might overflow, so you need to test multiplication_is_safe(a_bits, b) first.

#### @mr5 2014-01-08 09:39:33

How about subtraction_is_safe()? I came up with that problem but I dunno how to implement it myself, would you...Thanks :D

With unsigned integers, that's extremely simple -- just make sure the first one is larger than the second. With signed integers it's a little more complex, you have to check the signs too, but not too much. If I have time, I'll edit the answer above to include that, but it won't be today.

#### @Brett Hale 2015-01-17 08:47:14

This is pretty much useless. When it returns 'safe' - it is. Otherwise, it's still necessary to perform the full multiplication just to be sure it really is safe. Given the potentially huge range of values that report false negatives, this has no real value, when algorithms exist to return the correct answer, without a validation step.

#### @Brett Hale 2015-01-17 08:58:35

The use of 'significant bits' is not robust either. If a has m significant bits, and b has n significant bits, the product has m + n or m + n - 1 significant bits. A basic property of bit-wise multiplication. In short, this is all a lot of work for an indeterminate result. The msb calculations are just more overhead.

Knowing whether a calculation is definitely safe is often all you need.

#### @Tyler Durden 2015-01-21 21:08:03

Agreeing with Brett Hale, the posted method for unsigned multiplication here is just wrong.

#### @Alec Teal 2015-05-21 15:42:11

There is a lot wrong with this answer, while yes, would overflow implies these will return true, there's a lot of false positives. A poor answer.

It does have false positives, but it's also simple and doesn't require convoluted and expensive partial calculations. It makes a good and cheap first-pass algorithm, which in many cases is sufficient.

#### @dvicino 2015-08-28 15:35:43

You can obtain highestOneBitPosition just calling the C function lsf()

#### @RichardBruce 2016-03-23 01:15:25

You perhaps want to use a CLZ (count leading zero) instruction to help find the highest 1 quickly. Most modern architectures will provide this

#### @Navin 2016-05-21 07:08:02

-1, Too many false positives to be of any use. Unless this is consistently faster than the correct answer, I don't see the point.

#### @dimm 2017-02-26 22:30:43

This seems slow. For unsigned generally you can do the operation and then you can check for overflow.

#### @Pastafarianist 2018-06-18 18:47:23

highestOneBitPosition can be implemented in GCC as 32 - __builtin_clz(a) for uint32_t and 64 - __builtin_clzl(a) for uint64_t.

#### @supercat 2018-10-17 16:06:17

With addition or subtraction, using a modular-arithmetic type (e.g. an unsigned type in C) and checking wraparound is usually easier than trying to predict overflow. For multiplication, overflow will always occur if both values exceeds the square root of the maximum product, and never occur if neither value does. If one value does (64-bit unsigned types used for illustration), compute (big>>32)*small and (big & 0xFFFFFFFF)*small. Neither multiplication will overflow. If the first product fits in 32 bits, shift it left 32, add the second, and check for wrap-around.

#### @Robert Gamble 2008-10-13 23:02:46

Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn't standard.

You could also test for the possibility of overflow before you perform the multiplication:

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

#### @Jonas Gulle 2008-10-13 23:15:47

...or use numeric_limits<TYPE>::max()

#### @Thelema 2009-07-03 14:24:38

Don't forget to handle a=0 -- division breaks then.

#### @jww 2011-06-19 05:56:44

@Thelema: "Don't forget to handle a=0" - and INT_MIN / -1.

#### @the swine 2014-04-08 15:17:08

What if b == ULONG_MAX / a? Then it can still fit, given that a divides ULONG_MAX without residual.

#### @DrumM 2020-04-30 08:39:54

Funny that, performance wise, a multiplication is rather fast compared to a division and you're adding a division for every multiplication. This doesn't sound like the solution.

### [SOLVED] How do I iterate over the words of a string?

• 2008-10-25 08:58:21
• Ashwin Nanjappa
• 2177442 View
• 2984 Score
• Tags:   c++ string split

### [SOLVED] Is using unsigned integer overflow good practice?

• 2009-06-12 19:29:23
• user122147
• 7386 View
• 19 Score