# 2016q3 Homework1 (clz-tests)
contributed by <`Quexint`>

## 開發記錄

### `v0` 原始版本

- 參考
- [Counting leading zeros in a 32 bit unsigned integer with best algorithm in C programming [closed]](http://stackoverflow.com/questions/23856596/counting-leading-zeros-in-a-32-bit-unsigned-integer-with-best-algorithm-in-c-pro)
- [Fast computing of log2 for 64-bit integers](http://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers)
- [How To Find The Leading Number Of Zero's In a Number using C](http://stackoverflow.com/questions/6234533/how-to-find-the-leading-number-of-zeros-in-a-number-using-c)
- [nlzc](http://www.hackersdelight.org/hdcodetxt/nlz.c.txt)
- [Bithacks](http://graphics.stanford.edu/~seander/bithacks.html)
- 先完成 5 個版本的程式碼。
- `clz_recur`

#define MASK(x) ((1LL << (x)) - 1)
uint8_t clz_recur(uint32_t x)
{
    if(x == 0xFFFFFFFF) return 0;
    if(x == 0x7FFFFFFF) return 1;
    uint8_t tailingF = (0x0000FFFF == (x & 0x0000FFFF)) * 16 +
                       (0x00FFFFFF == (x & 0x00FFFFFF)) * 8 +
                       (0x0FFFFFFF == (x & 0x0FFFFFFF)) * 4 +
                       (0x3FFFFFFF == (x & 0x3FFFFFFF)) * 2 +
                       (0x7FFFFFFF == (x & 0x7FFFFFFF)) * 1;
    uint8_t range = (32 - tailingF)>>1;

    uint32_t upper = (x >> tailingF) >> range;
    return upper ? clz_recur(x | MASK(tailingF + range))  :
           range + clz_recur((x << range) | MASK(range));
}

### `v1` 加入 Benchmark 跟 `make plot`

- `make plot` 後, `png` 會有各別的 png 跟全圖的 png
- 記錄每個數字各做 500 次的時間


### `v2` 優化 `clz_bsearch`

- 將 if 的條件用 bitwise operation 取代

uint8_t clz_bsearch(uint32_t x)
{
    if (x == 0) return 32;
    int n = 0;
    if ((x & 0xFFFF0000)==0){
        n += 16;
        x <<= 16;
    }
    if ((x & 0xFF000000)==0) {
        n += 8;
        x <<= 8;
    }
    if ((x & 0xF0000000)==0) {
        n += 4;
        x <<= 4;
    }
    if ((x & 0xC0000000)==0) {
        n += 2;
        x <<= 2;
    }
    if ((x & 0x80000000)==0) {
        n += 1;
        x <<= 1;
    }
    return n;
}

- 運算時間中間有一段 變非常快