2016q3 Homework1 (clz-tests)

contributed by <Quexint>

開發記錄

v0 原始版本

• 參考
  • Counting leading zeros in a 32 bit unsigned integer with best algorithm in C programming [closed]
  • Fast computing of log2 for 64-bit integers
  • How To Find The Leading Number Of Zero's In a Number using C
  • nlzc
  • Bithacks
• 先完成 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;
}

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