binarySearchメソッドのバグ

GoogleのJoshua Bloch（Sun Microsystemsから転職したのは，このブログの読者は知ってるよね？）が，Google Research Blogで長い間眠っていた興味深いJavaのライブラリのバグについて報告している．

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

問題があるのは二分探索のコード中の中間を知るために平均を求める部分なのだが，整数値を加算した時にオーバーフローすると負の値になってしまい，その結果ArrayIndexOutOfBoundsExceptionが投げられるというものだ．java.util.Arraysクラス以外にも，java.util.Collectionsクラスやjava.util.TreeMapクラスや，他の分割統治法を用いるようなコードに存在している．自分のコードを見直してみるのもよいだろう．

さて，この部分だけを取り出したサンプルコードを書いてみた．

public class AverageTest {
    public static void main(String args[]) {
	int high = 100;
	int low = 10;

	System.out.printf("high = %d, low = %d?n", high, low);
	System.out.printf("1, (low + high) / 2 -> %d?n", (low + high) / 2);
	System.out.printf("2, (low + high) >> 1 -> %d?n", (low + high) >> 1);
	System.out.printf("3, (low + high) >>> 1 -> %d?n", (low + high) >>> 1);
	System.out.printf("4, low + ( (high - low) / 2) -> %d?n",
			low + ( (high - low) / 2));
	
	high = Integer.MAX_VALUE;
	low = Integer.MAX_VALUE - 1;

	System.out.printf("?nhigh = %d, low = %d?n", high, low);
	System.out.printf("1, (low + high) / 2 -> %d?n", (low + high) / 2);
	System.out.printf("2, (low + high) >> 1 -> %d?n", (low + high) >> 1);
	System.out.printf("3, (low + high) >>> 1 -> %d?n", (low + high) >>> 1);
	System.out.printf("4, low + ( (high - low) / 2) -> %d?n",
			low + ( (high - low) / 2));
    }
}

この実行結果は，以下のようになる．つまり，正しいコードは3と4だ．

high = 100, low = 10
1, (low + high) / 2 -> 55
2, (low + high) >> 1 -> 55
3, (low + high) >>> 1 -> 55
4, low + ((high - low) / 2) -> 55

high = 2147483647, low = 2147483646
1, (low + high) / 2 -> -1
2, (low + high) >> 1 -> -2
3, (low + high) >>> 1 -> 2147483646
4, low + ((high - low) / 2) -> 2147483646

さて，この興味深いバグは，いくつかの示唆を与えてくれる．一つは，この種のバグは非常に見つけにくいことであり，もう一つは技術の進歩の早さである．昔は32ビット空間は広大だと思ったが，今では必ずしもそうではない．Webの登場により，大規模データを処理するのが当たり前となりつつある昨今，この種のバグを作らないこと，また早期に発見して修正することが，ますます重要になっていくだろう．