Integer overflow detection C# for Add

Question

It's easy to get C# to throw an exception on an integer overflow. However, that's not what I'm looking for. I want to detect the overflow so I can continue the calculation in the high order. I'm building a sort of big int implementation.

I could catch the overflow exception, but that's not great for performance. Not to mention that it's conceptually incorrect.

Any idea how to check for overflow without exceptions?

Do you know that there's a BigInteger class in C#, or are you doing this just for practice? — Rob
– Rob ♦, Commented Aug 15, 2015 at 6:32
I assume the overflow is with a Single(), Double(), or Float() object when you are using Parse() or when you are performing a math operation. If the error is occurring due to Parse than use ParseExact(). If it is a math operations, it is usually caused by denominator of a division being very small (or zero). So check denominator before dividing. — jdweng
– jdweng, Commented Aug 15, 2015 at 6:35
I spent some time thinking about this as the question was an interesting bit of academics to ponder. My conclusion however is that you'd end up needing to write your own overflow detection in all operations that something like checked already does. I would expect any good implementation to be equally slow as what you're wanting to avoid, but with more bugs and gotchas. Without knowing the exact problem you're trying to solve, I would suggest the approach you're trying to avoid. — Trevor Ash
– Trevor Ash, Commented Aug 15, 2015 at 6:42
I'm with Atoms. I think it's not possible to know if overflow may happen before doing a possible overflow method. — Alireza
– Alireza, Commented Aug 15, 2015 at 8:13

Ivan Stoev · Accepted Answer · 2015-08-15 20:18:38Z

5

If you are seeking for a carry behavior, other answers/comments cover that pretty well. However, I find the original question to be an interesting brain puzzle (although not practically useful), specifically what is the best performance pure C# way to detect 2 signed integers add overflow. Ideally it would generate a minimum IL instructions with no branches. Here is the best I ended up - one with bool flag (true when overflow, false otherwise) and another with int "bit" (1 when overflow, 0 otherwise). Both satisfy the above criteria, "bit" version has few less IL instructions. Enjoy:-)

static int Add(int a, int b, out bool overflowFlag)
{
    unchecked
    {
        int c = a + b;
        overflowFlag = ((a ^ b) >= 0) & ((a ^ c) < 0);
        return c;
    }
}
static int Add(int a, int b, out int overflowBit)
{
    unchecked
    {
        int c = a + b;
        overflowBit = (int)((uint)((a ^ c) & ~(a ^ b)) >> 31);
        return c;
    }
}

answered Aug 15, 2015 at 20:18

Ivan Stoev

208k17 gold badges356 silver badges376 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Boyd Over a year ago

Though I'm probably not going to use this (BigInteger serves my purpose), it does answer the question and in a pretty cool way. The downside is that you probably can't do something similar for Multiplication.

Ivan Stoev Over a year ago

absolutely - that's why I mentioned it's usefulness at the beginning. but glad that you liked it:-)

Zotta · Accepted Answer · 2015-08-15 08:06:47Z

1

If you want to implement addition and subtraction with carry, I really recommend using uint instead of int! Cast both values to ulong before doing the calculation:

//Adds a and b
uint[] a = ... , b = ... ;//input
ulong carry=0
for(int i=0;i<length;i++)
{
    carry += (ulong)a[i] + (ulong)b[i];
    uint result = (uint)carry;
    carry >>= 32;//divide by 2^32
    //TODO: store result
}
//TODO: process remaining carry

I had problems with sign extension, when i first implemnted something like this, hence the unsigned types everywhere.

answered Aug 15, 2015 at 8:06

Zotta

2,6131 gold badge22 silver badges30 bronze badges

1 Comment

Boyd Over a year ago

What kind of problems did you have with the sign extension?

Collectives™ on Stack Overflow

Integer overflow detection C# for Add

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related