2024q1 Homework4 (quiz3+4)

contributed by < Daniel-0224 >

第三周測驗

測驗三

版本一
使用右移操作來計算 msb 在第幾位，以此當作 log 值，而計算 msb 也可以藉由計算 i 的 counting leading zero 來達成。

版本二
先判斷 i 是否大於

$2^{16}$ ，若是則繼續往 i 是否大於

$2^{24}$ 判斷，若不是則判斷 i 是否大於

$2^8$ ，以此類推，原理其實就是二分搜尋，在32位元中找到 msb 。

測驗四

測驗五

測驗五原理與測驗三大致相同，也是利用二分搜法找出 msb ，x-- 是為了正確運算2的冪，像是 x = 0x80 需要先減一在 return 時加一取的正確的

$\lceil \log (x)\rceil$ ，而 這裡的r 等於測驗三的 result ，r ｜＝ shift 等於 r + shift 因為 r 與 shift 都是2的冪，可以 ｜ 代替 ＋。

改進程式碼：
將 x-- 改成以下寫法可以使處理 x = 0 的狀況，並仍是 branchless。
這是在 linux kernel likely 巨集中學會的，使的 x 一定是 0 或 1 。

但程式碼還是有以下問題，當輸入為 0 或 1 時，輸出都是1，但根據數學定義，

$\log (1)=0$，而

$\log 0$ 是未定義的，這部分還不知道怎麼改進。

#define likely(x)    __builtin_expect(!!(x), 1)

int ceil_ilog2(uint32_t x)
{
-    x--;
+    x -= !!x;
}

後來想到了方法解決上述的問題，若是將原本測驗題程式碼中 x-- 及 return (r | shift | x > 1) + 1; 改成 return (r | shift | x > 1); ，就會變成 floor_ilog2 ，除了2的冪是正確的其他都比正確值少1，因此先判斷 x 是否為2的冪，若是則 return 不加1，不是則加1，解決了前面的問題而且還維持得以處理 x = 0 的狀況，並仍是 branchless。

int ceil_ilog2(uint32_t x)
{
-   uint32_t r, shift;
+   uint32_t r, shift, p;
    
-   x -= !!x; 
+   p =  (((x & (x - 1)) == 0));
    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; 
+   return (r | shift | x > 1) + (!p & 1);

}

In linux kernel:

這是我在 include/linux/sched.h 中找到與 log 相關的程式碼，但不太了解程式碼在做甚麼。 但我想 1 + ilog2(TASK_REPORT_MAX) 是 ceil 與 log 的組合。

static inline char task_index_to_char(unsigned int state)
{
	static const char state_char[] = "RSDTtXZPI";

	BUILD_BUG_ON(1 + ilog2(TASK_REPORT_MAX) != sizeof(state_char) - 1);

	return state_char[state];
}

第四周測驗

測驗一

函式 popcount_naive() 不斷清除 LSB 直到輸入的數值 v 為 0，而 n = -(~n) 等同 n++ ，因為在二補數系統中，

$-n=\sim n+1$ ，

$-(\sim n)=n+1$ 。

popcount 可以寫成以下公式：

$popcount(x)=x-\lfloor {\displaystyle \frac{x}{2}}\rfloor -\lfloor {\displaystyle \frac{x}{4}}\rfloor -\lfloor {\displaystyle \frac{x}{8}}\rfloor -...-\lfloor {\displaystyle \frac{x}{2^{31}}}\rfloor =\sum _{n=0}^{31}(2^n-\sum _{i=0}^{n-1}{2}^i)b_n=\sum _{n=0}^{31}{b}_n$

程式碼：

1. n = (v >> 1) & 0x77777777 將輸入 v 除以2，得
   $\lfloor {\displaystyle \frac{v}{2}}\rfloor$ ，& 0x77777777 以每 4 個位元 (nibble) 為一個單位計算 1 的個數。
2. v = (v + (v >> 4)) & 0x0F0F0F0F ，將每 4 個位元中 set bit 的個數加到 byte 中。

假設

$Bn$ 代表第 n 個 nibble (4 位元) 中的數值

// v
B7 B6 B5 B4 B3 B2 B1 B0  

// (v + (v >> 4))
B7 (B7+B6) (B6+B5) (B5+B4) (B4+B3) (B3+B2) (B2+B1) (B1+B0)

// (v + (v >> 4)) & 0x0F0F0F0F
0 (B7+B6) 0 (B5+B4) 0 (B3+B2) 0 (B1+B0)

透過 v *= 0x01010101 將各個 nibble 相加

A6 = B7+B6, A4 = B5+B4, A2 = B3+B2, A0 = B1+B0

                         0 A6  0 A4  0 A2  0 A0
                      x  0  1  0  1  0  1  0  1
---------------------------------------------------
                         0 A6  0 A4  0 A2  0 A0
                   0 A6  0 A4  0 A2  0 A0  0
             0 A6  0 A4  0 A2  0 A0  0
       0 A6  0 A4  0 A2  0 A0  0
---------------------------------------------------
                            ↑_______________________A6+A4+A2+A0

return v >> 24 : 最後得到的結果會放在 Most significant byte 中，因此向右位移 24 位元，即為所求的 popcount 值。

改善程式碼：

int totalHammingDistance(int8 nums, int numsSize){
    int total = 0;
    for(int i = 0; i < 32; i++){
        int ones = 0, zeros = 0;
        for(int n = 0; n < numsSize; n++){
            if((nums[n] >> i) & 1){
                ones++;
            } else {
                zeros++;
            }
        }
        total += ones*zeros;
    }
    return total;
}

n'th bit	3	2	1	0
4	0	1	0	0
14	1	1	1	0
2	0	0	1	0

第 0 bit :
zeros = 3; ones = 0; total = 0;
第 1 bit :
zeros = 1; ones = 2; total = 2;
第 2 bit :
zeros = 1; ones = 2; total = 2;
第 3 bit :
zeros = 2; ones = 1; total = 2;
total HammingDistance = 6.

測驗二