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 }_{2}i$ 的整數部分。

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

測驗三