# 2024q1 Homework4 (quiz3+4)
contributed by < `mesohandsome` >
## quiz3 測驗 1
### 程式碼運作原理
$$
c_m = P_{m + 1} 2^{m + 1}
$$
$$
d_m = (2^m)^2
$$
$$
Y_m = \left.
\begin{cases}
c_m + d_m & \text{if } a_m = 2^m \\
0 & \text{if } a_m = 0
\end{cases}
\right.
$$
藉由位元運算推算出下一輪 $c_{m - 1}$，$d_{m - 1}$
$$
c_{m - 1} = P_m2^m = (P_{m + 1} + a_m)2^m = P_{m + 1}2^m + a_m2^m = \dfrac{1}{2}P_{m + 1} 2^{m + 1} + (2^m)^2 = \left.
\begin{cases}
c_m / 2 + d_m & \text{if } a_m = 2^m \\
0 & \text{if } a_m = 0
\end{cases}
\right.
$$
$$
d_{m - 1} = (2^{m - 1})^2 = \dfrac{1}{4}(2^m)^2 = \dfrac{1}{4}d_m
$$
在程式碼中，`int m` 對應到 $d_m$，所以每回合都除以 4，也就是右移 2 位。
`int z` 則是 $c_m$，除以 2 也就是右移 1 位。
```c
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;
}
```
使用第 2 週測驗中的 `__ffs(x)` 取代 `__builtin_clz`。
```diff
- for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2) {
+ for (int m = 1UL << __ffs(x); m; m>>= 2) {
int b = z + m;
z >>= 1;
if (x >= b)
x -= b, z += m;
}
```
在[第 3 週測驗 1](https://hackmd.io/@sysprog/linux2024-quiz3) 中有一部分的敘述標示不清楚，$c_m$ , $d_m$ , $Y_m$ 之間應有間格標示，但在 hackmd 上用 `\\` 換行有些情況沒辦法顯示，所以黏在一起，閱讀時在這部份產生誤解並觀察了非常久才發現問題。
## quiz3 測驗 2
### 程式碼運作原理
為了減少乘除法運算，需要以 bitwise 運算去逼近 $1/10$，而算式必定為 $\dfrac{an}{2^N}$，$N$ 為非負整數，$a$ 為正整數，所以找出 $(\dfrac{1}{8} + \dfrac{1}{2} + 1) \cdot \dfrac{8}{128} = \dfrac{13}{128} \approx 0.1$。
```
(tmp >> 3) + (tmp >> 1) + tmp
```
上面的運算可以看成 $\dfrac{tmp}{8} + \dfrac{tmp}{2} + tmp = \dfrac{13}{8}tmp$
再把 $\dfrac{13}{8}tmp$ 乘以 $\dfrac{8}{128}$ 得到接近 $\dfrac{1}{10} tmp$，也就是 div 的結果。
也因為 $in = div * 10 + mod$，所以將剛才整理好的 $\dfrac{1}{10}tmp$ 以 bitwise 操作乘以 10 倍後，與原始值相減就會得到 mod 的結果。
```c
unsigned d2, d1, d0, q, r;
d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
q = ((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2) >> 7;
r = tmp - (((q << 2) + q) << 1);
```
`q` 計算完會逼近 `0.8 * in`，在計算 `div` 時要讓他接近 `0.1 * in`，所以要右移 3 位。
而 mod 會等於 div 10 的結果乘 10，所以原本的 `q` 為 `0.8 * in` 並將前 3 位多餘的過濾掉，再加上 `0.2 * in` ( 將值為 `0.1 * in` 的 `div` 左移兩位 ) 使值變為 `1.0 * in` 也就是 `div` 的 10 倍。
```c
#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
uint32_t q = (x >> 4) + x;
x = q;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
*div = (q >> 3);
*mod = in - ((q & ~0x7) + (*div << 1));
}
```
## quiz3 測驗 3
### 程式碼運作原理
使用二分搜尋的技巧，找出 $\log_2i$ 為多少，因此依序填入 65536 , 256 , 16 , 2。
```c
static size_t ilog2(size_t i)
{
size_t result = 0;
while (i >= 65536) {
result += 16;
i >>= 16;
}
while (i >= 256) {
result += 8;
i >>= 8;
}
while (i >= 16) {
result += 4;
i >>= 4;
}
while (i >= 2) {
result += 1;
i >>= 1;
}
return result;
}
```
`__builtin_clz` 的輸入不能為 `0`，因此先將輸入 `v` 和 `1` 做 OR 運算，避免為 `0` 的狀況發生。
```c
int ilog32(uint32_t v)
{
return (31 - __builtin_clz(v | 1));
}
```
## quiz3 測驗 4
### 程式碼運作原理
`avg->internal` 表示 $S_t$，`val << avg->factor` 表示 $Y_t$，`avg->weight` 表示 $\alpha$。
`factor` 用來調整可以顯示到多少的精確度。
```c
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
? (((avg->internal << avg->weight) - avg->internal) +
(val << avg->factor)) >> avg->weight
: (val << avg->factor);
return avg;
}
```
將上面的算式化簡，就會得當與原本公式相符的結果：
$$
S_t = 2^{-weight}Y_t + (1 - 2^{-weight})S_{t - 1}
$$
## quiz3 測驗 5
```c
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 = 0 的狀況，並仍是 branchless
讓程式一開始依據 x 是否為 0 做減法，避免 unsinged integer 減到小於 0 後出現錯誤。
最後回傳時也判斷 x 是否為 0，決定是否加 1。
```diff!
- x--;
+ x -= (x > 0);
...
- return (r | shift | x > 1) + 1;
+ return (r | shift | x > 1) + (x > 0);
```
## quiz4 測驗 1
### 程式碼運作原理
以每 4 個位元為一個單位計算 1 的個數，利用以下公式計算：
$$
x - \lfloor \frac{x}{2} \rfloor - \lfloor \frac{x}{4} \rfloor - \lfloor \frac{x}{8} \rfloor
$$
將輸入 `v` 右移 1 位 ( 除以 2 )，然後 `& 0x77777777` 的用意是，如果較高位的 4 位在位移之後，右移完要移除的位元會變成低位的第 4 個位元，因此以 `0x77777777` ( `01110111 ... 0111` ) 將這些不需要的位元清除，就可以得到每 4 個位元完整的 $\lfloor \frac{x}{2} \rfloor$。
而這個操作總共用了 3 次，取出 $\lfloor \frac{x}{2} \rfloor$ , $\lfloor \frac{x}{4} \rfloor$ , $\lfloor \frac{x}{8} \rfloor$。
```c
n = (v >> 1) & 0x77777777;
v -= n;
```
使用 `v = (v + (v >> 4))` 會得到：
```
B7 (B7+B6) (B6+B5) (B5+B4) (B4+B3) (B3+B2) (B2+B1) (B1+B0)
```
再使用 `0x0F0F0F0F` 做 mask 得到：
```
0 (B7+B6) 0 (B5+B4) 0 (B3+B2) 0 (B1+B0)
```
與 `0x01010101` 相乘完後會在第 24 個位元後得到 B0 + B1 + ... + B7，因此將結果右移 24 個位元即為結果。
```c
v *= 0x01010101;
return v >> 24;
```
以下程式用來找出每個數之間的 hamming distance，透過 xor 將不同的位元標示成 1，再以 popcount 找出總共有幾個 1，程式中使用了兩層迴圈來計算，因此每一組配對會被重複計算到，所以最後應該要將 `total` 除以 2，也就是右移 1 位。
```c
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;
}
```
### 撰寫更高效的程式碼
1. 第 0 個 bit 觀察 :
全部都是 1 -> Hamming Distance = 0
2. 第 1 個 bit 觀察 :
1 有一個，其餘皆為 0
可以直接用單個 bit 判斷 Hamming Distance (1)* (numsize - 1)
3. 第 2 個 bit 觀察 :
1 有兩個，其餘皆為 0
Hamming Distance (2)* (numsize - 2)
根據以上規則可以整理成以下程式，比起原本的程式碼更有效率，可通過 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/submissions/)：
```c
int total = 0;
for (int i = 0; i < 32; i++) {
int count = 0;
for (int j = 0; j < numsSize; j++)
count += (nums[j] >> i) & 1;
total += count * (numsSize - count);
}
return total;
```
## quiz4 測驗 2
### 程式碼運作原理
$$
popcount(x \& \overline{m}) - popcount(x \& m) = popcount(x \oplus m) - popcount(m)
$$
`popcount(0xAAAAAAAA) = 16` 所以可以得出 `popcount(n ^ 0xAAAAAAAA) - 16`，但為了避免 `n < 0` 所以加上一個 3 的倍數變為 `popcount(n ^ 0xAAAAAAAA) + 23`。
再做下一回合的運算以得到一個小於 3 的數：
```c
n = popcount(n ^ 0x2A) - 3;
```
經過上一回合後，`n` 目前的值介於 `-3 ~ 2`，最後需要針對小於零的狀況加 3，且在原本程式中並沒有將 `n` 從 `unsigned` 轉型成 `int`，由於沒有標示正負的符號，導致 `& 3` 的結果不如預期：
```diff
- return n + ((n >> 31) & 3);
+ return n + (((int)n >> 31) & 3);
```
觀察可移動的方式，`move_masks[0]` , `move_masks[1]` , `move_masks[2]` 為第一排，如果 `board` 與這三個移動方式做 OR 運算，得到 `0x70044444`，可以發現有連成一直線時，會有一個位元被設定成 `7`，為了檢察是否為 `7`，將 `board + 0x11111111` 在和 `0x88888888` 做 AND 運算就可以發現是否有人獲勝。
```c
static const uint32_t move_masks[9] = {
0x40040040, 0x20004000, 0x10000404, 0x04020000, 0x02002022,
0x01000200, 0x00410001, 0x00201000, 0x00100110,
};
/* Determine if the tic-tac-toe board is in a winning state. */
static inline uint32_t is_win(uint32_t player_board)
{
return (player_board + 0x11111111) & 0x88888888;
}
```
先將 `x` 的範圍縮減，`x >> 15` 移除較低的 15 位，`(x & UINT32_C(0x7FFF))` 只保留最低的 15 位。
```c
static inline int mod7(uint32_t x)
{
x = (x >> 15) + (x & UINT32_C(0x7FFF));
/* Take reminder as (mod 8) by mul/shift. Since the multiplier
* was calculated using ceil() instead of floor(), it skips the
* value '7' properly.
* M <- ceil(ldexp(8/7, 29))
*/
return (int) ((x * UINT32_C(0x24924925)) >> 29);
}
```
## quiz4 測驗 3
```
/* The process of deletion in this tree structure is relatively more intricate,
* although it shares similarities with deletion methods employed in other BST.
* When removing a node, if the node to be deleted has a right child, the
* deletion process entails replacing the node to be removed with the first node
* encountered in the right subtree. Following this replacement, an update
* operation is invoked on the right child of the newly inserted node.
*
* Similarly, if the node to be deleted does not have a right child, the
* replacement process involves utilizing the first node found in the left
* subtree. Subsequently, an update operation is called on the left child of th
* replacement node.
*
* In scenarios where the node to be deleted has no children (neither left nor
* right), it can be directly removed from the tree, and an update operation is
* invoked on the parent node of the deleted node.
*/
```
根據函式註解，可以將缺漏的部分補上。
```c
struct xt_node *least = xt_first(xt_right(del));
if (del == *root)
*root = least;
xt_replace_right(del, least);
xt_update(root, xt_right(least));
return;
```
```c
struct xt_node *most = xt_last(xt_left(del));
if (del == *root)
*root = most;
xt_replace_left(del, most);
xt_update(root, xt_left(most));
return;
```
```c
xt_update(root, parent);
```
Sign in with Wallet
Connect another wallet