数値型とオーバーフロー

読了目安 約3分

Int は 64 ビット。オーバーフローはクラッシュで気付ける。Double の誤差は整数の計算で避ける。

競技プログラミングでは、答えが 10^18 になる問題が珍しくありません。 数値型が「どこまで表せるか」を知らないと、原因の見えないバグに悩まされます。

Int は 64 ビット

Swift の Int は 64 ビットの整数です。 約 ±9.2×10^18 まで表せます。

print(Int.max)
print(Int.min)

C++ の int は 32 ビットで、約 ±2.1×10^9 しか表せません。 C++ で 64 ビットの long long と書き分ける範囲を、Swift は Int だけでカバーします。

オーバーフロー

オーバーフローは、計算結果が型の表せる範囲を超えることです。 Swift では、オーバーフローした瞬間に実行時エラーで止まります。

let a = Int(readLine()!)!
print(a * a)

4000000000

4×10^9 の 2 乗は 1.6×10^19 で、Int.max を超えるため止まります。 試してみよう: 入力を 3000000000 に変えると、9×10^18 で範囲に収まり出力されます。

C++ のオーバーフローは未定義動作で、壊れた値のまま黙って進むことがあります。 Swift は必ずその場で止まるので、バグに早く気付けます。

答えが範囲に収まる問題でも、途中の掛け算で溢れることがあります。 たとえば a × b ÷ c は、答えが小さくても a × b の時点で止まりえます。 制約から途中経過の最大値を見積もる癖をつけてください。

あえて溢れさせて計算を続ける演算子 &+ &- &* もあります。 ハッシュ値の計算などに使う道具で、競プロで必要になる場面はほぼありません。

Double の誤差

小数を扱う Double は、値を 2 進数の近似で持ちます。 そのため、簡単な計算にも誤差が入り込みます。

print(0.1 + 0.2)
print(0.1 + 0.2 == 0.3)

小数の == 比較は当てにならないと覚えてください。

整数で計算する定石

誤差を避ける定石は、小数を最小単位の整数に置き換えることです。 1.1 を 10 回足す計算で比べます。

var total = 0.0
for _ in 0..<10 {
    total += 1.1
}
print(total)
print(total == 11.0)

11 になるはずが、誤差でずれました。 「0.1 が 11 個」と数え直せば、整数だけで正確に計算できます。

var total = 0
for _ in 0..<10 {
    total += 11  // 1.1 を「0.1 が 11 個」と数える
}
print(total)  // 0.1 が 110 個、つまり 11 ちょうど
print(total == 110)

学びどころ

演習

整数 A と B が 1 行に空白区切りで入力されます。 A × B を出力してください。

制約: 1 ≤ A, B ≤ 10^9

答えは最大 10^18 です。 32 ビットの整数では溢れますが、Swift の Int なら収まります。

入力例:
3 5

出力例:
15

let parts = readLine()!.split(separator: " ").map { Int($0)! }
print(parts[0] * parts[1])