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還是稍微好一點。

---