学校の課題「10倍整数型：IntegerX10」について真剣に実装してみた

# 課題内容

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

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

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

```java: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桁増やそう！という課題になっています。

<details><summary>期待する動作例</summary>
下記のコードを作成し、

```java: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);
    }
}
```

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

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

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


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

# 先生が意図した解答

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

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

```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と出力されてしまうので、条件分岐で対処しています。

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

## 問題点

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

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

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

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

```console
98
```

あれ？違いますね…

`(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の場合には出力してはいけません。

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

```diff_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));
-       }        
+       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`の最大値を計算しようとしています。
実際に計算するコードは以下のようになります。

```java
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`関数を書き換えたものが以下のものになります。

```diff_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) {
+       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減算しないようにする。
という風にしています。

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

# 最終プログラム

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

```java: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`使えばもっと簡略化できるでしょ…
オーバーフロー・アンダーフロー時の値は不定ということにしておけば、

```java: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`型そのまま使えばいいんじゃね…と思ってみたり