Correct Code Is Hard To Write

2/25/2004 4:37:56 PM

Correct Code Is Hard To Write

Even the simplest, most primitive data structures have special cases that make it difficult to find all bugs. Consider integers, for example.

How would you write a Compare function for two integers, that returns a negative value for less-than relationship, zero for equality, and a positive value for a greater-than relationship? If you write the following,

public void Compare(int i1, int i2)
{
   return i1-i2;
}

you would have a problem with extreme values (values with the 30th bit set), because Compare(int.MinValue, int.MaxValue) will incorrectly return 1 and Compare(int.MaxValue, int.MinValue) will incorrectly return -1 in unchecked mode. Using checked mode for overflow checking doesn't help either, because an exception should not have to be fired from this function. The correct approach is

public int Compare(int i1, int i2)
{
   return i1>i2 ? 1 : i1<i2 ? -1 : 0;
}

With floating-point numbers, the use of a sign bit eliminates the possibility of this problem. However, many floating point values are not comparable, in which case the result of the Compare will be zero.

Now, let's write an Abs function, which returns the absolute value of an integer. Sounds easy, right?

public int Abs(int n)
{
   return n>=0 ? n : -n;
}

The problem is that, with machine integers, 0 is not the only value that is the negation of itself. The int.MinValue is also the negation of itself, because there is no way to represent its positive counterpart. The correct implementation is the following:

public int Abs(int n)
{
   return n>=0 ? n : checked(-n);
}

I just wanted to point out that writing correct code is not trivial. One last thing, I recommend the use of arithmetic overflow checks for Debug builds, at least.

Comments

 

Navigation

Categories

About

Net Undocumented is a blog about the internals of .NET including Xamarin implementations. Other topics include managed and web languages (C#, C++, Javascript), computer science theory, software engineering and software entrepreneurship.

Social Media