課題内容

僕が通っている学校のある授業でこんな課題が出されました。

10倍整数型

Javaのint型の上限・下限を1桁増やし、-21474836489〜21474836479 の範囲の整数を扱う IntegerX10 クラスを作成せよ。

なお、以下のひな型に沿って実装すること。(...の部分を自分で実装する)

IntegerX10.java

public class IntegerX10 {
  // 1の位の値
  public int value1;
  // 10以上の位の値
  public int value10;

  public IntegerX10(...) {
    ...
  }

  public IntegerX10 add(IntegerX10 v) {
    ...
  }

  public String toString() {
    ...
  }
}

通常、int型は4バイトで表されるため、最大値Integer.MAX_VALUEは2147483647になりますが、それを1桁増やそう！という課題になっています。

期待する動作例

下記のコードを作成し、

IntegerX10Main.java

public class IntegerX10Main {
    public static void main(String[] args) {
        IntegerX10 v1 = new IntegerX10(Integer.MAX_VALUE);
        IntegerX10 v2 = new IntegerX10(Integer.parseInt(args[0]));

        IntegerX10 v3 = v1.add(v2);

        System.out.println(v1 + " + " + v2);
        System.out.println(" = " + v3);
        System.out.println(" = 10*" + v3.value10 + " + " + v3.value1);
    }
}

コンパイルして実行すると、

$ java IntegerX10Main 10
2147483647 + 10
 = 2147483657
 = 10*214748365 + 7

となり、Integer.MAX_VALUEに引数の値(10)を足せていることがわかります。

この問題に取り組んでいたところ、いろいろ考慮しないといけないことがあったので、真剣に解いてみようと思います。

先生が意図した解答

この授業ではJava自体のスキルを磨くためではなく、オブジェクト指向について理解するためなので、そこまで複雑なことは求められていません。
そのため、先生が求める回答は以下のようになります。

※あくまでも僕が勝手に先生の気持ちになって考えただけなのでもしかしたら違う可能性もありますが悪しからず笑

IntegerX10.java

public class IntegerX10 {
  // 1の位の値
  public int value1;
  // 10以上の位の値
  public int value10;

  public IntegerX10(long v) {
    this.value1 = (int) (v % 10);
    this.value10 = (int) (v / 10);
  }

  public IntegerX10 add(IntegerX10 v) {
    IntegerX10 res = new IntegerX10(0);
    res.value1 = this.value1 + v.value1;
    res.value10 = this.value10 + v.value10;
    res.value10 += (int) (res.value1 / 10);
    res.value1 %= 10;
    return res;
  }

  @Override
  public String toString() {
    if (this.value10 == 0) {
      return Integer.toString(this.value1);
    } else {
      return Integer.toString(this.value10) + Integer.toString(Math.abs(this.value1));
    }
  }
}

解説

コンストラクタ

コンストラクタではlong型を引数とすることでInteger.MAX_VALUEよりも大きい値を受け取ることができるようにします。

その上で、一の位を抽出するためにmod 10を、10以上の位を抽出するために10で割り、どちらもintにキャストすることでvalue1、value10に代入しています。

`add`関数

考え方としてはvalue10、value1それぞれを足し合わせればよいということです。
ただしvalue1を足した際に2桁になってしまうことがあるため、その時用に繰り上がりの処理を追加しています。

add実行時に新しいインスタンスで返しているのは先生からの実装例のヒントをもとに作成しているためです。
本記事内ではこれを仕様とし、addは非破壊的な関数として実装します。

`toString`関数

value10が0の時にInteger.toString関数を実行してしまうと0と出力されてしまうので、条件分岐で対処しています。

このあたりは、先生からの実装例のヒントをもとに作っているのでモヤモヤしますが、とりあえずこれを解答例としておきます。

問題点

この課題が出されて、何も躊躇なく上のコードを書いて提出できたなら、課題が早く終わっていいですね。

ただし、このプログラムでは負の値を加算する計算をしたときにバグが起こります。
例えば、以下の場合はどうでしょうか。

IntegerX10 v1 = new IntegerX10(100);
IntegerX10 v2 = new IntegerX10(-18);
IntegerX10 v3 = v1.add(v2);
System.out.println(v3);

やりたいことは、$100 + (-18) = 82$です。
実際に実行してみると、

あれ？違いますね…

(value10, value1) の表記で上の計算を表してみると

(10, 0) + (-1, -8) = (9, -8)

