1

consider the following:

(i+j)/2

i and j are both 32 bit integers and the result should also be. But in the little equation, there's a hidden overflow, i+j could become larger then a 32 bit integer even though the result would always be a 32 bit integer.

public class Sum{
     public static void main(String []args){
        int i = 2147483647;
        int j = 2147483647;                       
        System.out.println((i + j)/2);
     }
}

Gives me -1 as a result.

How do you guard against situations that can overflow but are not always obvious. Is there a pattern that describes this?

(apart from declaring everything long)

I'm looking for a general answer, the java example is just to provide an example, my Delphi does the same.

  • 2
    Guard? You mean, as in "prevent this from happening?" Then how would you ever use the + operator? Using long only shifts the problem to the next level. You always risk overflow unless you establish your own data types with half the language-provided range. – Kilian Foth Aug 13 '14 at 11:25
  • 1
    @KilianFoth You don't need your own data type, just your own math operators that check for overflow. You could argue that nothing's forcing you to use the non-overflow version, but I'd retort that nothing forces you to use your custom numeric types either. – Doval Aug 13 '14 at 11:33
  • You're right, I totally forgot that you can write your own + in C++ (because I haven't used it professionally). – Kilian Foth Aug 13 '14 at 11:40
  • In many cases, you don't need any guards, because the inputs are naturally restricted to a range that won't overflow. – Bart van Ingen Schenau Aug 13 '14 at 12:35
  • 1
    In case you haven't changed it yet, your mean value calculator doesn't need to use large intermediate values. Here is an example. To stray from language-agnosticism, C#'s checked is related to this and 28 million is no sweat for its decimal type. – Nathan Cooper Aug 13 '14 at 14:22
7

You have three choices, none of which are ideal for all situations:

Detect Overflows. Most languages have a way to determine the largest possible value for integer data types. The addition in your example will result in an overflow whenever j > (max_value_of_type - i). You will have to check every use for overflows or build a library or class to does it for you.

Use Larger Types. If there are larger integers available, use those to do your intermediate calculations and convert back to the smaller type when finished. The hitch here is that you must understand whether the results of those calculations are guaranteed to fit the smaller size if that's what you'll be returning. Your example of (i + j) / 2 fits, but (i * j) / 2 doesn't.

Restrict the Input Values. This is a lot like both of the above in that you're limiting the inputs to values you know won't cause an overflow and at the same time making the integers large enough to hold the result.

| improve this answer | |
  • How about the python way? Integers are as large as they need to be to fit the number, no overflow possible. That surely costs a lot of run time, but you should still add it as an option. – nwp Aug 13 '14 at 12:32
  • 2
    @nwp: Arbitrary precision falls under the heading of using larger types. – Blrfl Aug 13 '14 at 12:34
1

You can define your own arithmetic operators, for example like this.

int operator + (int a, int b) {
    int res = a + b;
    if(a > 0 && b > 0 && res < 0) {
        throw new ArithmeticOverflowException();
    } else if(a < 0 && b < 0 && res > 0) {
        throw new ArithmeticUnderflowException();
    }
    return res;
}
| improve this answer | |
  • 1
    if b or a is 0 the answer may be negative otherwise the answer must be positive? – Pieter B Aug 13 '14 at 12:22
  • Yep, you got me there. The condition must be more clever. :) – Haspemulator Aug 13 '14 at 12:23
  • 2
    Note: In C/C++ signed overflow is undefined behavior, so you must test for overflow before adding. You can do something like this: if (a > INT_MAX - b) { /* handle overflow */ }. – Doval Aug 13 '14 at 12:26
  • 3
    What language is this? It looks like C++ to me, but C++ does not allow defining operators on built in data types only, so you would need to define your own data type Int. – nwp Aug 13 '14 at 12:26
  • 1
    @Haspemulator using code is fine, but it helps to explain what the code is doing and why. – user22815 Aug 13 '14 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.