contributed by <
brian049
>
在測驗三當中針對 ilog 有三種版本,第一種版本透過不斷向右位移二進位位元來計算以 2 為底的對數。
第二種版本與第一種版本相似,但是是透過比較較大數字開始,一步一步將二進位位元向右位移到 0。
相對於第一種方式,第二種方式較為快速,我透過 Linux shell command time
指令來計算執行時間。
針對兩種方式我透過用兩種測資,一個測資為 65536,另一個測資為 87654321。
經過測試發現,若是測資較小,執行時間較無差異,但是若是測資較大,則執行時間差異較大。
第三種方式是透過呼叫 __builtin_clz
巨集來計算在二進位當中最高位元為 1 的位置,來得到以 2 為底的對數。
在 linux/log2.h 當中有 ilog2 巨集的定義。
其實作的方法是暴力法(Brute force) 從 63 位元開始比對,若是向左位移 63 位元得到 1 時則是 2 的 63 次方,以此類推直到比對到第 2 位元。
透過 Github 搜尋欄位查詢到在 linux/lib/math/div64.c 當中有應用到 ilog2
這個巨集。
mul_u64_u64_div_u64
函式當中運用 ilog2
巨集來判斷兩數 a, b 是否在相乘之後是否會溢位。
測驗五是測驗三的延伸,改變的點是添加了 ceilling 的功能。
r
以及 shift
是用作紀錄因給定數字 x
分別大於 0xFFFF
, 0xFF
, 0xF
, 0x3
的時候,需要進行下一步判斷需要位移的數量。
其中 r
, shift
都是 2 的指數所以 r | shift
就相當於 r + shift
。
最後的 x > 1
是為了判斷 x
若是大於 1 且小於等於 0x3 時的狀況。
x = 0
in branchless若是 x
為 0,在進入函式一開始的時候會因為 x--
變成 0xFFFFFFFF,所以在做減法前就需要判斷是否為 0。
commit: 0095464