今天偶然看到一個講
求較小值的帖子，讓我突然想起一年前一次折騰逆向工程的嘗試，當時用IDA進行反匯編，看到一串匯編代碼，非常精妙，最終發現僅僅是為了計算兩個整數的較小值。可現在非常努力的回憶，就是想不起來是怎么做的。
真的非常想再現那串算法，于是自己開始推敲。我來談談我推敲的過程。
命題：給定整數x,y，計算較小值m。
兩個數的差異，在于他們的差，于是想到計算z = x - y，我想也許可以利用這個中間值，利用一些巧妙的位運算求出，可是貌似還是比較困難。于是我打算重新理一下思路：
可能出現的情況：(暫時忽略特殊情況 z = 0)
1. x < y
z < 0
就是要找到一個函數f，滿足f(y , z) = x
2. x > y
z > 0
就需要這個f不僅滿足1，而且滿足此時f(y , z) = y
因為算法的目的是使用加減法、位運算這些基本運算，盡可能簡單的計算。所以我選擇了加法運算
y + g(z) = x , z = x - y < 0;
y + g(z) = y , z = x - y > 0;
最終變成尋求一元函數g
就是
g(z) = z, z < 0
g(z) = 0, z > 0
也就是要找到一個一元分段函數，而且需要運算簡單，于是我想到了g(z) = (z >> 31) & z
如果z < 0，z>>31得到的是FFFFFFFF，再與上一個z，還是z，
如果z > 0, z>>31得到的是0000000，最終還是0
所以最終的算法是
z = x - y
m = ((z >> 31) & z) + y;
這個算法應該跟當初看到的比較接近了。它的優點很顯然，全部是最基本的運算，而且不包含控制指令，而且完全可以直接由寄存器計算完成，效率很高。
算法本身并非什么驚天地泣鬼神大算法，而且在編譯器里肯定會有自己做這樣的優化，其實最讓我欣慰的是我這次的思路，思路非常清晰，很久沒有動腦子的我，居然還能這么思考，我已經很高興了。其中主要包含兩種思想：分類討論、降低元數(降二元為一元)。這也是使用非常廣泛的方法了，前者主要幫助理清思路，后者主要降低復雜度。
Updated: 之前用的是z>>32，用gcc編譯會出現一個警告：
right shift count >= width of type [enabled by default]
但還不清楚會存在什么樣的隱患，所以改成31
posted on 2011-08-22 23:58
夜風 閱讀(14569)
評論(16) 編輯 收藏 引用 所屬分類:
算法