となり、v3の値は(9, -8)になります。
この値をtoString関数にかけると、value1の絶対値がとられ、98になってしまうのです。。

原因

原因は、同じ数値の表し方が2つあるためです。
例えば、1の表現方法は、(0, 1) と(1, -9)の2つがあります。

解答①

上記の問題を解決するために、(value10, value1)が(0, 1)、(1, -9)のどちらでも正しい値を出力するようにtoString関数に細工していきましょう。

細かい算出過程は省きますが、以下の表に当てはまるとうまく表示できるようになります。

`value10`	`value1`	文字列
0	×	`value1`
正	負	`value10 - 1` + `10 + value1`
負	正	`value10 + 1` + `-10 + value1`
それ以外	それ以外	`value10` + `abs(value1)`

※ ×はDon't care

ただし、value10 - 1やvalue10 + 1の計算後の値が0の場合には出力してはいけません。

ということで、これらを考慮して実装してみたところ次のようになります。

IntegerX10.java

    public class IntegerX10 {
      // 1の位の値
      public int value1;
      // 10以上の位の値
      public int value10;
    
      public IntegerX10(long v) {
        this.value1 = (int) (v % 10);
        this.value10 = (int) (v / 10);
      }
    
      public IntegerX10 add(IntegerX10 v) {
        IntegerX10 res = new IntegerX10(0);
        res.value1 = this.value1 + v.value1;
        res.value10 = this.value10 + v.value10;
        res.value10 += (int) (res.value1 / 10);
        res.value1 %= 10;
        return res;
      }
    
      @Override
      public String toString() {
-       if (this.value10 == 0) {
-         return Integer.toString(this.value1);
-       } else {
-         return Integer.toString(this.value10) + Integer.toString(Math.abs(this.value1));
-       }        
+       int v10 = 0, v1 = 0;
+       if (this.value10 == 0) {
+         v1 = this.value1;
+       } else if (this.value10 > 0 && this.value1 < 0) {
+         v10 = this.value10 - 1;
+         v1 = 10 + this.value1;
+       } else if (this.value10 < 0 && this.value1 > 0) {
+         v10 = this.value10 + 1;
+         v1 = -10 + this.value1;
+       } else {
+         v10 = this.value10;
+         v1 = Math.abs(this.value1);
+       }
+       return (v10 != 0 ? Integer.toString(v10) : "") + Integer.toString(v1);
      }
    }

toStringが結構ボリューミーになりましたね。
もっといい方法を考えてみましたが、僕の力ではこれが精一杯でした。

もちろん、上で問題だったコードを実行してみても82と出力してくれるようになります。

問題点

もう問題は解決したと思いましたか？
実は、まだ罠があるんです。
それは、IntegerX10の最大値、最小値付近で加減算をする場合です。

具体的な例を挙げると以下の計算が当てはまります。

(2147483647, 0) + (0, 9) = (2147483647, 9)
(2147483647, 0) + (1, -1) = (2147483648, -1)

両方とも、$21474836470 + 9 = 21474836479$つまりIntegerX10の最大値を計算しようとしています。
実際に計算するコードは以下のようになります。

System.out.println(new IntegerX10((long) Integer.MAX_VALUE * 10).add(new IntegerX10(9)));
System.out.println(new IntegerX10((long) Integer.MAX_VALUE * 10).add(new IntegerX10(10).add(new IntegerX10(-1))));

実行すると、

21474836479
-21474836481

となり、下の値がおかしくなっています。

原因

value10とvalue1の計算過程をよく見てください。
右辺を見ると、下側の右辺のvalue10の値$2147483648$がintの最大値$2147483647$を超えていることにお気づきでしょうか。

そのため、add関数内のres.value10 = this.value10 + v.value10の計算でオーバーフローが発生し正しく計算できなくなっていたのです。

解答②

上記の問題を解決するために、add関数の最初に、引数vの内部変数を(1, -1)から(0, 9)に変更するようにすればよいのです。
最小値付近では同じような原理でアンダーフローにもなるため、それらを考慮してadd関数を書き換えたものが以下のものになります。

