How do I detect unsigned integer overflow?

Question

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

However, spurious solutions can be generated when a^b 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++.

Archeozoic

Information which may be useful on this subject: Chapter 5 of "Secure Coding in C and C++" by Seacord - http://www.informit.com/content/images/0321335724/samplechapter/seacord_ch05.pdf SafeInt classes for C++ - http://blogs.msdn.com/david_leblanc/archive/2008/09/30/safeint-3-on-codeplex.aspx - http://www.codeplex.com/SafeInt IntSafe library for C: - [blogs.msdn.com/michael_howard/archiv – Nikos

Seacord's Secure Coding is a great resource, but don't use IntegerLib. See blog.regehr.org/archives/593. – Oxbridge

The gcc compiler option -ftrapv will cause it to generate a SIGABRT on (signed) integer overflow. See here. – Davidoff

It does not answer the overflow question, but another way to come at the problem would be to use a BigNum library like GMP to guarantee you always have enough precision. You will not have to worry about overflow if you allocate enough digits up front. – Haas

The information given by @HeadGeek in his answer is pretty much what I would say as well. However, with one addition. The way you are detecting overflown for a multiplication now is probably the fastest. On ARM as I've commented in HeadGeek's answer you can use the clz instruction or the __clz(unsigned) function to determine the rank of the number (where its highest bit is). Since I'm unsure if this is available on x86 or x64 I will assume it is not and say that finding the most significant bit will take at worst log(sizeof(int)*8) instructions. – Unswerving

And your code currently does it in approximately 3 to 4 instructions. – Unswerving

There's a way to statically detect integer overflow (with False Positives): usenix.org/conference/osdi12/technical-sessions/presentation/… – Addia

Answer 1

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:

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

---

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

Prokopyevsk

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. – Archeozoic

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

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

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. – Squarely

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

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

@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) – Prokopyevsk

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

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". – Sabah

@Prokopyevsk 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 – Poseidon

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

Unsigned integers does overflow and underflow, when you do (unsigned int)-1 you get UINT_MAX, same for UINT_MAX + 1, you get 0 – Falsify

if (a > INT_MAX / x) is true say for x=3 and a=2 .... no overflow here though;] – Grover

Answer 2

Starting with C23, the standard header <stdckdint.h> provides the following three function-like macros:

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

where type1, type2 and type3 are any integer type. These functions respectively add, subtract or multiply a and b with arbitrary precision and store the result in *result. If the result cannot be represented exactly by type1, the function returns true ("calculation has overflowed"). (Arbitrary precision is an illusion; the calculations are very fast and almost all hardware available since the early 1990s can do it in just one or two instructions.)

Rewriting OP's example:

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 contains the potentially-overflowed result of the multiplication in all cases.

Long before C23, GCC 5+ and Clang 3.8+ offer built-ins that work the same way, except that the result pointer is passed last instead of first: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow. These also work on types smaller than 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+ introduced arithmetic-overflow builtins with fixed types, but they are much less flexible and Clang 3.8 has been available for a long time now. Look for __builtin_umull_overflow if you need to use this despite the more convenient newer alternative.

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.

Freshen

__builtin_sub_overflow is definitely not in Clang 3.4. – Moten

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

@tambre, I don't think there are. – Freshen

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

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

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

Great info! Note that dividing a signed integer can also overflow (specifically INT_MIN / -1, since abs(INT_MIN) == INT_MAX + 1 with the usual two's complement representation), but there don't seem to be corresponding builtin functions. – Blaubok

This is by far the best answer and should be the accepted one IMO. – Lightship

@MuditJain With basic pattern recognition of Microsoft's adoption of updated C standards, we can expect C23 features to be in Visual Studio by 2037. – Deeprooted

C23? Which compilers currently support that? – Skimp

Answer 3

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

Reliquary

and of course you could rename highestOneBitPosition to log :) – Forzando

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. – Reliquary

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. – Coinsurance

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. – Reliquary

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

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, ... – Antilog

@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. – Reliquary

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

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.dui0491c/…). 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. – Unswerving

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

@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. – Reliquary

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

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

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. – Reliquary

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. – Sidoon

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. – Sidoon

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

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

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. – Homoio

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. – Reliquary

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

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

-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. – Chadchadabe

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

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

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. – Stylobate

Use binary search instead of top-down loop in the pure C implementation: something like size_t highestOneBitPosition(T a) { size_t shift = (sizeof(T) * CHAR_BIT) / 2, position = 0; while (a) { if(a >> shift) { a >>= shift; position += shift; } shift /= 2; } return position; }, sorry for the format, untested, I just improvised this in the comment box. Instead of O(n) it's O(log(n)) which is great. Small downside: you pay one more branch and a couple more instructions per loop, and for a random input value those branches are less consistent and so is maybe less branch-predictor friendly. – Overstretch

