【初心者向け】2の補数表現と桁溢れ（オーバーフロー）

zuka

こんにちは。zuka（@beginaid）です。

この記事では自分がJavaを復習した際につまずいたポイントをまとめていきます。今回は，Javaにおける2の補数表現と桁溢れ（オーバーフロー）に関してです。

なお，本記事では分かりやすさを優先するため，用語を正確に使わない部分や理解が曖昧な部分を残すことがあります。予めご了承ください。間違いがございましたら，お問い合わせフォームまたは最下部コメント欄よりご指摘いただけますと助かります。

背景

以下の出力に疑問を持ったことがキッカケでした。

public class Main {
	public static void main(String[] args) {
	    int x = 128; // 128を変数宣言
	    System.out.println((byte) x); // 128をbyte型にキャストして表示 -> -128と表示される 
	}
}

int型で宣言された変数xをbyte型にキャストして表示したところ，-128と表示されました。こちらの理由を簡単にお伝えしていきます。

結論

128は2進数で表すと1000 0000です。これは8bitの2の補数表現で-128を表します。したがって，32bitのデータ型であるintを8bitのデータ型であるbyteにキャストすると，桁溢れ（オーバーフロー）が発生して-128が表示されます。

説明

以下では，最初に2の補数表現について説明し，その後に結論を裏付ける説明をしていきたいと思います。

数値型の表現範囲

int型は$[-2^{31}$〜$2^{31}-1]$の整数を表すことができますが，byte型は$[-2^{7}$〜$2^{7}-1]$，つまり$[-128$〜$127]$の整数しか表すことができません。せっかくなので，ここら辺の背景をもう少し詳しく説明していきます。

安直に考えると，8bitで表すことのできる最大の整数は1111 1111で255になりそうですよね。しかし，多くのプログラミング言語では整数を2の補数表現で表しています。どういうことかというと，最上位ビットを「符号を表すbit」と定めてしまいます。後述しますが，こうすることで負の数も8bitの範疇で扱うことができるようになります。

すると，残りの7bitで絶対値を定めるしかありません。7bitで表すことのできる最大の整数は127ですので，8bitの2の補数表現で表すことのできる最大の整数は127になります。このとき，8bitの2の補数表現で表すことのできる最小の整数は，127にマイナスを付けた-127になりそうですが，実は-128になります。ここを理解するためには，2の補数表現の定義を知っておく必要があります。

$2^k$補数表現

本記事では，$k$bitの$n$の補数表現を特に「$n^k$補数表現」と表すことにします。$n^k$補数表現の定義は以下のようになります。

$x_{(10)} \in [0, n^{k-1}-1]$に対する$n^k$補数表現は$n^{k}_{(10)}-x_{(10)}$である。

この定義を少し言い換えると，巷でよく言われている「$x$に足して$n$進数表示の$k$bit目（最上位bit）で桁上がりが発生する最小の数」という補数（complement）の定義になります。

$x$の最大値が$n^{k-1}-1$であるのは，最上位bitを符号を表すbitとして保存するため，数値は残りのk-1bitで絶対値を表現するしかないからです。ちなみに，$n=2$，つまり2進数の場合は最上位bitが0の場合は正，1の場合は負を表せるため，理にかなっています。

$n$と$k$について少し補足しておきましょう。$n$の値は何進数かを表し，$k$はどの程度まで大きな値を保持するかを決定するbit数を表します。通常，コンピュータ内では$n=2$を扱うことが多く，補数表現の話題も$n=2$を前提として語られる場合が多いです。

例えば，$n=2$，$k=4$のとき，$0011_{(2)}=3_{(10)}$の$2^4$補数表現は$16-3=13_{(10)}$です。つまり，$2^4$補数表現の世界では，$-3$を表したいときは$13$を使うということです。

同様に，$n=10$，$k=2$のとき，$37_{(10)}$の$10^2$補数表現は$100 - 37 = 63_{(10)}$です。つまり，$10^2$補数表現の世界では$-37$を表したいときは$63$を使うということです。

境界値について

先ほどの定義から，0の$n^k$補数表現は$n^{k}$になります。$n=2$，$k=8$のときを考えると，0の$2^8$補数表現は-128になります。ここが，8bitの2の補数表現の最小値が-128，最大値が127になる理由です。0は正と負の境目であることから，kbitを等分することはできず，はみ出した分がマイナス側に分配されたというイメージです。

賢明な読者の皆様であれば，0の$n^k$補数表現をプラス側に分配しても良いのではないかという疑問を持たれる方もいらっしゃると思います。ここに関しては，特に2進数の場合を考えれば分かりやすいです。0の$n^k$補数表現である$n^{k}$の最上位bitが1であることから，表現したい数値は負の数ですので，分配先としてはマイナス側が適しているのです。

補数表現の意義

先ほどのような定義をすることで，mod nの世界で減算を加算として扱えるという利点があります。例えば，先ほどの3の$2^4$補数表現を利用して「$11-3$」を計算したいとします。このとき，

となり，たしかに「$11-3=8$」を加算のみで求めることができました。同様に，37の$10^2$補数表現を利用して$84 - 37$を計算したいとします。このとき，

となり，たしかに$84-37=47$を加算のみで求めることができました。

結論再び

再び冒頭のコードに立ち返ってみましょう。

public class Main {
	public static void main(String[] args) {
	    int x = 128; // 128を変数宣言
	    System.out.println((byte) x); // 128をbyte型にキャストして表示 -> -128と表示される 
	}
}

最初に32bitのint型でx=128を定義していました。これは2進数表示で0...0 1000 0000になりますね。こいつを無理やり8bitのbyte型にキャストすると，2進数表示で1000 0000になります。最上位bitに注目すると，1となっているので負の数を表していることが分かります。さらに，下位7bitに注目すると，0を表していることが分かります。0の$2^8$補数表現は$2^8$ですので，結局xは-128と表示されてしまったのです。

この現象が，いわゆる桁溢れとかオーバーフローとか言われています。