二分探索で探索範囲の中間点を求めるとき、

int m = low + (high - low) / 2;

と書くことがよくある。
これは、low および high がともに大きい値のときに

int m = (low + high) / 2;

を用いた際に起こるオーバーフローが回避できるためである。

しかし、最初の形式でも、low および high の値によってはオーバーフローが起こることがある。

オーバーフローを起こすケース

以下のプログラムを考えてみよう。
これは、32 ビット符号付き整数のほぼ全範囲を対象に、ある条件 (この条件は、ある整数以上では常に成り立ち、その整数未満では決して成り立たない) が成り立つ最小の値を求めようとしたプログラムである。

オーバーフローにより上手く動かないプログラム

#include <stdio.h>

int judge(int query) {
    return query >= 2929831;
}

int main(void) {
    int no = -2020202020, yes = 2020202020;
    while (no + 1 < yes) {
        int m = no + (yes - no) / 2;
        if (judge(m)) yes = m; else no = m;
    }
    printf("%d\n", yes);
    return 0;
}

しかし、このプログラムは処理が終了しない可能性がある。
デバッグ用に、探索範囲を出力し、ループを一定回数で打ち切るようにしてみよう。

オーバーフローにより上手く動かないプログラム (デバッグ版)

#include <stdio.h>

int judge(int query) {
    return query >= 2929831;
}

int main(void) {
    int no = -2020202020, yes = 2020202020;
    int limit = 40;
    while (limit-- > 0 && no + 1 < yes) {
        int m = no + (yes - no) / 2;
        printf("no = %d, yes = %d, m = %d\n", no, yes, m);
        if (judge(m)) yes = m; else no = m;
    }
    printf("%d\n", yes);
    return 0;
}

すると、ある環境では、以下の実行結果が得られた。
本来狭まっていくはずの探索範囲が、むしろ広がってしまっている。

実行結果例

no = -2020202020, yes = 2020202020, m = -2147483648
no = -2147483648, yes = 2020202020, m = 2083842834
no = -2147483648, yes = 2083842834, m = 2115663241
no = -2147483648, yes = 2115663241, m = 2131573445
no = -2147483648, yes = 2131573445, m = 2139528547
no = -2147483648, yes = 2139528547, m = 2143506098
no = -2147483648, yes = 2143506098, m = 2145494873
no = -2147483648, yes = 2145494873, m = 2146489261
no = -2147483648, yes = 2146489261, m = 2146986455
no = -2147483648, yes = 2146986455, m = 2147235052
no = -2147483648, yes = 2147235052, m = 2147359350
no = -2147483648, yes = 2147359350, m = 2147421499
no = -2147483648, yes = 2147421499, m = 2147452574
no = -2147483648, yes = 2147452574, m = 2147468111
no = -2147483648, yes = 2147468111, m = 2147475880
no = -2147483648, yes = 2147475880, m = 2147479764
no = -2147483648, yes = 2147479764, m = 2147481706
no = -2147483648, yes = 2147481706, m = 2147482677
no = -2147483648, yes = 2147482677, m = 2147483163
no = -2147483648, yes = 2147483163, m = 2147483406
no = -2147483648, yes = 2147483406, m = 2147483527
no = -2147483648, yes = 2147483527, m = 2147483588
no = -2147483648, yes = 2147483588, m = 2147483618
no = -2147483648, yes = 2147483618, m = 2147483633
no = -2147483648, yes = 2147483633, m = 2147483641
no = -2147483648, yes = 2147483641, m = 2147483645
no = -2147483648, yes = 2147483645, m = 2147483647
no = -2147483648, yes = 2147483647, m = -2147483648
no = -2147483648, yes = 2147483647, m = -2147483648
no = -2147483648, yes = 2147483647, m = -2147483648
no = -2147483648, yes = 2147483647, m = -2147483648
no = -2147483648, yes = 2147483647, m = -2147483648
no = -2147483648, yes = 2147483647, m = -2147483648
no = -2147483648, yes = 2147483647, m = -2147483648
no = -2147483648, yes = 2147483647, m = -2147483648
no = -2147483648, yes = 2147483647, m = -2147483648
no = -2147483648, yes = 2147483647, m = -2147483648
no = -2147483648, yes = 2147483647, m = -2147483648
no = -2147483648, yes = 2147483647, m = -2147483648
no = -2147483648, yes = 2147483647, m = -2147483648
2147483647

これは、int が 32 ビットのとき、

int no = -2020202020, yes = 2020202020;

を用いた yes - no の計算がオーバーフローしてしまうためである。
このとき、yes - no の値は 4,040,404,040 となり、32 ビット符号付き整数の最大値 2,147,483,647 を超えてしまうのである。

