６４ビット整数のオーバーフロー判定についてのメモ

こんにちは。

去年の暮れに『素数をつないで落ちつくんだ〜簡単！素因数分解で「京」を目指せ』という iOS/Android アプリをリリースしたのですが、その際、64ビット整数 (long型) 同士の掛け算の結果がオーバーフローしているかどうかの判定をする必要がありました。

これが思ったより悩ましかったので、その時の調べたり試したことをまとめてみました。

オーバーフローとは？

Wikipedia によると以下のような現象のことです。

デジタルコンピュータにおいて、演算結果がレジスタの表せる範囲や記憶装置上の格納域に記録できる範囲を超えてしまう現象、またはその結果レジスタ等に格納される値を意味する。オーバーフローは、本来演算結果を格納する場所とは違う場所に格納される場合がある。「溢れ」とも言う。 (算術オーバーフロー – Wikipedia)

要は計算の結果が大きすぎて、エラーになってしまった状態です。ゲーム内の得点の計算などでこれが発生すると、せっかくの記録が台無しになってしまうので、大問題です。

以下では、このオーバーフローの防ぎ方を考えていきます。なお、ここでは符号つき整数の場合を考えます。

加算（＋）の場合

整数 a と整数 b の足し算の結果（和）がオーバーフローしていないかの判定を考えます。ここで、正の64ビット整数の最大値を LONG_MAX とし、a も b も正の値だとします。

I. 処理系依存の方法

これはC言語として保証されていない（と思う）方法ですが、符号付き整数がオーバーフローしてその最大値 LONG_MAX (9223372036854775807) を1超えると、逆に最小値 LONG_MIN（-9223372036854775808）になってしまう処理系がほとんどです。それを利用して「加算の結果が負になったらオーバーフローだった」と判定します。実用的にはこれでいいんじゃないですかね。

うちでは動作する加算オーバーフロー判定

II. 正攻法

処理系に依存しない方法を考えます。
a と b の和が LONG_MAX を超えるには、少なくとも a か b のどちらか一方が LONG_MAX/2 以上である必要があるので、

(1) a と b どちらも LONG_MAX/2 未満の場合、オーバーフローはしない

(2) a のみが LONG_MAX/2 以上の場合、a – LONG_MAX/2 + b がLONG_MAX/2 以上の場合、オーバーフローする

     b のみが LONG_MAX/2 以上の場合、b – LONG_MAX/2 + a が LONG_MAX/2 以上の場合、オーバーフローする

(3) a と b どちらも LONG_MAX/2 以上の場合、オーバーフローする

LONG_MAX は実際には奇数ですので、計算の際はそれを意識してコードを書く必要があるかもしれません。

処理系にほとんど依存しない加算オーバーフロー判定

[2017.03.02 追記]
上記のような方法を取らざるを得ないと思っていたのですが、コメント欄にご指摘をいただきました。

確かに a < LONG_MAX – b の判定ならオーバーフローを起こさずに可能ですので、a + b がオーバーフローするかどうか計算前に検知することができます。今後はこの方法でやろうと思います。(^^;

III. ハードウェア情報を読み取る

そもそもC言語などの高級言語ではオーバーフローと呼ばれる現象は、機械語（アセンブリ言語）の世界では単なるキャリーフラグを伴った加算なので、キャリーフラグを読み取ればオーバーフローしたかどうか判定できます。しかしこの方法は完全な処理系依存になってしまうので、ここでは扱いません。

乗算（×）の場合

本記事を書こうと思ったきっかけになったケースです。整数 a と整数 b の掛け算の結果（積）がオーバーフローしたかどうかの判定を考えます。

I. 処理系依存の方法

上述の加算の場合、LONG_MAX を超えると負の値になりました。乗算の場合も、積が LONG_MAX を超えたら負の値になってくれるような期待をしていた時期が自分にもありました。
しかし実験の結果、

@y_sakaki
これを御覧ください pic.twitter.com/U1VcqkARu0

— TOME＠アルバイト (@shinhirota) 2016年12月11日

なんと、結果は正になったり負になったりで、オーバーフロー判定には使えないようでした。

仕方ないのでいろいろ考えたのですが、掛け算した結果を a で割って b と等しくなれば計算できている（オーバーフローしていない）と判定してみることにしました。

うちでは動く乗算オーバーフロー判定

いくつかのケースを試しましたが、正しく判定できたので、実装もシンプルなので上記のアプリはこの方法でオーバーフロー判定してます。

この方法（実装は Unity なので C#ですが）で、正しく64ビット整数の最大値 922京3372兆368億5477万5807 のカウンターストップが達成されたスクリーンショットがこちらw。（あいしさん、ここまでプレイしていただいてありがとうございます）

落ちついて9223372036854775807点 #素数をつないで落ちつくんだ https://t.co/R9Qj8PsgAQ pic.twitter.com/RqHytPq5Go

— あいし (@IC_9) 2016年12月11日

64ビット整数の最大値でちゃんと止まってます

II. 正攻法

乗算の処理系に依存しない判定方法が難しい。
加算の時と同じように考えると、以下のようになると思います。

a と b の積が LONG_MAX を超えるには、少なくとも a か b のどちらか一方が √LONG_MAX 以上である必要があるので、

(1) a と b どちらも √LONG_MAX 未満の場合、オーバーフローはしない

(2) a のみが √LONG_MAX 以上の場合、a ÷ √LONG_MAX × b が　√LONG_MAX 以上の場合、オーバーフローする

     b のみが √LONG_MAX 以上の場合、b ÷ √LONG_MAX × a が　√LONG_MAX 以上の場合、オーバーフローする

(3) a と b どちらも √LONG_MAX 以上の場合、オーバーフローする

しかしこのロジックをコンピューター上で正確に実行するのは困難です。なぜなら(2)の計算の途中に小数が入り込み、誤差が生じる余地があるからです。というわけで、積の正攻法判定はとりあえずあきらめました。

どなたか良い方法があれば教えてください…。(–;

[2017.03.02 追記]
コメント欄に良い方法をいただいてしまいました。

 「a < LONG_MAX / b が成り立つ場合、a * b はオーバーフローしない」と判断できそうです。今後はこの方法でやろうと思います。(^^;

減算（ー）、除算（÷）の場合は？

a も b も正の値だとすると、減算で（符号の逆転はあるにせよ）オーバーフローするケースはありません。

また除算でも（切り捨て誤差が発生するにせよ）オーバーフローするケースはありません。

まとめ

• 64ビット整数演算のオーバーフロー判定は、処理系依存のコードであれば上記のような簡単な方法で記述できる。実用上はそんなに問題ないはず。
• 符号付き64ビット整数の乗算オーバーフロー時、答えが負の数になると思ってはいけない。
• とりあえず「積を元の数で割ってみて元に戻るか」で判定してみた iOS/Android アプリをリリースしていますが、今の所NGケースは見つかっていません。
• [2017.03.02 追記] 乗算の判定に関してコメント欄で「a < LONG_MAX / b が成り立つ場合、a * b はオーバーフローしない」というやり方を教えていただきました。このやり方のほうが、環境依存しないという意味で、よさそうですのでお勧めいたします。(^^;