# 2024 Homework4 (quiz3+4) contributed by < `dockyu` > ## 第 3 週測驗題 [第 3 週測驗題 連結](https://hackmd.io/@sysprog/linux2024-quiz3) ### 測驗一 --- ## 第 4 週測驗題 [第 4 週測驗題 連結](https://hackmd.io/@sysprog/linux2024-quiz4) ### 測驗一 ```c unsigned popcount_naive(unsigned v) { unsigned n = 0; while (v) v &= (v - 1), n = -(~n); return n; } ``` 有幾個位元是1就必須加幾次 `n = -(~n)` 等於 `n++` 是一種很酷的寫法，但是為什麼編譯器在做最佳化的時候應該也可以將 `n++` 轉成 `n = -(~n)` ，這樣程式碼可讀性比較高，為什麼不這樣做呢？ --- 如果用下面的方法來做要減31次 \begin{align} popcount(x) = x - \left \lfloor{{\dfrac{x}{2}}}\right \rfloor - \left \lfloor{{\dfrac{x}{4}}}\right \rfloor - ... - \left \lfloor{{\dfrac{x}{2^{{31}}}}}\right \rfloor \end{align} 但是如果分區塊(四位元)來進行每個區塊只要減3次，而且可以**同時進行**，在透過位移和乘法將每個區塊加總 我覺得這個分區塊的想法是最精妙的部份，有點類似平行處理，跟下面的測驗4的棋盤表示法在概念上有點像 ### 測驗二 已經知道 $x \mod 3$ 其實就是奇數與偶數 bit 的1的數量的差 並且可以推導出下面的公式 \begin{align} popcount(x \And \overline{m}) - popcount(x \And m) = popcount(x \bigoplus m) - popcount(m) \end{align} ```c= int mod3(unsigned n) { n = popcount(n ^ 0xAAAAAAAA) + 23; n = popcount(n ^ 0x2A) - 3; return n + ((n >> 31) & 3); } ``` 第3行其實就等於`奇偶的差+39`，因為只有32 bit 所以奇偶的差的範圍是 `-16 ～ 16` ，第一行的 n 的範圍是 `23 ～ 55`，所以要再做一次但是因為最大才55所以可以用 0x2A 當作 m ，做完第二行後 n 的範圍是 `-3 ～ 3`，如果是負的後面 `((n >> 31) & 3)` 會是3，把 n 補回正的 ```bash (gdb) p /t i $2 = 11111111111111111111111111111101 (gdb) set variable i = i >> 1 (gdb) p /t i $3 = 1111111111111111111111111111110 ``` 提醒: 負數位移會補1 ```c= int mod3(unsigned n) { static char table[33] = {2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1 }; n = popcount(n ^ 0xAAAAAAAA); return table[n]; } ``` 第3行明顯跟上面推導的公式不一樣少了 `-16` ，所以 n 的範圍是 `0 ～ 32` ，而 $n=0$ 實際上 $\mod 3$ 的結果是-16，對照下表，因為範圍是 `0 ～ 32` 而且我們已經知道每一個數的答案，那麼直接用一個 lookup table 比較快 |$n$|$\mod 3$|正確答案| |:-:|:-:|:-:| |0|-16|2| |1|-15|0| |2|-14|1| |3|-13|2| |4|-12|0| |$\vdots$|$\vdots$|$\vdots$| |31|15|0| |32|16|1| 我覺得使用 lookup table 是一種很優美的方式，我之前根本沒有想過，他的流程是先用數學方法將問題的範圍限縮在一個可接受的範圍內，再用查表法來加快速度 其實兩種 mod3 函式都有用 popcount 來縮小範圍但是前者必須做兩次，因為範圍還沒精確到可以直接得出答案 參考 [vax-r 的筆記](https://hackmd.io/@vax-r/linux2024-homework4) 定義8條線的三個點是一個4位元的後3位元，這樣下每一格都不會互相影響