# 2024q1 Homework4 (quiz3+4)
contributed by < `Grace258` >

## [第 3 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz3)
### 測驗一
版本一使用 `log2` 函式取得最靠近 `N` 且小於等於 `N` 的 `2` 的指數，回傳值的資料型態為 `double` ，因此需要將其強制轉型成 `int` ，才會是最高有效位 `(MSB)`。
可以將其理解為將目標數 `N` 拆解成 `2` 的冪相加，由 `2` 的 `MSB` 次方開始，每次向右移一位 `(/2)` ，直到 `a = 0`。

版本二和版本一的差別在於版本二使用 `while` 迴圈來取得最高有效位。

實作的原理是將欲求平方根的 $N^2$ 拆解成:
$N^2=(a_n+a_{n-1}+a_{n-2}+\ ...\ +a_0)^2, a_m=2^m\ or\ a_m=0$

取得最高有效位也可以使用

int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL)

:::danger
不用列出 AAAA, BBBB 等參考題解。專注在探討程式碼和應用案例。
:::

其中 `__builtin_clz(x)` 是 GCC 的內建函式，目的是找到 x 的最高有效位左邊的 0 的個數，當 `x = 0` 時，未定義。
`int m` 對應到 $d_m$ ，所以 AAAA 是 `2` ，

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 >>= AAAA) {
        int b = z + m;
        z >>= BBBB;
        if (x >= b)
            x -= b, z += m;               
    }
    return z;
}

#### 使用 [ffs](https://man7.org/linux/man-pages/man3/ffs.3.html) 替換 `__builtin_clz`
為了使程式不依賴 `GNU extension` ，將 `__builtin_clz` 替換成相似的概念 [ffs](https://man7.org/linux/man-pages/man3/ffs.3.html)， `ffs` 接受一個整數變數，並以整數回傳該變數的 `LSB(Least Significant Bit)` ，`ffsl` 和 `ffsll` 用途和 `ffs` 一樣，差別在於接收的變數型態，前者為 `long` 後者為 `long long`。