clz
===
## 作業要求
* 閱讀[重新了解數值](https://hackmd.io/s/SkKZBXZT)
* 比較以下clz算法之效能差異(使用32bit之數值)
* recursive version
* iteration version
* binary search technique
* byte-shift version
* Harley’s algorithm

## 實做
* recursive version
* code

    int clz(uint32_t x)
    {
      if(!x) return 32; //輸入為0直接回傳
      uint16_t upper = (x >> count);//把位元拆半成upper
      uint16_t lower = (x & (0xFFFFFFFF>>count));//把位元拆半成lower
      /*中止條件(拆半到不能再拆半時)*/
      if(count==1) return (x>>1)?0:1;
      /*中止條件(拆半到不能再拆半時)*/
      count >>= 1;
      result =upper ? clz(upper) : (count<<1) + clz(lower);//如果upper有數值就算upper就好了，不然就算lower＋upper的0個數
      count <<= 1;//回復count的數值
      return result;
     }

* 補充：原始的code沒有設定中止條件，這樣recursive是不會停止的。
* 測試結果
* iteration version
* code

    int clz(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);
    }

* 測試結果

* binary search technique
* code

    int clz(uint32_t x) {
    if (x == 0) return 32;
    int n = 0;
    if (x <= 0x0000FFFF) { n += 16; x <<= 16; }
    if (x <= 0x00FFFFFF) { n += 8; x <<= 8; }
    if (x <= 0x0FFFFFFF) { n += 4; x <<= 4; }
    if (x <= 0x3FFFFFFF) { n += 2; x <<= 2; }
    if (x <= 0x7FFFFFFF) { n += 1; x <<= 1; }
    return n;
    }

* 測試結果
binary search 在輸入接近10000時，會產生明顯抖動的現象發生!

* byte-shift version
* code

    int clz(uint32_t x) {
    if (x == 0) return 32;
    int n = 1;
    if ((x >> 16) == 0) { n += 16; x <<= 16; }
    if ((x >> 24) == 0) { n += 8; x <<= 8; }
    if ((x >> 28) == 0) { n += 4; x <<= 4; }
    if ((x >> 30) == 0) { n += 2; x <<= 2; }
    n = n - (x >> 31);
    return n;
    } 

* 測試結果

* Harley’s algorithm
* code

    int clz(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);
    }

* 測試結果

## 測試結果比較


*總體而言 Harley 的效能是最差的

## 參考資料

[gnu Makefile 使用手冊](https://www.gnu.org/software/make/manual/html_node/Implicit-Variables.html#Implicit-Variables)
[gcc與Makefile使用筆記](http://jayextmemo.blogspot.tw/2015/01/linux-gcc-makefile.html)
[台大cmlab](http://www.cmlab.csie.ntu.edu.tw/~daniel/linux/gcc.html)