C言語では、符号付き整数の計算におけるオーバーフローは未定義動作となり、任意の結果を生む可能性がある。

オーバーフローの回避方法

より扱える範囲が広い型を用いる

今回の問題は、探索範囲の幅が広すぎたために int 型ではオーバーフローしてしまったことである。
そのため、一時的により扱える範囲が広い long long 型を用いて計算を行うことで、オーバーフローを回避できる。
適切に計算を行えば、int 型に収まる探索範囲の中間地点も int 型に収まるはずである。

中間計算に long long 型を用いたプログラム

#include <stdio.h>

int judge(int query) {
    return query >= 2929831;
}

int main(void) {
    int no = -2020202020, yes = 2020202020;
    while (no + 1 < yes) {
        int m = no + ((long long)yes - no) / 2;
        if (judge(m)) yes = m; else no = m;
    }
    printf("%d\n", yes);
    return 0;
}

キャストを用いて中間地点の計算を long long 型で行うようにしたことで、意図通り動作するようになった。

下駄を履かせて符号なし整数型で計算する

今回の場合、符号つき整数で探索範囲の差を計算するとオーバーフローしてしまったが、同じ幅の探索範囲でも、符号なし整数ならオーバーフローを回避できる。
そのため、適当な値を足して符号なし整数にしてから中間地点を求め、符号つき整数に戻すことで、オーバーフローを回避できる。

中間計算に符号なし整数型を用いたプログラム

#include <stdio.h>

#define OFFSET 0x80000000u

int judge(int query) {
    return query >= 2929831;
}

int main(void) {
    int no = -2020202020, yes = 2020202020;
    while (no + 1 < yes) {
        unsigned int mu = no + OFFSET + ((yes + OFFSET) - (no + OFFSET)) / 2;
        int m = mu >= OFFSET ? (int)(mu - OFFSET) : -(int)(OFFSET - mu);
        if (judge(m)) yes = m; else no = m;
    }
    printf("%d\n", yes);
    return 0;
}

意図通りの動作にはなったが、long long 型へのキャスト一発での改善よりも複雑なコードになってしまった。

符号つき整数に戻す処理を

int m = mu - OFFSET;

としても動くかもしれないが、変換先の範囲外の値の符号なし整数から符号つき整数への変換は処理系定義であり、確実ではない。

どの方法がよいか？

前述の

オーバーフローにより上手く動かないプログラム
中間計算に long long 型を用いたプログラム
中間計算に符号なし整数型を用いたプログラム

をそれぞれ Compiler Explorer でコンパイルし、中間地点を計算する部分のコンパイル結果を見てみた。
コンパイラは x86-64 gcc 15.2、コンパイルオプションは -O2 を用いた。
結果は以下のようになった。

オーバーフローにより上手く動かないプログラムの中間地点計算

        movl    %esi, %eax
        subl    %edx, %eax
        sarl    %eax
        addl    %edx, %eax

中間計算に long long 型を用いたプログラムの中間地点計算

        movslq  %esi, %rdx
        subq    %r8, %rdx
        movq    %rdx, %rax
        shrq    $63, %rax
        addq    %rdx, %rax
        sarq    %rax
        addl    %ecx, %eax

中間計算に符号なし整数型を用いたプログラムの中間地点計算

        movl    %esi, %eax
        subl    %edx, %eax
        shrl    %eax
        addl    %edx, %eax

long long 型を用いる処理はソースコードの見た目はスッキリしていたが、コンパイル結果は値を 64 ビットに変換する処理が入り、長くなってしまった。
一方、符号なし整数型を用いる処理はソースコードが煩雑になった一方、コンパイル結果は必要十分で美しい。

処理速度やバイナリサイズの細かな差があまり重要でない場合は、long long 型を用いるのがよいだろう。
一方、処理速度を少しでも速くしたく、かつコンパイラの最適化能力を十分信頼できる場合は、符号なし整数型を用いるのがよいだろう。

そもそも対策をしなくてもオーバーフローしない探索範囲 (0 ～ 2020202020 など) のみを扱う場合は、対策なし (オーバーフローにより上手く動かないプログラム) がソースコードの見た目・コンパイル結果ともに優れ、よさそうだ。

まとめ

中間地点を求める際に「low と high がともに大きいとき」のオーバーフローを回避するための形式

int m = low + (high - low) / 2;

は、low と high の差が大きいとき、オーバーフローを起こしてしまう。
このオーバーフローは、探索範囲の差を求める際により表現できる正の値の上限が大きい符号なし整数型や long long を用いることで、回避できる。