たつをの日記 - 1999年12月5日

オーバーフローと戦う

SUFARYでは、 とてつもなく巨大な配列を二分探索する必要があるのだが、 これまでオーバーフローについては何も考慮していなかった。 二分探索の部分を簡略化するとこんな感じである。

while (left <= right) {   /* left も right も INT 型 */
	INT middle = (left + right) / 2;
	if (x[middle] < target)
		left = middle + 1;
	else if (x[middle] == target)
		return middle;
	else
		right = middle - 1;
}

2行目で領域の中心を計算するとき left + right がオーバーフローする可能性が かなりあるのだ。 以下のように単純に unsigned にキャストすれば済みそうなものだが、 この場合、INT は signed とは限らないのでダメである。

	middle = ((unsigned INT)left + (unsigned INT)right) / 2;

そこで、ちょっと処理は複雑になるが以下のようにしてみた。

	if ((left & 1) == 1 && (right & 1) == 1)
		middle = left / 2 + right / 2 + 1;
	else
		middle = left / 2 + right / 2;

一般にはこういうときどのようなコードを書くのだろうか。 一昔前のビット数の少ないコンピュータでは頻出した問題だと思うのだが、 関連文書か何かどなたかご存知ありませんか？ また、「もっと良い方法がある」という方、ぜひ教えて頂けないでしょうか。