# 2016q3 Homework1 (clz)
contribute by <`kaizsv`>

### recursive

int recursive(uint32_t N, int length)
{
    int shift = length >> 1;
    int left = 32 - shift;
    uint32_t MAX = 0xFFFFFFFF;

    uint16_t upper = (N >> shift) & (MAX >> left);
    uint16_t lower = (N & (MAX >> left));

    if (shift == 1) {
        return upper ? 0 : (lower ? 1 : 2);
    }

    return upper ? recursive(upper, shift) : shift + recursive(lower, shift);
}

### harley algorithm
這個一直試不好，後來看了[這篇](http://www.hackersdelight.org/hdcodetxt/nlz.c.txt)把`table`的順序調一下，我在程式碼內都有插入`assert`確保這些修改的程式碼是對的。

int harley_algorithm(uint32_t N)
{
    static int const table[] = {
        32, 31, 0xff, 16, 0xff, 30, 3, 0xff,
        15, 0xff, 0xff, 0xff, 29, 10, 2, 0xff,
        0xff, 0xff, 12, 14, 21, 0xff, 19, 0xff,
        0xff, 28, 0xff, 25, 0xff, 9, 1, 0xff,
        17, 0xff, 4, 0xff, 0xff, 0xff, 11, 0xff,
        13, 22, 20, 0xff, 26, 0xff, 0xff, 18,
        5, 0xff, 0xff, 23, 0xff, 27, 0xff, 6,
        0xff, 24, 7, 0xff, 8, 0xff, 0, 0xff
    };

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

    N = (N << 3) - N;
    N = (N << 8) - N;
    N = (N << 8) - N;
    N = (N << 8) - N;

    return table[N >> 26];

}

直接下`make plot`就會產生這兩張，上面是`i = 0 ~ 1,000,000`每個點的時間，若是 32bit 太花時間，就算加上`OpenMP`還是要很久，且檔案很大根本塞不進記憶體，就先算到1,000,000。

下面是1,000,000次的平均值，就我的結果而言，`binary search and bit shift`的

###### tags: `assigment_4` `clz`