# 2024 Homework4 (quiz3+4)
## [第 4 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz4)

### 測驗 1

[population count](https://en.wikichip.org/wiki/population_count) 用於計算二進位表示的數值中，有多少位元是 1，常見應例子有 sparse matric 或是 bit array 中非 0 的元素個數和計算兩個字串的 Hamming distance。

popcount_naive 透過不斷清除 LSB ，直到輸入 `v` 為零，以下為實作程式

unsigned popcount_naive(unsigned v)
{
    unsigned n = 0;
    while (v)
        v &= (v - 1), n = -(~n);
    return n;
}

這裡我以輸入 `v` = 111100 和 `v &= (v - 1)` 為例逐步說明

step1 : v = 111100, (v-1) = 111011, 111100 &= 111011 , 此時 v = 111000, n = 1

step2 : v = 111000, (v-1) = 110111, 111000 &= 110111 , 此時 v = 110000, n = 2

step3 : v = 110000, (v-1) = 101111, 110000 &= 101111 , 此時 v = 100000, n = 3

step4 : v = 100000, (v-1) = 011111, 100000 &= 011111 , 此時 v = 000000, n = 4

Output is 4

而二補數系統中 `n = -(~n)` 是等同於 `n++`，我可拆解成以下表示形式

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

這裡我們為 $n = -(\sim n)$ 帶個例子解釋，假設 $n = 0011$，那麼 $\sim n = 1100$，$-(\sim n) = 0100$，$-(\sim n)$ 就是在對 $\sim n$ 的結果加一。