- 概要
- 導入：オーバーフローの発生
- メモリの確保：int x; とはなんぞや
- 型が扱える値の範囲：int と long long の違い
- メモリの確保：数値が2進数として格納される
- 型が扱える値の範囲：int と long long の違い - 詳細
- C++ で整数型の最大・最小値を出力してみる
- オーバーフローとは？
- オーバーフローを意識しないといけない問題とそれに関連する記事
- 補足
- 終わりに
- 参考
- 更新履歴
競プロのコンテスト中にオーバーフロー（桁あふれ）によるWAに苦しんだのでその周辺知識をまとめました．
概要
内容はおおまかに以下のようになっています．
- 変数宣言によるメモリの確保
- 2進数の簡単な説明
- 数値がコンピュータ内部でどう表現されるのか（数値の内部表現）
- オーバーフローとは
記事中の使用言語は C++ です．記事の最後の方に，オーバーフローを知らないと理解できない競プロの問題やそれに関連する記事を少しだけまとめておいたので，時間がない方はそれだけでもご覧になってください．
導入：オーバーフローの発生
いきなりですが以下のコードをご覧ください．
#include <iostream> using namespace std; int main() { int x; long long y; x = 2147483647; y = 2147483647; cout << x << "\n"; cout << y << "\n"; x++; y++; cout << x << "\n"; cout << y << "\n"; return 0; }
出力結果
2147483647 2147483647 -2147483648 # なぜ214783648にならないのか？ 2147483648
インクリメントした int 型変数 x がなぜか負の値になっています．
以上のコード，出力結果を示した意図が分かる方は本記事の内容はあまり真新しいものではないと思います．分からない方はぜひ本記事をご覧ください．厳密な議論はできませんが，オーバーフローとはどういう現象でどんなときに起こるのかがイメージできるようになるはずです．
※以下，めんどいので敬語を略します．
メモリの確保：int x; とはなんぞや
まず，int x; にはどのような意味があるのかを見ていく．
C++ では，整数型の変数を定義したいときに int x; というコードを書く．基本中の基本である．
このコードの意味は，「今からメモリの一定幅の領域に x という名前をつけて管理するぞ」ということを宣言し，コンピュータに対してそうするように命令をしているのである．つまり，int x; と宣言することで，メモリ上に数値を格納できる場所を確保したわけである．このことをメモリの確保という．
型が扱える値の範囲：int と long long の違い
メモリの確保では「『一定幅の領域』に名前をつけて管理する」と述べたが，この幅を指定しているのが int x; の int という部分である．int が確保されるメモリ領域を指定しているのである．
int は変数の型を表し，int の他にshort，long longなどの整数を扱える型がある．それぞれの型の変数を宣言するには以下のように書けば良い．
int x; short y; long long z;
これらの違いは，宣言した時に確保されるメモリ領域の幅である．そして，それはその型が扱える値の範囲に直結している．
型の違い＝確保されるメモリ領域の幅の違い
以下，競プロで主に使用するであろう int型，long long 型を例に「型の違い」について解説していく．
確保するメモリ領域の幅が大きいほど格納できる値の範囲が大きくなることはなんとなくイメージできる．細かいことは抜きに，現段階では
int x;よりもlong long x;と変数の宣言をした方が x に大きな値を格納することができる（大きなメモリ領域を確保できる）
ということだけ理解していれば良い．目安としては，
int型：long long型：
あたりまで扱える（正確な値は後述）．繰り返すが，変数の型が違うと確保されるメモリ領域が異なる．
メモリの確保：数値が2進数として格納される
int と long long の違いは，確保されるメモリ領域が異なると述べた．次に，「数値が（確保した）メモリ領域にどのように格納されるか」を説明する．これを理解するために，まず，コンピュータ内部で数値がどう扱われるかを説明していく．
コンピュータ内部での数値の表現
コンピュータ内部では数値は 2 進数として扱われる．当然，我々が x = 8として代入した 8 という 10 進数も，コンピュータ内部では 2 進数として表現される．先述のメモリ領域の確保と関連づけて言うと，変数に数値（10 進数）を代入したとき，その数値はメモリ上に 2 進数として格納される．
変数への代入の際には，10 進数 -> 2 進数への変換は人間が意識しなくても良い（値を利用する際には 10 進数のことだけ考えておけば良い）が，「オーバーフロー」を考える際には重要である．
2 進数による 10 進数の表現について補足しておく．2 進数では，各桁を 0 か 1 の 2 通りで表現する（「2」種類の数字を使うから「2」進数）．
例えば，16 桁の 2 進数ならば，各桁が 2 通りの表現ができるため 通りの 10 進数を表現できる（2 × 2 × ... × 2（ 16 個）通り）．ここでなぜ 2 進数の話をしたかと言うと，変数宣言をしたときに確保されるメモリ領域と 2 進数が密接に関連しているからである．
メモリ領域の最小単位 bit と 10 進数
メモリ領域の確保が行われたとき，メモリ領域は特定の幅をもって確保されると述べてきたが，確保されるメモリの最小単位を「bit」という．メモリを確保するときは，「メモリ領域を 1 bit 確保した」，「2 bit 確保した」，... などと表現する．
1 bit のメモリ領域で 2 通りの数（0 or 1）を表現できるため，n bit のメモリ領域が確保された時には 通りの 10 進数を表現できる．
例えば，8 bit のメモリ領域を確保したとき（箱をイメージすると良い），各 bit に0 か 1 を格納すれば 通り，つまり，0 ~ 255（
）を扱える．このようにしてコンピュータ内部で 10 進数が扱えるようになっている．
以上より，「変数の型が異なると確保されるメモリ領域の幅が異なる」というのは，「変数の型が異なると確保されるメモリ領域の bit 数が異なる」と言い換えることができる．
n bit のメモリ領域を確保した時に，何通りの 10 進数（表現できる 10 進数の範囲）を表現できるかを以下に示した．
| 確保したメモリ領域 | 何通りの 10 進数？ | 10 進数の範囲 |
|---|---|---|
| 1 bit | |
0 ~ 1 |
| 2 bit | |
0 ~ 3 |
| 4 bit | |
0 ~ 15 |
| 8 bit | |
0 ~ 255 |
| 16 bit | |
0 ~ 65535 |
0 始まりのため，10 進数の最大値が ではなく，
となっているので注意．
（昔モバゲーのサークル？みたいなやつの定員が 65536 くらいだったのなんとなく印象に残ってたけどこういうことだったのか）
int 型変数のメモリ領域
以上を踏まえて，int 型の変数宣言によるメモリ領域の確保の流れをまとめる．int 型の宣言では 32 bit のメモリ領域が確保されるため，以下のような流れになる．
int x;と変数の宣言xという名前で 32 bit のメモリ領域を確保xには通りの数を代入できるようになる（
～
）
※負の値まで範囲が広がっていることに関しては後述．
このような手順で int 型変数に数値を格納できるようになる．メモリ領域の確保がどのようなものかイメージが湧いただろうか．ここまで理解できたところで，次節では再び int 型，long long 型の違いを説明する．
型が扱える値の範囲：int と long long の違い - 詳細
メモリ領域の確保の流れを踏まえて、もう一度 int x; と long long x; という変数宣言の違いを見ていく．
long long の方が扱える数の範囲が大きい（確保されるメモリ領域が大きい）と先述したが，具体的には，
int x;：32bitのメモリ領域を確保long long x;：64bitのメモリ領域を確保
となっている．つまり，「int と long long の違い」は，「確保されるメモリ領域が 32 bit か 64 bit かの違い」である．2 進数の数の表現は 2 のべき乗（）で表されるため，32 bit と 64 bit では扱える数の範囲に大きな違いが出ることには注意したい．
以上より，「変数の型が異なると扱える数の範囲が異なる」ということが理解できたであろう．ここで，C++ において扱える整数型と，それぞれの型が扱える整数の範囲をまとめておく．
C++：整数型一覧
主要な整数型の扱える数の範囲を表にまとめておく．感覚としてこれくらいの桁数というのを知っておくと良い．
AtCoder の問題の制約が，
となっているのを見たことがある競プロer の方は，この表の桁数をみるとテキトーな数を設定しているわけではないという出題者の意図が分かるだろう．
| 型の名前 | 占有サイズ（bit） | 占有サイズ（byte） | 値の範囲 | 桁数 |
|---|---|---|---|---|
| short | 16 bit (216) | 2 byte | -32,768 ~ 32,767 | 104 |
| unsigned short | 16 bit (216) | 2 byte | 0 ~ 65,536 | 104 |
| int | 32 bit (232) | 4 byte | -2,147,483,648 ～ 2,147,483,647 | 109 |
| unsigned int | 32 bit (232) | 4 byte | 0 ～ 4,294,967,295 | 109 |
| long | 32 bit (232) | 4 byte | -2,147,483,648 ～ 2,147,483,647 | 109 |
| unsigned long | 32 bit (232) | 4 byte | 0 ～ 4,294,967,295 | 109 |
| long long | 64 bit (264) | 8 byte | – 9,223,372,036,854,775,808 ～ 9,223,372,036,854,775,807 | 1018 |
| unsigned long long | 64 bit (264) | 8 byte | 0 ～ 18,446,744,073,709,551,615 | 1019 |
8 bit = 1 byte
詳しくは下記を参照。
※ signed と unsignedの違い（符号付き、符号無しの違い），int と long の違いについては本筋と少しずれてしまうので補足に参考リンクを貼っておいた．
C++ で整数型の最大・最小値を出力してみる
上で紹介した各型の最大値・最小値を出力してみる．型が扱える範囲は環境に依る（64 bit or 32 bit）が，そこに関しては考慮しない（勉強不足で分かっていない）．筆者の環境は
整数型に関するマクロが定義されている <climits> ヘッダをインクルードすると，各型の最大値・最小値の定数を使うことができる．例えば，int 型の最大・最小値はそれぞれ INT_MAX，INT_MIN として使用できる．それを用いて各型の最大値・最小値を出力してみる．
#include <iostream> #include <string> #include <climits> using namespace std; int main() { string str = "------------------------------\n"; // 整数型 integer cout << "integer type" << "\n"; cout << "\n"; // short cout << "short: " << SHRT_MIN << " ~ " << SHRT_MAX << "\n"; cout << "unsigned short: " << 0 << " ~ " << USHRT_MAX << "\n"; cout << str << "\n"; // int cout << "int: " << INT_MIN << " ~ " << INT_MAX << "\n"; cout << "unsigned int: " << 0 << " ~ " << UINT_MAX << "\n"; cout << str << "\n"; // long(64bit環境) cout << "long: " << LONG_MIN << " ~ " << LONG_MAX << "\n"; cout << "unsigned long: " << 0 << " ~ " << ULONG_MAX << "\n"; cout << str << "\n"; // long long(64bit環境) 処理系依存のサイズになる cout << "long long: " << LLONG_MIN << " ~ " << LLONG_MAX << "\n"; cout << "unsigned long: " << 0 << " ~ " << ULLONG_MAX << "\n"; cout << str + str << "\n"; // 実数型 float < double < long double cout << "real number type" << "\n"; cout << "\n"; cout << "float: " << UNDERFLOW << " ~ " << MAXFLOAT << "\n"; cout << "double(+-): " << "10^-308" << " ~ " << "10^+308" << "\n"; cout << "long double(+-): " << "10^-4932" << " ~ " << "10^+4932" <<"\n"; cout << str << "\n"; return 0; }
出力結果
integer type short: -32768 ~ 32767 unsigned short: 0 ~ 65535 ------------------------------ int: -2147483648 ~ 2147483647 unsigned int: 0 ~ 4294967295 ------------------------------ long: -9223372036854775808 ~ 9223372036854775807 unsigned long: 0 ~ 18446744073709551615 ------------------------------ long long: -9223372036854775808 ~ 9223372036854775807 unsigned long: 0 ~ 18446744073709551615 ------------------------------
オーバーフローとは？
最後に本記事の目的である「オーバーフロー」（桁あふれともいう）について説明する．簡単に言うと，オーバーフローとは，変数に格納できる数値の範囲を超えた値を格納しようとしたときに発生する現象のことである．
例えば，冒頭のコードでは，int 型が「 〜
」の範囲しか格納できないにも関わらずインクリメントを行い，
（格納できる最大値より 1 大きい値）を格納しようとしてオーバーフローが起きた．その結果として
ではなく
が出力された．なぜこのようなことが起こるのかを説明していく．
オーバーフローのイメージ
厳密な説明は次節に行うため，ここではイメージを捉える．オーバーフローのイメージとしては，カチカチするカウンターがピッタリである（数取器というらしい）．
上に示したカウンターは 4 桁のため，決して 10000 以上の数を表示できない．9999 の状態からカチカチして 10000 を入力しようとすると，最小の 0000 に戻ってしまう．5 桁目（一万の位）が「あふれて」しまったのである．心の中で 5 桁目が数えられる人がいるかもしれないが，他人から見たら 0000 にしか見えない．
これと同じ現象がコンピュータ内部で起きると考えれば分かりやすい．int 型では（最大の） までしか測れないのに，（最大より 1 大きい）
を測ろうとすると数値が最小値にリセットされてしまうというわけである．
オーバーフローが起こると計算結果が意図しないものになるため，大きな値を扱う際には気をつけなければならない．オーバーフローによるバグは意識していないとなかなか気づけないことがある（オーバーフローを知らずにWA連発した...）．
オーバーフローの実態
オーバーフローについてイメージが湧いたところで，int型の に 1 を足すとなぜ
になるかをメモリ領域の観点から説明する．
詳しくはこちらの記事の「桁あふれという現象」という節を見た方が分かりやすいと思うが，ざっと説明する．まず，オーバーフローの最たる例として，
確保したメモリ領域で表現できる最大値を格納した状態 1 を加算すると，最小値になる．また，最小値から 1 を減算すると最大値になる
が挙げられる．これは「確保したメモリ領域の幅」と「 2 進数」で説明できる．int 型の最大値の 10 進数表記，2 進数表記はそれぞれ，
- 10進数：
- 2進数：
（32桁、全てが1）
それに1を足した数は
- 10進数：
- 2進数：
（33桁、桁が繰り上がる）
となる．このとき、int 型は 32 bit のメモリ領域までしか確保できていないのに，メモリ領域が 33 bit 分必要な数値を格納しようとしている．変数の中身は，あくまでも確保（指定）されたメモリ領域の数値を参照する．そのため，1 を足した後の変数の中身は，あふれてしまった 33 桁目の「1」を無視した（33 bit 目に格納された 1 を無視した）， 32 桁分 の ，つまり
int型の最小値になってしまう．
この挙動から，int 型の変数に永遠に数を足していっても 〜
をぐるぐる回り続けることが容易に分かる．格納できる数値の範囲は複雑だが，原理はカチカチカウンターと同じである．
※ 桁あふれした時の、あふれた分のメモリの挙動（メモリリークが起きるのかどうか）が分からないため、どなたかコメントをいただけるとありがたいです．
オーバーフローを意識しないといけない問題とそれに関連する記事
最後に，競プロでオーバーフローを意識しないといけない問題，オーバーフローに関する記事を列挙しておく．難易度順ではないのと，灰色コーダーがお勧めする問題なので初学者用だと思う．
No.9008 空白区切りで与えられる数値データの合計値を求める（yukicoderより）
この記事を見た後にまず解いてみてほしい問題．競プロで，整数型のオーバーフローを気をつけなければいけない一番簡単な問題．ABC055 B - Training Camp
計算過程でのオーバーフローをどのように防ぐのかという基本的な問題．ABC059 B - Comparison
整数型で扱えない桁数の値の大小をどうやって比較するという問題．（これはオーバーフロー抜きにしても良い問題だった）DDCC2018 C問題：チップ・ストーリー ～白銀編～
mod によって桁あふれを防いで正確な答えを導き出そうという問題．競プロでは「1000000007」という数字は常識みたいだが，この問題で初めて知った．私にとってはとても難しい問題でした．「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜
けんちょんさんが「1000000007」という数字が何なのかを優しく解説してくれているとても親切な記事．
補足
int と longは何が違う？
筆者が後で見直す用．int はシステム標準だけど，long は環境依存で桁数が変わるから気をつけないといけないということだろうか．
signedとunsigned
本記事の内容が理解できた方にはそんなに難しい話ではない．それぞれ，
signed：「符号付き」の意味で、負の範囲を含むunsigned：「符号なし」の意味で正の範囲（0以上）のみを含む
を表し，扱える数の範囲が異なるよということ．
- 表現できる数値の場合の数（ややこしい言い回しでごめんなさい）
は同じだが，
- 表現できる数値の範囲（種類）
は異なる．signed は基本省略され，int は signed int を表す．
| 型 | 表現できる数値の範囲 |
|---|---|
| (signed) int | -2147483648 ~ 2147483647 |
| unsigned int | 0 ~ 4294967295 |
どちらも 通りの数を表せるが，その範囲が異なる．これは，2 進数の先頭の桁の数を符号として扱うか数として扱うかという違いである．
終わりに
本記事では，オーバーフローについてまとめてみました．灰色コーダーが何を偉そうに感は否めないですが，温かい目でおっさんの戯言を見守っていただけるとありがたいです．
ただなんとなく int x; というコードを書いていたことにどんな意味があったのか，オーバーフローとは何なのかについて理解するための一助となれば幸いです．今回記事を書いたことによって自分も少しだけメモリの確保をしなければいけない意味が分かってきたので引き続き勉強していきます．
また，競プロの問題を解く時に，
1,000,000,007で割った余りを計算しろ
と明示的に書いてある時は気づけますが，int 型で扱える範囲のギリギリを責めるような問題の時には計算過程でオーバーフローが起きるのか意識した方が良さそうです．この記事を書いたからには簡単なオーバーフローで WA 食らわないよう気をつけていきます．
最後まで読んでくださり本当にありがとうございました．間違い・ご指摘等あればコメント・Twitterのリプでお願い致します．
参考
データ型の範囲(2016/6) Microsoftのデータ型の範囲についての公式ページ
- 数値の扱いに関する諸問題(2004 - 2014)
更新履歴
- 2018/11/30 投稿（灰色，rate: 336）
- 2019/06/09 ちょっと編集した（緑色，rate: 903）
- 時間があったら図を作りたい...
