The Wonder Four: 解 bug 的心理陷阱：我的可以動

2012年2月8日星期三

昨天又遇到鬼打牆的解 bug 問題，一開始是自己寫的 AP +

JNI shared library 可以用，但是給同事的 AP call 就有

錯誤，於是卡在我的可以動的迷思中 XD。所以先請同事幫忙

debug，但是除了一個 static access warning 外，在應用

程式端也沒別的線索了。自己才真正開始回去追 JNI shared

library，結果確定是該用 jintArray 的型態用錯為 jint

*。於是修改過後今天給同事確定可以解掉這個問題。但現

在問題變成是，為何原本的寫法我的應用程式可以存取 JNI

integer array ? XD

另外昨天看到一篇 Joshua Bloch 的 binary search, merge

Programming Pearls 書(1986, second edition 2000 )中

的演算法，跟他在 JDK 實作 java.util.Array 的 binarySearch (存在九年的 bug) 同樣犯了 divide and

conquer 取中間數的錯誤：

6: int mid =(low + high) / 2;

mid 可能遇到太大的 low 跟 high 造成 mid 發生 integer overflow，大於最大正整數 (2^31 - 1)，這個 bug 可以藏

這麼久的原因是之前沒有人測過這麼大量的 binary search 或

merge sort 解法是

6: int mid = low + ((high - low) / 2);

或用 Java 的 unsigned right shift, ">>>", (最高位補 0

確保為正整數)取代除以 2 較快些

6: int mid = (low + high) >>> 1;

C/C++ 參考解法如下：(參考 Nokia 的 Antonie Trux 指出

C89/90 跟 C++、C99 說明 signed integer 相加 overflow

的話是未定義行為，因此先轉型為 unsigned int)

6: mid = ((unsigned int)low + (unsigned int)high)) >> 1;

該文後面 Joshua Bloch 說明的是這個 bug 讓他學會謙虛，

即使是我們認為理所當然的取平均都可能出錯，細心的設計

、測試的重要性、正規方法、檢視程式碼、靜態分析都是很

棒的，任何單一方法絕對無法保證沒有 bug。即使我們竭盡

全力解一個 bug，也可能要花上幾十年才解掉。因此寫程式

必須小心、防衛並時時警覺。

The Wonder Four