# 2016q3 Homework1(clz)
contributed by <`jkrvivian`>

### Reviewed by <`vic85821`>
* 建議貼出修改後的 harley algorithm code
* 缺少各演算法的效能比較
* 原本的recursive版本的錯誤在哪,為何會造成程式錯誤
* [commit c3ad77e](https://github.com/jkrvivian/clz-tests/commit/c3ad77e3fd63fbb997f4a1590bf24b2633ea8fa3) 從commit看不出各個檔案的內容與修改

## 目標
閱讀 重新理解數值 裡頭關於 count leading zero (clz) 的描述，設計實驗，比較 32-bit 數值對以下實做的效能差異：

* recursive version
* iteration version
* binary search technique
* byte-shift version
* Harley’s algorithm

## 測試

測試[重新理解數值](https://hackmd.io/s/SkKZBXZT#integer-overflow)中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
* 照此[連結](http://www.hackersdelight.org/hdcodetxt/nlz.c.txt)的程式碼修改
* 但還不清楚這個演算法背後的原理
* 測試一樣沒有問題~

## 參考資料
* [TempoJiJi](https://hackmd.io/s/ryiig7YT)
* [劉亮谷學長](https://hackmd.io/GYJghsCsDMDGCmBaekQA5EBZrxIs0ADHtAOyYCM0mI8AbCKbEA==#)
* [黃鏡清同學](https://hackmd.io/s/Byyd3nua)

###### tags: `system embedded` `HW1-4`