# 2017q3 Homework1 (clz)
contributed by <`HMKRL`>

---
>**TODO**: cdf, pdf[color=red]

首先觀察各個版本的實作方式，並與效能做比較：

此為 fork 後直接執行 `make plot` 得到的結果：

原先預期直接採用iteration會根據 leading zero 有不同表現，但發現不是如此，檢視程式碼：

    int n = 32, c = 16;
    do {
        uint32_t y = x >> c;
        if (y) {
            n -= c;
            x = y;
        }
        c >>= 1;
    } while (c);
    return (n - x);

可以發現此處也採用了每次減半的作法，因此不會因 leading zero 數量不同有太大差異。

嘗試將 `iteration.c` 修改如下：

static inline __attribute((always_inline))
unsigned clz(uint32_t x)
{
    int n = 32;
    while (x) {
        x >>= 1;
        --n;
    }

    return n;
}

得到以下結果：

可以明顯看出數值較小的部份，由於 leading zero 較多，花費的 cycle 數也較多

- binary & byte
分別觀察這兩種作法的程式碼，可以發現實作幾乎相同，差別在是直接比較或先進行位移，因此效能分析的結果也幾乎相同

- recursive

為了減少遞迴末段的 function call 造成效能問題，採用了 `magic` 表做終止條件查表

- harley
首先觀察這段程式碼：

x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);

直接帶入數值協助理解，帶入 `0000 0000 0100 0000 1110 1111 0000 1000`

得到 `0000 0000 0111 1111 1111 1111 1111 1111`

由此得知這段程式碼用途是將第一次出現的1之後的位元都設為1

/* 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)];

此區域經過觀察，得知其為一種 hash function ，可以將經過前項處理產生的33種可能數值轉化至最高5個位元，並透過查表對照相應的clz值

此種作法的優點：因為是採用查表實作，因此只要更改對應的表格，就可以便於計算其他數值(例如 `CTZ` )