IntegerX10.java

    public class IntegerX10 {
      // 1の位の値
      public int value1;
      // 10以上の位の値
      public int value10;
    
      public IntegerX10(long v) {
        this.value1 = (int) (v % 10);
        this.value10 = (int) (v / 10);
      }
    
      public IntegerX10 add(IntegerX10 v) {
+       if (this.value10 > 0 && v.value1 < 0) {
+         v.value10 -= 1;
+         v.value1 = 10 + v.value1;
+       } else if (this.value10 < 0 && v.value1 > 0) {
+         v.value10 += 1;
+         v.value1 = -10 + v.value1;
+       }
    
        IntegerX10 res = new IntegerX10(0);
        res.value1 = this.value1 + v.value1;
        res.value10 += this.value10 + v.value10;
        res.value10 += (int) (res.value1 / 10);
        res.value1 %= 10;
        return res;
      }
    
      @Override
      public String toString() {
        int v10 = 0, v1 = 0;
        if (this.value10 == 0) {
          v1 = this.value1;
        } else if (this.value10 > 0 && this.value1 < 0) {
          v10 = this.value10 - 1;
          v1 = 10 + this.value1;
        } else if (this.value10 < 0 && this.value1 > 0) {
          v10 = this.value10 + 1;
          v1 = -10 + this.value1;
        } else {
          v10 = this.value10;
          v1 = Math.abs(this.value1);
        }
        return (v10 != 0 ? Integer.toString(v10) : "") + Integer.toString(v1);
      }
    }

具体的な処理内容としては、
value10が正である場合、引数vによってはオーバーフローする恐れがあるので、(1, -1)などという値を(0, 9)としてvalue10を加算しないようにする。
value10が負である場合、引数vによってはアンダーフローする恐れがあるので、(-1, 1)などという値を(0, -9)としてvalue10をg減算しないようにする。
という風にしています。

これで問題のプログラムもきちんと計算できるようになりました🎊

最終プログラム

最終的なプログラムは以下のようになりました。（解答②のものと同じです。）

IntegerX10

public class IntegerX10 {
  // 1の位の値
  public int value1;
  // 10以上の位の値
  public int value10;

  public IntegerX10(long v) {
    this.value1 = (int) (v % 10);
    this.value10 = (int) (v / 10);
  }

  public IntegerX10 add(IntegerX10 v) {
    if (this.value10 > 0 && v.value1 < 0) {
      v.value10 -= 1;
      v.value1 = 10 + v.value1;
    } else if (this.value10 < 0 && v.value1 > 0) {
      v.value10 += 1;
      v.value1 = -10 + v.value1;
    }

    IntegerX10 res = new IntegerX10(0);
    res.value1 = this.value1 + v.value1;
    res.value10 += this.value10 + v.value10;
    res.value10 += (int) (res.value1 / 10);
    res.value1 %= 10;
    return res;
  }

  @Override
  public String toString() {
    int v10 = 0, v1 = 0;
    if (this.value10 == 0) {
      v1 = this.value1;
    } else if (this.value10 > 0 && this.value1 < 0) {
      v10 = this.value10 - 1;
      v1 = 10 + this.value1;
    } else if (this.value10 < 0 && this.value1 > 0) {
      v10 = this.value10 + 1;
      v1 = -10 + this.value1;
    } else {
      v10 = this.value10;
      v1 = Math.abs(this.value1);
    }
    return (v10 != 0 ? Integer.toString(v10) : "") + Integer.toString(v1);
  }
}

おわりに

先生は特に深いことを考えずにこの課題を出したと思いますが、
このように身近な所にもバグの原因は隠れているんだなと改めて感じました。

個人的なプライドですが、課題（特にプログラム系）ではあまり妥協したくないので、課題に取り組むついでに記事にしてみました。

余談

いや、こんなもんひな型無視してlong使えばもっと簡略化できるでしょ…
オーバーフロー・アンダーフロー時の値は不定ということにしておけば、

IntegerX10Long

public class IntegerX10Long {
  public static final long MAX_VALUE = 21474836479l;
  public static final long MIN_VALUE = -21474836489l;

  public long value;

  public IntegerX10Long(long v) {
    this.value = v;
  }

  public IntegerX10Long add(IntegerX10Long v) {
    long newValue = this.value + v.value;
    if (newValue > MAX_VALUE)
      newValue = MAX_VALUE;
    else if (newValue < MIN_VALUE)
      newValue = MIN_VALUE;
    return new IntegerX10Long(newValue);
  }

  @Override
  public String toString() {
    return Long.toString(this.value);
  }
}

でいいんじゃね。

てか、アンダーフロー・オーバーフロー時の値が不定なら偶然うまく足し算できちゃってるだけでlong型そのまま使えばいいんじゃね…と思ってみたり