The end of catastrophic programming # 03 "Comparison of integers, if" a> b ", assume that it is" a --b> 0 ""

An ordinary programmer understands intuitively and reflexively, I would like to write an article about a rudimentary and simple story. Because of the rudimentary nature, a heavy programmer like me I do it well (even if I thought I understood it).

If there are any mistakes or inappropriate content, please comment We will consider corrections and adjustments to the content.

This time, "The end of catastrophic programming # 01" Do it with the absolute value of an integer "" I wrote an article based on the post in the comment section of. Thank you for your comment.

1. Comparison of left side and right side

Programming is sometimes math, sometimes not math.

In some areas of mathematics If ʻa> b, then ʻa --b> 0 would be correct.

In programming There are many cases where ʻa> b holds, but ʻa --b> 0 does not hold.

Similarly

• ʻA <b holds, but ʻa --b <0 does not hold
• ʻA <= b holds, but ʻa --b <= 0 does not hold
• ʻA> = b holds, but ʻa --b> = 0 does not hold
• ʻA == b holds, but ʻa --b == 0 does not hold

There are many cases.

2. This time we are talking about integer type

** This time, I will limit it to integer types **. ** Floating point type requires attention in another dimension **, so I will write an article at another time.

To make the story easier Consider a 32-bit signed integer type. In Java, C #, and C / C ++, it's called an int type. (In C / C ++, it is assumed that the int type is a 32-bit processing system. For some people, you can imagine int32 or Int32. )

The range that a 32-bit signed integer type can represent is, for many programming languages, -2147483648 to 2147483647 It should be.

1.3. Let's try it for the time being

Try to execute the following code around Java, C #. It just shows the boolean values (True or False) of ʻa> b and ʻa --b> 0. Try putting some values in ʻa and b`.

For the time being, I will try it in C #. Even if you do it in Java or C / C ++, the screen output part is slightly different.

//Enter values for each of a and b and try various things.
int a = 100;
int b = 100;

//For Java, System.out.printf("a > b : %s%n", (a > b));And.
Console.WriteLine("a > b : {0}",     (a > b));
Console.WriteLine("a - b > 0 : {0}", (a - b > 0));

After trying some, it looks like this.

In the first two, the truth of ʻa> b and ʻa --b> 0 match, The bottom two do not match.

3. Always be careful even in four arithmetic operations

You should always be careful even with simple operations such as addition, subtraction, multiplication, and division (+,-, \ *, /).

For integer type Addition, subtraction, multiplication and division (+,-, \ *, /) may ** overflow **. In addition, integer division (/) will result in an error (exception, crash, etc.) when divided by ** 0 in many languages and environments **.

Also, divisions that include ** negative integers can create difficult situations **.

For example

int a = 5;
int b = -2;
int answer = a / b;

If you do, there are languages / environments where ʻanswer becomes -2and languages / environments where it becomes-3. For example, if the division of integers is ** cut off **, it is -2, If it works as ** Floor function (floor function) **, Since an integer value smaller than the operation result is adopted, it becomes -3`.

Similarly, modulo operations (%) containing negative integers may behave differently depending on the language and environment.

If you believe that integer division (/) will not overflow, You may want to try (minimum of type int) / (-1). (This operation may be treated specially depending on the language and environment.)

It's a little off topic, but this time we'll consider overflow.

4. Sometimes I inadvertently forget to overflow by subtraction

If you can only express from -2147483648 to 2147483647 It's easy to imagine that addition (+) and multiplication (*) can cause an overflow. It is natural that subtraction (-) may overflow, but Depending on the situation, you may inadvertently forget it.

The following is an example of overflow beyond the range that can be expressed.

The bottom operation is below the lower limit that can be expressed in the negative range, This is also an overflow (overflow in the negative direction). Some people call this "underflow", but in general When the number is so close to 0 that it cannot be expressed with floating point precision, It should be correct to call it underflow. Strictly speaking, underflow is a misuse of the above situation for integer values. (Usually, it is a range that can be understood by the flow of the story, so it is delicate to point out.)

5. End

When creating a program that performs complicated calculations, I think that overflow often makes me feel uncomfortable.

In a simple case, At first glance, there is a possibility of doing it in a case that does not seem to be directly related to this story.

To give one concrete example Such as Comparator and Comparable interface, It seems that there are some cases where the mechanism of ordering the instances of objects is used.

For example, if you want to sort the instances in the list as the programmer wants. If you have instances A and B of an object This is the one used to determine which is the first in the order.

In the case of using a class, the code will be long, so we will use the value type example. Below is an example from C #, but it looks similar in Java. Recently, the number of languages that can use lambda expressions has increased, so I will write in lambda expressions. (I can write it a little more clearly, but I write it redundantly with an emphasis on clarity.)

//Array of integer values
var array = new int[] { 3, 1, -2147483647, -5 };

//Store in list
var list = new List<int>(array);

//Evaluate and sort by lambda expression
list.Sort(
  (a, b) =>
  {
    return (a - b);
  }
);

foreach (var item in list)
{
  Console.WriteLine(item);
}

The point is the lambda expression part.

(a, b) =>
{
  return (a - b);
}

but,

int compare(int a, int b)
{
  return (a - b);
}

I think it is easy to understand.

In many frameworks, Comparator comparison methods and comparison functions are

• Negative integer if ʻa is less than b`.
• 0 if ʻa and b` are equal.
• A positive integer if ʻa is greater than b`.

It is supposed to be implemented to return.

With this specification, programmers can understand very well what they want to do with a single operation. Due to the specifications of the app, (a --b) is If it is clear that it is within the range where there is no possibility of overflow There is no problem with return (a --b);.

If there is a possibility of overflow, the sort result may not be what you expected.

The code example above is intended to sort the numbers in ascending order, The result is as follows.

1
3
-2147483647
-5

It's not in ascending order at all. ** Also note that the results will vary depending on the initial order in the original array ʻarray`. ** **

5. Countermeasures

Basically, you should always be careful about the possibility of overflow if you perform four arithmetic operations.

In the Comparator example, if you don't need to do four arithmetic operations, There is also a method of implementing without four arithmetic operations. In programming, a naive and stupid implementation may actually be safer or more efficient. There is ok.

In this example, ʻarray` was an int type array, so You don't have to define the sort yourself in the first place, I would like you to read it appropriately when sorting objects that you have defined yourself.

list.Sort(
  (a, b) =>
  {
    int result = -1;

    if( a > b )
    {
        result = 1;
    }
    else if( a == b )
    {
        result = 0;
    }

    return result;  
  }
);

Or if you use the ternary operator

list.Sort(
  (a, b) =>
  {
    return (a > b) ? 1 : ((a == b) ? 0 : -1);
  }
);

Or a naive implementation will work.

If the object to be compared has a Comparable implementation, It's a good idea to take advantage of it.

In C #

list.Sort(
  (a, b) =>
  {
    return a.CompareTo(b);
  }
);

It feels like.

For Java I think you will use ʻInteger.compare (a, b) `and so on.