2024q1 Homework4 (quiz3+4)

contributed by < Grace258 >

第 3 週測驗題

測驗一

版本一使用 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)

不用列出 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 替換 __builtin_clz

為了使程式不依賴 GNU extension ，將 __builtin_clz 替換成相似的概念 ffs， ffs 接受一個整數變數，並以整數回傳該變數的 LSB(Least Significant Bit) ，ffsl 和 ffsll 用途和 ffs 一樣，差別在於接收的變數型態，前者為 long 後者為 long long。