changed 8 years ago
Linked with GitHub

clz

作業要求

  • 閱讀重新了解數值
  • 比較以下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 使用手冊
gcc與Makefile使用筆記
台大cmlab

Select a repo