contributed by <` jerry7961` >
## quiz 3
### 測驗一
這段程式碼的目的是計算開平方根。
`__builtin_clz(x)` 會計算 `x` 最高有效位元（最左邊的 1 ）之前有幾個 0 ，再用 31 減掉 `__builtin_clz(x)` 即可得到 `x` 最高有效位元的位置。

int i_sqrt(int x)
{
    if (x <= 1) /* Assume x is always positive */
        return x;

    int z = 0;
    for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2) {
        int b = z + m;
        z >>= 1;
        if (x >= b)
            x -= b, z += m;
    }
    return z;
}

### 測驗二

#include <stdint.h>

void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
    uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
    uint32_t q = (x >> 4) + x;
    x = q;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    *div = (q >> 3); // CCCC = 3
    *mod = in - ((q & ~0x7) + (*div << 1)); // DDDD = 1
}

### 測驗三
* 版本一每次迴圈將 i 右移 1 位，並將 log 加 1 。

int ilog2(int i)
{
    int log = -1;
    while (i) {
        i >>= 1;
        log++;
    }
    return log;
}

* 版本二不是每次只右移 1 位，而是在不同的階段分別右移 16 位、 8 位、 4 位和 1 位，計算效率較版本一高。
* 第一個 `for loop` 檢查 `i` 是否大於等於 2 的 16 次方（65536），如果是說明 `i` 至少有 16 位（在二進位表示中），因此 `result` 增加 16 ，並將 `i` 右移 16 位（i >>= 16），相當於除以 2 的 16 次方。這個過程重覆進行，直到 `i` 小於 65536 。接下來的 for loop 按照順序判斷 i 是否大於 $2^{8}$、$2^{4}$、$2^{2}$ 。最後函式返回 `result` ，即 $\log_2i$ 的整數部分。

static size_t ilog2(size_t i)
{
        size_t result = 0;

        while (i >= 65536) {
            result += 16;
            i >>= 16;
        }

        while (i >= 256) {
            result += 8;
            i >>= 8;
        }

        while (i >= 16) {
            result += 4;
            i >>= 4;
        }

        while (i >= 2) {
            result += 1;
            i >>= 1;
        }

        return result;
}

* 版本三利用巨集`__builtin_clz(x)` ，`__builtin_clz(x)` 會計算 x 的二進位表示中，最高位（左側）開始連續的零的數量，也就是 `x` 最高有效位元（最左邊的 1 ）之前有幾個 0 ，再用 31 減掉 `__builtin_clz(x)` 即可得到 x 最高有效位元的位置。
* 因為`__builtin_clz` 的輸入若是 0 則無定義，所以 DDDD 應為 `v | 1`，這樣即使原始輸入 `v` 為 0，操作後的結果也會是 1 ，可以安全使用`__builtin_clz`。

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(v | 1));
}

## quiz 3
### 測驗三