HackMD
2016q3 Homework1(clz)
contributed by <jkrvivian>
Reviewed by <vic85821>
- 建議貼出修改後的 harley algorithm code
- 缺少各演算法的效能比較
- 原本的recursive版本的錯誤在哪,為何會造成程式錯誤
- commit c3ad77e 從commit看不出各個檔案的內容與修改
目標
閱讀 重新理解數值 裡頭關於 count leading zero (clz) 的描述，設計實驗，比較 32-bit 數值對以下實做的效能差異：
- recursive version
- iteration version
- binary search technique
- byte-shift version
- Harley’s algorithm
測試
測試重新理解數值中clz的
- iteration version
- binary search technique
- byte-shift version
從1開始跑到UNIT_MAX，直接和gcc提供的內建函式__builtin_clz()比對結果，結果測試都正確
程式碼：
for (i = 1; i < UINT_MAX; ++i) {
assert(clz_iteration(i) == __builtin_clz(i));
assert(clz_binary_search(i) == __builtin_clz(i));
assert(clz_byte_shift(i) == __builtin_clz(i));
}
- recursive version
直接使用作業說明中的程式碼會core dump- 原本的shift-bit的位數都沒有更改
- return lower也要加上shift-bit的位數
- 修改：
- 本來寫
uint16_t lower = (x & (0xFFFF >> shift);結果完全不對，參考 TempoJiJi 同學的方法才發現錯誤，好粗心>"<
uint8_t clz_recursive(uint32_t x, int shift)
{
if (!shift) return 0;
uint16_t upper = (x >> shift);
uint16_t lower = (x & (0xFFFF >> (16 - shift)));
return upper ? clz_recursive(upper,shift>>1) : shift + clz_recursive(lower,shift>>1);
}
測試結果如上，一樣沒有印出任何訊息，正確
- Harley’s algorithm
- 照此連結的程式碼修改
- 但還不清楚這個演算法背後的原理
- 測試一樣沒有問題~
