試行錯誤ダイアリー

新卒エンジニアが日々の技術的な学び,働き方,日々感じたこと等を書きます

オーバーフローと補数表現

「なぜ,オーバーフローは起こるのか?」
「表示範囲の最大値と最小値の絶対値が違うのはなぜ?」
と質問されたことがあって,補数表現を含めて改めて確認してみた.

オーバーフローとは

コンピュータの演算において数値型が表現可能な値の上限を超えること、およびそれによって発生したエラー。「桁あふれ」とも言う

参考:Wikipedia-オーバーフロー

計算機では型によって数値の桁数が決まっているので,その表現可能な値の範囲を超えたときに起こる問題ということですね.

具体的に,Javaのint型では符号付き4バイトで,その値の範囲は-2147483648〜2147483647になります.

実際に Javaのコードで確認してみると,

public class Test{
    public static void main(String[] args) {
        int int_max;
        int val;
        int_max = 2147483647;//intの最大値
        val = 1;//1

        System.out.println("int_max : "+String.valueOf(int_max));
        System.out.println("val : "+String.valueOf(val));

     //intの最大値に1を加算
        System.out.println("int_max + val : " + String.valueOf(int_max + val));

        /*出力
        int_max : 2147483647
        val : 1
        int_max + val : -2147483648
        */
    }
}

この例ではint型の最大値である「2147483647」に「1」を足すと本来なら「2147483648」になるはずなのに「-2147483648」になってしまっています.

このように負の数になってしまう理由は,計算機内で数値が2進数で表現されていて,2の補数(真補数)を用いて負の数を表しているためです. 負の数を2の補数で表現することで,減算を負数の加算として扱うことができるため,減算器を用意する必要がなく回路が単純化されるというメリットがあります.

補数とは

補数は「ある数」の「負」の表現方法で,正確には「真補数(2の補数)」と「擬補数(1の補数)」があるのですが,ここでは実際に計算機内で使用されている「真補数」について説明します.
※正確には基数という概念が存在しますが,今回は基数が2であると仮定して話を進めます.基数とは2進数における2のことで,10進数だと基数は10です.

2進数のある数をX(n桁)と真補数Yの関係は次のように定義されます.

{
\begin{equation}
X + Y = 2^{n}
\end{equation}
}

つまり真補数Yは

{
\begin{equation}
Y = 2^{n} - X
\end{equation}
}

になります.

2の補数を求めてみる

実際の数値で補数を求めてみる.今回は単純化するために4ビットの2進数で確認します.

4ビットの2進数で

{
\begin{equation}10_{(10)}\end{equation}
}

を表現すると,
{\begin{equation}1010_{(2)}\end{equation}}

になります.

{\begin{equation}1010_{(2)}\end{equation}}における{\begin{equation}(2)\end{equation}}は2進数表現であることを示します.

4桁なので上の定義に従うと

{\begin{equation}Y = 2^{4} - 1010_{(2)}\end{equation}}
{\begin{equation} Y = 10000_{(2)} \end{equation}}-{\begin{equation} 1010_{(2)} \end{equation}}
{\begin{equation}Y = 0110_{(2)}\end{equation}}
{\begin{equation}
2^{4} = 16_{(10)} = 10000_{(2)}
\end{equation}}

となり,10の補数は2進数で「0110」で表せることがわかります.

簡単な求め方として,ある数(ここでは10)の2進数表現をビット反転して1を加算すると簡単に求まります.

符号付き表現

数値型では最上位ビット(Most Significant Digit:MSD)で符号を決定しています. 最上位ビットが1であれば「マイナス」,0であれば「プラス」になります.

例えば4ビットで10進数の−2を2の補数表現を使って表現すると,「1110」になります.

最小値である-8についても,−8は8の2の補数表現に(Y)になるので

{
\begin{equation}
Y = 2^{4} - 1000_{(2)}
\\\\
Y = 10000_{(2)} - 1000_{(2)}
\\\\
Y = 1000_{(2)}
\end{equation}
}

となり,「−8」は{\begin{equation}1000_{(2)}\end{equation}}と表せることがわかります

4ビットの2の補数表現の対応表は以下のようになります.

4ビットのビット列 2の補数表現
0000 +0
0001 +1
0010 +2
0011 +3
0100 +4
0101 +5
0110 +6
0111 +7
1000 -8
1001 -7
1010 -6
1011 -5
1100 -4
1101 -3
1110 -2
1111 -1

正しい表現になっているかはわかりませんが,
この関係性は2進数におけるゼロである0000を中心として数直線上で理解できそうです.

f:id:appli-in:20180709032506p:plain:w600

この図では10進数の6である

{\begin{equation}0110_{(2)}\end{equation}}

{\begin{equation}0000_{(2)}\end{equation}}

に足しても

{\begin{equation}0110_{(2)}\end{equation}}
ですが,

−6を表現したいときには,0である

{\begin{equation}(1)0000_{(2)} \end{equation}}

から6である

{\begin{equation}0110_{(2)}\end{equation}}
を引くことで感覚的に理解できそうです.

※(1)0000の1を括弧で囲っているのは4桁の表現なので実際は5桁目は無いように見えるためこのような表現にしています.

これらのことを一般化すると 表現のビット数を{
\begin{equation}
N
\end{equation}
}としてintの表現範囲を{
\begin{equation}
Range
\end{equation}
}とすると

{
\begin{equation}
- 2^{N-1} \sim Range \sim 2^{N-1}-1
\end{equation}
}

となり,

実際に,4桁の場合の範囲は

{
\begin{equation}
-8 \sim Range \sim 7
\end{equation}
}

で,

{
\begin{equation}
- 2^{(4-1)} \sim Range \sim 2^{(4-1)}-1
\end{equation}
}

となり成り立つことがわかります.

ここで改めてオーバーフローが起こる仕組みについて考えてみると, int型は4バイトつまり32ビットで表現できる数値で,最上位桁が符号を表すので,最上位桁を除くビットが全て1である,

{
\begin{equation}
01111111111111111111111111111111_{(2)} = 2147483647_{(10)}
\end{equation}
}

が最大値になります.

これに1を足すと

{
\begin{equation}
10000000000000000000000000000000_{(2)} = - 2147483648_{(10)}
\end{equation}
}

となってしまうためオーバーフローが起こります.

まとめ

オーバーフローが起こる仕組みについて,実際に起こることを確かめ,次に,計算機上の負の数の表現である2の補数表現を例を追って理解しながら説明しました,符号付き表現の範囲を一般化することで任意の桁数のときの表現範囲についても理解できたと思います.

最後に,オーバーフローが実際にどのように起っているかを具体的なビット列や数値と共に確かめることで,理解できたかなと思います.

他にも1の補数(擬補数),符号付き絶対値表現などの表現ができます.実際は表現範囲が2の補数のほうが大きいので使われていることはないと思いますが,気になった方は調べてみてください.