# 2024q1 Homework2 (quiz1+2)
contributed by < [jouae](https://github.com/jouae) >

## [2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)

### 快速排序：原理
1. 選定[樞元（ pivot ）](https://terms.naer.edu.tw/detail/b419dcc83a54a91387c7a2365d870acf/?startswith=zh&seq=6)
2. 設定左索引為序列開端與右索引序列尾端，藉由左右索引對應值比較樞元大小選定分割位置，切割出大於等於樞元的元素構成的子序列及小於的元素構成的子序列。
3. 根據兩個子序列重複上述行為。

### 快速排序：空間複雜度
在測驗題中的原始碼，堆疊大小的上限設定串列長度的兩倍。

* Worst case
* Best case
* Average case

## [2024q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)

### find first bit set
> [commit 77f2ec9](https://github.com/jouae/clab/commit/77f2ec9574c5d029a95b0736c317cb9cb9eb2229)

根據控制句 (control statement) 成立時， `num+=32` 跟 `word>>=32` ，bitmask `AAAA` 的作用就是確認 `word` 前 32 個 bit 中是否有包含 `1`，舉例來說：

word =
0000 0010 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000

可以看出後 32 個 bit 中沒有出現 `1` 所以和 bitmask `AAAA` AND運算得到 `0` 且 `num+=32` 後 `word` 左移 32 位元。而 16 進位表示中 `f` 佔有 4 個位元表示，故 bitmask `AAAA` 為 `0xffffffff` ，表示其是對 4*8=32 個位元做位元操作。
## 參考資料
* [作業說明](https://hackmd.io/@sysprog/BkmmEQCn6)