2024q1 Homework4 (quiz3+4)

contributed by < 56han >

第 3 週測驗題

2024q1 第 3 週測驗題

測驗 `1`

Y_{m} = {\begin{cases} c_{m} + d_{m}, & if a_{m} = 2^{m} \\ 0, & if a_{m} = 0 \end{cases}

在每次迴圈更新

c_{m}

、

d_{m}

來計算

Y_{m}

進而推得

a_{m}

c_{m - 1} = P_{m} 2^{m} = (P_{m + 1} + a_{m}) 2^{m} = P_{m + 1} 2^{m} + a_{m} 2^{m} = {\begin{cases} \frac{c_{m}}{2} + d_{m} & if a_{m} = 2^{m} \\ \frac{c_{m}}{2} & if a_{m} = 0 \end{cases}

d_{m - 1} = \frac{d_{m}}{4}

透過閱讀數學算式，進而得到幾個重點：

函式中 z 即是
$C_{m}$ ，而 m 即是
$d_{m}$ ，b 即是
$Y_{m}$ ，x 則是代表前一輪的差值，也就是
$X_{m + 1}$ 。
函式中的迴圈每次迭代時 m 往右位移 2 位，是在表示上面公式中的
$d_{m - 1} = \frac{d_{m}}{4}$ 。
b = z + m; 表示
$Y_{m} = c_{m} + d_{m}$ 。
if 條件是判斷：當
$X_{m + 1}$ 比
$Y_{m}$ 大時，則更新其值。

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;
}

延伸問題 - 嘗試用第 2 週測驗題提到的 ffs / fls 取代 __builtin_clz，使程式不依賴 GNU extension

__ffs() 函數的目的是找到參數 (unsigned long) 中最低位的 1 所在的位置（從 0 開始計算）。
將__ffs() 函數改寫成下面的 fls() 函數的目的是找到參數 (unsigned long) 中最高位的 1 所在的位置（注意：從 1 開始計算）。
__builtin_clz() 為 GCC 的內建函式，功能為找到 x 最高位數前面有幾個 0 ， x 為 0 時，未定義。

所以將 BITS_PER_LONG - fls(x) 即可得到 __builtin_clz(x)。

static inline unsigned long fls(unsigned long x)
{
    int num = 32;
    if(!x)
        return 0;
    if ((x & 0xffff0000) == 0) {
        num -= 16;
        x <<= 16;
    }
    if ((x & 0xff000000) == 0) {
        num -= 8;
        x <<= 8;
    }
    if ((x & 0xf0000000) == 0) {
        num -= 4;
        x <<= 4;
    }
    if ((x & 0xc0000000) == 0) {
        num -= 2;
        x <<= 2;
    }
    if ((x & 0x80000000) == 0) {
        num -= 1;
        x <<= 1;
    }
    return num;
}

因此可以將 i_sqrt() 改寫成以下

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) {
+    for (int m = 1UL << (fls(x)-1 & ~1UL); m; m >>= 2) {
        int b = z + m;
        z >>= 1;
        if (x >= b)
            x -= b, z += m;               
    }
    return z;
}

測驗 `2`

測驗 `3`

考慮 ilog2() 可計算以 2 為底的對數，且其輸入和輸出皆為整數。以下是其一可能的實作: (版本一)
透過一次又一次的右移(除以 2 )，直到 i=0，去計算 i 以 2 為底時有多少位數。

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

改寫為以下程式碼: (版本二)
透過右移的方式去計算 i 以 2 為底時有多少位數。

