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

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.

Value of a value of b a > b a - b > 0
100 100 False False
100 50 True True
-2000000000 500000000 False True
2000000000 -500000000 True False

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.

Calculation Calculation result calculated by hand Result of calculation in Java
2147483647 + 5 2147483652 -2147483644
2147483 * 10000 21474830000 -6480
2147483647 - (-5) 2147483652 -2147483644
-2147483648 - 5 -2147483653 2147483643

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

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.

Recommended Posts

The end of catastrophic programming # 03 "Comparison of integers, if" a> b ", assume that it is" a --b> 0 ""
The end of catastrophic programming # 01 "Do it with the absolute value of an integer"
[Java] You might be happy if the return value of a method that returns null is Optional <>
Memo: [Java] If a file is in the monitored directory, process it.
Get the type of an array element to determine if it is an array
If it is Ruby, it is efficient to make it a method and stock the processing.
The patchForObject added to RestTemplate cannot be used effectively if it is a default implementation (the one that uses HttpURLConnection).
A description of Interface that is often mistaken
Is there a performance difference between Oracle JDK and OpenJDK at the end of 2017?
Create a package that is a common development component of Automation Anywhere A2019 # 1-First, build and use the SDK sample as it is
[Quarkus] A trap that doesn't work even if you copy and paste the GCP Pub / Sub sample as it is
At the time of dialogReturn event, I checked because it is not updated even if I specify a component with update
The comparison of enums is ==, and equals is good [Java]
The question of which is better, if or switch
Is it faster if the docker bind mount is readonly?
Program to determine if it is a leap year
A memo of the program that allows you to realize that the probability of dice rolling is about 1/6
Even if I write the setting of STRICT_QUOTE_ESCAPING in CATALINA_OPTS in tomcat8.5, it is not reflected.
[Docker] Is it good enough to call it a multi-stage build? → The story that became so good