abs(int)のコーナーケース

与えられたある整数の絶対値を取得するような
一見シンプルなメソッドにもコーナーケースが存在する。
言語によって挙動が異なるので注意する必要がある。

期待される振る舞い

絶対値を取得するメソッドなので直感的にはこのように動いて欲しい。
$$ abs(x) = \left\{ \begin{array}{} x & ( x > 0) \\ 0 & ( x = 0) \\ -x & ( x < 0) \\ \end{array} \right. $$

言語によって実装は異なるため実際には下記。 $$ abs(x) = \left\{ \begin{array}{} x & ( x > 0) \\ 0 & ( x = 0) \\ -x & ( x < 0) \\ ? & (x = 型で表現できる最小値) \\ \end{array} \right. $$

原因

符号付数値表現 - Wikipedia

符号付整数値の内部表現が2の補数となっているため
表現できる幅が負の方向に1だけ広い。

例えば8bit符号付き整数型の場合
最大値は 01111111 127
最小値は 10000000 -128
最小値-128の絶対値である128は8bitで表現できる範囲を超えてしまう。

言語ごとの挙動の違い

1. 最小値をそのまま返却する (C++, Java)

#include <climits>
#include <cstdlib>
#include <iostream>
 
using namespace std;  
 
int main(void) {
    cout << INT_MIN << endl;
    cout << abs(INT_MIN) << endl;
}

import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        System.out.println(String.valueOf(Integer.MIN_VALUE));
        System.out.println(String.valueOf(Math.abs(Integer.MIN_VALUE)));
    }
}

結果
-2147483648
-2147483648

負数そのまま返しとるやんけ！！！

実際問題、値として最小値が入ってくるケースはごくごく稀なものの
内部的にabsを利用している、みたいな場合に発生すると辛そう。
というか正の値を返して欲しい。

Javaでの内部実装はこちら。

    // Math.java内の実装
    public static int abs(int a) {
        return (a < 0) ? -a : a;
    }

そりゃそうなるかという感じ。

2. 例外を発生させる (C#)

using System;
 
public class IntMin {
    public static void Main(){
        Console.WriteLine(Math.Abs(Int32.MinValue));
    }
}

結果
Unhandled Exception:
System.OverflowException: Negating the minimum value of a twos complement number is invalid.
  at System.Math.AbsHelper (System.Int32 value) [0x00015] in <8f2c484307284b51944a1a13a14c0266>:0 
  at System.Math.Abs (System.Int32 value) [0x00009] in <8f2c484307284b51944a1a13a14c0266>:0 
  at IntMin.Main () [0x00010] in /workspace/Main.cs:6 
[ERROR] FATAL UNHANDLED EXCEPTION: System.OverflowException: Negating the minimum value of a twos complement number is invalid.
  at System.Math.AbsHelper (System.Int32 value) [0x00015] in <8f2c484307284b51944a1a13a14c0266>:0 
  at System.Math.Abs (System.Int32 value) [0x00009] in <8f2c484307284b51944a1a13a14c0266>:0 
  at IntMin.Main () [0x00010] in /workspace/Main.cs:6 

桁あふれなども含めて例外出して欲しい派なので
静的型付け言語において、個人的に望ましい動作はこっち。

3. 多倍長整数として返却する (Python)

任意精度演算 - Wikipedia

# coding: utf-8
import sys
 
print sys.maxint
print -sys.maxint - 1
print abs(-sys.maxint - 1)

結果
9223372036854775807
-9223372036854775808
9223372036854775808

表現できる範囲を超えたら内部的に広げてしまって返す。
内部でどうなっているのか、あまり意識せずに多倍長整数を扱えるのは自然だし便利。
調べた限りだとRubyもそんな感じ。

そもそも

    static Random rnd = new Random();

    static int random(int n) {
        return Math.abs(rnd.nextInt()) % n;
    }

書籍Effective Javaのある項目で、上記コードにはいくつか問題が
あってそれはどこでしょう？という記述に絡めて紹介されていた。

rnd.nextInt()は極めて稀にInteger.MIN_VALUEを返すので
極めて稀に負数が返却されるよって話で、うわ怖ってなって
他言語だとどうなのだろうと思ったのが調べたきっかけ。

確かにリファレンスには注意が書いてあるけど、absなんてどの言語にもあるし
雰囲気で使えちゃうので、知らずに実世界でこのバグ踏んでたらとても辛そう。

引き続き慎重にやっていきましょう。