# 2017q1 Homework1 (clz)
contributed by <`zmke`>

## 開發環境
OS: Ubuntu 16.04 LTS
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
Model name: Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K

## Count Leading Zero
* 計算從 MSB 開始往下到第一個 1 有幾個 0

### recursive version

static const int mask[]= {0,8,12,14};
static const int magic[]= {2,1,0,0};

unsigned clz2(uint32_t x,int c)
{
    if (!x && !c) return 32;

    uint32_t upper = (x >> (16>>c));
    uint32_t lower = (x & (0xFFFF>>mask[c]));
    if (c == 3) return upper ? magic[upper] : 2 + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}

* 從 `clz2(x, 0)` 開始，將 x 分成兩半(upper and lower)
* 若 `upper == 0` 將 `lower` 代入下層遞迴，否則代入 `upper`
* `c == 3` 時終止，用 `magic[]` 來判斷剩下的兩個 bit 開頭有幾個 0
* 將下層的結果加上確定的 0 數得到答案

### iteration version

static inline __attribute((always_inline))
unsigned 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);
}

* y 與 upper 類似，用來紀錄前一半的 bit string
* `y != 0` 將關注的 bit string 縮小到 y ，繼續迴圈
* `y == 0` 向 LSB 方向擴大 c 個 bit
* 直到 `c == 0` 終止，回傳 n-x ， x 是最後剩下的一個 bit 會等於 1 或 0

### byte shift technique

static inline __attribute((always_inline))
unsigned 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;
}

## Reference
[重新理解數值](https://hackmd.io/s/Hy-pTh8Fl)
[ktvexe 筆記](https://hackmd.io/s/BJBZn6Q6)