# 2016q3 Homework1 (CLZ)
#### contributed by <andy19950>

### Count Leading Zero (CLZ)
- 用來計算一筆資料前面有幾個零
- 實做方法
1.recursive
2.iteration
3.binary search technique
4.byte-shift version
5.Harley’s algorithm

#### 首先來個 recursive 版本

int clz_recur(uint32_t x, int size)
{
    if(size == 0) return 0;
    // shift upper half down, rest is filled up with 0s 
    uint16_t upper = (x >> size);
    // mask upper half away
    int loc = (int) ceil(log((double)size)/log((double)2));
    uint16_t lower = (x & TABLE[loc]);
    return upper ? clz_recur(upper, size/2) : size + clz_recur(lower, size/2);
}

- 原本程式碼算是個概念，我把傳入值加入了每次要檢查的 size
- 取 lower 的方法是在 .h 檔定義一個 TABLE[] = {0x01, 0x03, 0x0F, 0xFF, 0xFFFF};
- 每次都把 size 取 log 以2為底，因為 C 只有 log 以 e 為底，所以我用換底公式實做以 2 為底
- 接下來就是遞迴到size = 0 的時候回傳，函式會把前面有幾個 0 通通加起來再回傳給 main

#### 再來是 iteration 版本

int clz_itera(uint32_t x) {
    int n = 32, c = 16;
    do {
        uint32_t y = x >> c;
        if (y) { n -= c; x = y; }
        c >>= 1;
    } while (c);
    return (n - x);
}

- 這是參考老師給的程式碼，用 while 迴圈每次檢查 1 bit
- 但這份程式碼還是把輸入資料切一半來處理，算是比較好的版本

#### 最後是 Harley's Algorithm

uint32_t clz_Harley(uint32_t x)
{
    static const uint8_t Table[] = {
      0xFF, 0, 0xFF, 15, 0xFF, 1, 28, 0xFF,
      16, 0xFF, 0xFF, 0xFF, 2, 21, 29, 0xFF,
      0xFF, 0xFF, 19, 17, 10, 0xFF, 12, 0xFF,
      0xFF, 3, 0xFF, 6, 0xFF, 22, 30, 0xFF,
      14, 0xFF, 27, 0xFF, 0xFF, 0xFF, 20, 0xFF,
      18, 9, 11, 0xFF, 5, 0xFF, 0xFF, 13,
      26, 0xFF, 0xFF, 8, 0xFF, 4, 0xFF, 25,
      0xFF, 7, 24, 0xFF, 23, 0xFF, 31, 0xFF,
    };
/* Propagate leftmost 1-bit to the right */
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);

    /* x = x * 0x6EB14F9 */
    x = (x << 3) - x;   /* Multiply by 7. */
    x = (x << 8) - x;   /* Multiply by 255. */
    x = (x << 8) - x;   /* Again. */
    x = (x << 8) - x;   /* Again. */

    return (Table[x >> 26]);
}

- 由於它實在是太博大精深了，等我搞懂了再來補充QQ
---
### 接下來就是效能分析拉
- recursive 版本明顯消耗更多時間
- iteration 跟 Harley 差不多，但Harley還是稍微好一點。
---