A lot of the critique of this answer is needlessly condemning, as if we can't just trivially refine this answer's solution's concept. If highest_bit_position(a) + highest_bit_position(b) < n then multiplication doesn't overfull, if > n it ddefinitely does overflow, and if == n then we gotta do further checking. Since the majority of inputs won't hit the == n case, it would be decently performant in the typical case. – Overstretch

Answer 4

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

Cispadane

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

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

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

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

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. – Clockmaker

Answer 5

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.

Colton

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! – Haletky

"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? – Ransell

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

@Iconoduly 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)? – Ransell

@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." – Iconoduly

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

@Iconoduly 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. – Ransell

@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. – Iconoduly

@Iconoduly 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? – Ransell

Let us continue this discussion in chat. – Iconoduly

@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. – Stylobate

Answer 6

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.

Collocation

Answer 7

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

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.

Of note, this uses the partial Karatsuba method multiplicative decomposition to compute the high 32 bits of the 64-bit multiplication to check if any of them should become set to know if the 32-bit multiplication overflows.

If using C++, you can turn this into a neat little lambda to compute overflow so the inner workings of the detector get hidden:

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

Plague

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.. – Plague

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. – Wisteria

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. – Plague

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. – Wisteria

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

@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. – Klingensmith

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

The multiplication "solution" is wrong. For example, x = 0x80000000 and y = 2 would overflow, but since (y >> 16) == 0 in this case, the code does not detect that. I see no easy fix; I suggest to delete that part of the answer. – Nobility

Thank you for providing a counter-example for the multiplication case. The simple way to fix this is to perform more of the Karatsuba decomposition (en.wikipedia.org/wiki/Karatsuba_algorithm) for the multiplication and if any of those sub-parts results in bits in this high 32-bit section, the result is overflow. – Plague

@Matt, that fails when x[i] and y[i] are both 0xFFFFFFFF and carry is 1. You have to test for overflow before adding carry, and at that point you might as well ditch the |. – Starrstarred

@yurikilochek, you make a good point. It's been forever since I've thought about this, but I'm not sure how I missed that. – Klingensmith

Answer 8

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 a^b=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:

• x⁰ == 1 (all permutations of 9, 8, 7, 6, 5, 4, 3, 2 are solutions)
• x¹ == x (no solution possible)
• 0^b == 0 (no solution possible)
• 1^b == 1 (no solution possible)
• a^b, 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)

Bluff

why are you not using 9.876.543.210 as the upper limit? – Raper

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

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 – Jankey

Answer 9

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

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

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.

Ascocarp

Doesn't this invoke undefined behavior? Signed overflow is undefined behavior. Correct me if I'm wrong, but even if you don't use the result, you get UB. stackoverflow.com/questions/16188263/… – Dietetic

You might have to do the multiplication in assembly too if you want to avoid UB. – Dietetic

Answer 10

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

It is based on the concepts explained on this page: https://www.cs.umd.edu/~meesh/cmsc311/clin-cmsc311/Lectures/lecture22/overflow.pdf (https://web.archive.org/web/20170121033813/http://www.cs.umd.edu:80/class/spring2003/cmsc311/Notes/Comb/overflow.html wayback machine)

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.

Unhouse

The link is broken: HTTP 403: Forbidden – Steelwork

Answer 11

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.

Adhern

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. – Archeozoic

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

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

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

@Haletky Only if overflows were expected to be frequent. – Ransell

Answer 12

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.

Winfield

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/… – Kibler

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

Answer 13

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
}

Mulder

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. – Readjust

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

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

@Readjust 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 – Ambiversion

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. – Osteomyelitis

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. – Burl

Answer 14

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

Bingle

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

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

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. – Bingle

<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> – Psychophysics

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. – Psychophysics

Answer 15

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

Kentledge

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

Answer 16

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.

Graffito

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. – Stylobate

Answer 17

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.

Rotifer

Answer 18

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

Penthea

Answer 19

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

Crow

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

Answer 20

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.

Carlsbad

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

Answer 21

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

Barnabe

Answer 22

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.

Haunted

Answer 23

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.

Stretto

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

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

Answer 24

To expand on Head Geek's answer, there is a faster way to do the 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 );
}

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.

Emersen

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. – Nu

Answer 25

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

Preview

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. – Barnabe

Answer 26

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

Dore

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) – Orvah

Answer 27

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

Tupiguarani

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

Answer 28

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

Lacrimatory

Answer 29

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

Byplay

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

Answer 30

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

    }
}

Pestiferous