我認為這裡的 while 可以改成 if，因為 i 透過右移會越來越小，因此不會進入相同迴圈中，只會往下走，進入別的判斷式中。

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= (1<<16)) { //2^16
        result += 16;
        i >>= 16;
    }
    while (i >= (1<<8)) { //2^8
        result += 8;
        i >>= 8;
    }
    while (i >= (1<<4)) { //2^4
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

亦可運用 GNU extension __builtin_clz 來改寫，注意輸入若是 0 則無定義： (版本三)
透過 31-__builtin_clz() 找到最高位數，即是取 log 以後的值。

__builtin_clz() 為 GCC 的內建函式，功能為找到 x 最高位數前面有幾個 0 ， x 為 0 時，未定義。

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

測驗 `4`

測驗 `5`

延伸測驗 3，已知輸入必為大於 0 的數值 (即 x > 0)，以下程式碼可計算

⌈ \log_{2} (x) ⌉

，也就是 ceil 和 log2 的組合並轉型為整數：

int ceil_ilog2(uint32_t x)
{
    uint32_t r, shift;
    x--;
    r = (x > 0xFFFF) << 4;               
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (r | shift | x > 1) + 1;       
}

函數首先 x - 1，是為了對於 2 的冪的數值也能夠正確計算對數。
shift = (x > 0xFF) << 3; 表示，若 x > 15 則為 1 << 2，否則為 0 << 2。
大部分和測驗 3 類似，當我們看到以下片段

shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;

首先判斷 x > 0xFF ，並使用 shift 記錄要移動多少。
x >>= shift; 即是測驗 3 的 i >>= 16;，r |= shift; 即是 r = r + shift; 之意。

最後 return 可拆成3個部份看

return (r | shift | x > 1) + 1;

r | shift 即是 r = r + shift; 之意
判斷 x 是否還有剩，因為前面shift = (x > 0x3) << 1; 會忽略 x = 0x2 的情況。
最後再 +1 作為取上界 (ceil) 。

第 4 週測驗題

2024q1 第 4 週測驗題

測驗 `1`

此題是 LeetCode 477. Total Hamming Distance ，透過兩個for 迴圈可以逐一比較兩個數字之間的 Hamming Distance，最後要除以2 (右移1位)，因為重複計算ab和ba。

GCC 提供對應的內建函式:

__builtin_popcount(x): 計算 x 的二進位表示中，總共有幾個 1

int totalHammingDistance(int* nums, int numsSize)
{
    int total = 0;;
    for (int i = 0;i < numsSize;i++)
        for (int j = 0; j < numsSize;j++)
            total += __builtin_popcount(nums[i] ^ nums[j]); 
    return total >> 1;
}

延伸問題 - 不依賴 popcount，嘗試以上述歸納的規則，撰寫出更高效的程式碼。

從 popcount 角度出發，時間複雜度就被限制在

O (n^{2})

。
以下嘗試從位元展現的樣貌，觀察 Total Hamming Distance 的規則。

n'th bit	4	3	2	1	0
input 7	0	0	1	1	1
input 5	0	0	1	0	1
input 10	0	1	0	0	1
input 17	1	0	0	0	1

第 0 個 bit 觀察 :
全部都是 1 -> Hamming Distance = 0
第 1 個 bit 觀察 :
1 有一個，其餘皆為 0
可以直接用單個 bit 判斷 Hamming Distance (1)* (numsize - 1)
第 2 個 bit 觀察 :
1 有兩個，其餘皆為 0
Hamming Distance (2)* (numsize - 2)

以 bit 找規則:

所有 Number 中從第 0 個 bit 開始計算全部該 bit 的 Hamming Distance ，在全部累加起來就是 Total Hamming Distance。

可以改寫成以下程式碼，其中：

(nums[i] >> bit) & 1 判斷 nums[i] 該 bit 是否為 1
bitCount 統計出所有數字的該 bit 為 1 有幾個
bitCount * (numsSize - bitCount) 統計該 bit 的 Hamming Distance

int totalHammingDistance(int* nums, int numsSize) {
    int total = 0;
    for (int bit = 0; bit < 32; bit++) {
        int bitCount = 0;
        for (int i = 0; i < numsSize; i++) {
            bitCount += (nums[i] >> bit) & 1;
        }
        total += bitCount * (numsSize - bitCount);
    }
    return total;
}

測驗 `2`

我理解 n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA) 可以寫為 n = popcount(n ^ 0xAAAAAAAA) - 16 ，其中也可以理解「我們要將它加上一個足夠大的 3 的倍數」，但為何是選擇加上39？使其為 n = popcount(n ^ 0xAAAAAAAA) + 23;

int mod3(unsigned n)
{
    n = popcount(n ^ 0xAAAAAAAA) + 23;
    n = popcount(n ^ 0x2A) - 3;
    return n + ((n >> 31) & 3);
}

2024q1 Homework4 (quiz3+4)

第 3 週測驗題

測驗 1

延伸問題 - 嘗試用第 2 週測驗題提到的 ffs / fls 取代 __builtin_clz，使程式不依賴 GNU extension

測驗 2

測驗 3

測驗 4

測驗 5

第 4 週測驗題

測驗 1

延伸問題 - 不依賴 popcount，嘗試以上述歸納的規則，撰寫出更高效的程式碼。

測驗 2

測驗 3

Read more

2025 嵌入式作業系統分析與實作 Lab1

韌體工程師 面試

Linux Final Project

linux2024-homework6

測驗 `1`

測驗 `2`

測驗 `3`

測驗 `4`

測驗 `5`

測驗 `1`

測驗 `2`

測驗 `3`

韌體工程師面試