How to know a value overflows without recurring to a runtime OverflowException

Question

So the question is:

Given a native integral type that represents the largest possible number in a given compiler (language?), for example ulong in C#, how do you detect that an input string representing a number is going to overflow the largest value that is representable by that given type without falling back to a checked context and a runtime OveflowException?

Obviously the C# compiler can detect constant integral overflows:

ulong l = 18446744073709551615; //ok
ulong l = 18446744073709551616; //compile time error: Integral constant is too large.

Is the compiler using a runtime OverflowException (or equivalent) under the hood? If so, is there a way to actually do this without recurring to a runtime exception or building a numeric type that can hold larger numbers like System.Numeric.BigInt? It is worth noting that BigInt has no native support in C# as the following is a compile time error although the integral constant is well inside the type's range:

BigInt i = 18446744073709551616; //compile time error: Integral constant is too large.

Does a behind-the-scenes-exception like TryParse also count as a no-no? — Jeroen Vannevel
– Jeroen Vannevel, Commented Sep 20, 2014 at 22:48
You could have a look at UInt64.TryParse, there is no try-catch on the road. However, i don't know the way the compiler actually uses. — Tim Schmelter
– Tim Schmelter, Commented Sep 20, 2014 at 22:50
@InBetween : "If I'm not mistaken TryParse just wraps Parse that does throw a runtime exception". No. It's an exception-free implementation. That's the point. — spender
– spender, Commented Sep 20, 2014 at 22:54
You could use a unchecked context and make hardware-like overflow detection, but not sure that's better than exceptions. — Mephy
– Mephy, Commented Sep 20, 2014 at 22:56
@InBetween: for some reason my link above to Uint64.TryParse was not correct, here is what i originally wanted to link: referencesource.microsoft.com/#mscorlib/system/… — Tim Schmelter
– Tim Schmelter, Commented Sep 20, 2014 at 23:10

AlexD · Accepted Answer · 2014-09-20 23:21:02Z

1

Would something like this count as a solution?

string s1 = "18446744073709551616";
string s2 = ulong.MaxValue.ToString();
// assuming s1 contains digits only and no leading zeros
if(
    s1.Length > s2.Length ||
    s1.Length == s2.Length && string.CompareOrdinal(s1, s2) > 0
)
    Console.WriteLine("overflow");

answered Sep 20, 2014 at 23:21

AlexD

32.8k3 gold badges73 silver badges65 bronze badges

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

2 Comments

InBetween Over a year ago

Nice one :) We thought about doing it this way but it seemed a hack more than anything else. We'd rather some clever mathematical trick but there doesn't seem to be any.

AlexD Over a year ago

@InBetween Well, more proper way would be to implement own parser. See NumberToUInt64

Roman Starkov · Accepted Answer · 2014-09-21 00:14:17Z

The compiler most likely just parses the input one digit at a time, with code similar to that of ulong.Parse but obviously adapted to the task.

The way ulong.Parse decides that it overflows is reasonably simple, but you do need to know how integers are parsed. ulong.Parse parses the input one character at a time. It maintains the ulong result, and for each character, it multiplies the result by 10, then adds the value of the character (which is 0 to 9), and it keeps doing so until the input runs out or the result overflows.

There are two overflow checks, because there are two things that can overflow: the multiplication by 10, and the addition. To check that the multiplication won't overflow, the current result is compared to 1844674407370955161. If the result is greater than that, and there are still digits left, the algorithm exits, reporting overflow. Observe that this number is the same as ulong.MaxValue with the last digit removed, making it the largest integer that can be multiplied by 10 without overflow.

Next, it needs to check whether adding a number from 0 to 9 will overflow. It does so by adding the number first, and then checking whether the result has decreased instead of increasing. This works because of how addition is implemented inside CPUs; basically the top bit of the result is discarded because it can't fit.

And that's it, really. If the characters run out without tripping any of the two checks above, the number is parsed successfully, otherwise it's an overflow.

Collectives™ on Stack Overflow

How to know a value overflows without recurring to a runtime OverflowException

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related