Alex Rivera | Logout

How do I detect unsigned integer overflow?

Asked 2008-10-13T22:53:21.407
758

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

c++ c integer-overflow
Edit
Report

3 Answers

40

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.

answered 2013-01-28T17:51:30.800
28

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
answered 2013-03-11T01:57:31.330
0

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.

answered 2013-02-13T17:34:18.263

Your Answer