2025q1 Homework4 (quiz3+4)

contributed by < weiso131 >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

第三周測驗一

填空

• AAAA: (n + d - 1) / d
• BBBB: 0x7fffffff
• CCCC: n + m
• DDDD: 1
• EEEE: mpi_gcd(rop, op2, r)

解釋程式碼原理

mpi_set_u64

將 uint64_t 的數值每 31 bit 做儲存，不直接使用 64 bit 是為了避免運算過程中因為溢位造成的問題。

mpi_mul_naive

可以把它想成

$2^{31}$ 進位的乘法運算

mpi_fdiv_qr

類似二進位的長除法運算
將被除數的值逐個 bit 複製到 r 並左移一格
若 r > d0 代表商的第 i 個 bit 是 1

第三周測驗二

填空

• AAAA: X ^ mask
• BBBB: mask << i
• CCCC: *asrc

解釋程式碼

DETECT_NULL

0x00 < 字元 <= 0x80

減去 0x01 之後第一個位元是 0 ， 會被 0x80 這個 bit mask 阻擋掉變成 0x00

字元 > 0x80

減去 0x01 之後第一個位元仍是 1 ， 不會被 0x80 擋掉 ， 但對原本的字元進行反碼之後，第一個位元會是 0 ， 做了 AND 操作之後就會變阻擋

字元 == 0x00

減去 0x01 之後是 0xff
0x00 反碼也會是 0xff ， 進行 AND 運算後沒影響
最後與 0x80 運算後變成 0x80

memchr_chr

• 將 str 轉換成 unsigned long ， 之後就可以一次檢查 sizeof(unsigned long) 個 byte
• mask 是將 c 填滿 unsigned long 長度的每個 byte ，然後原本的寫法會在 sizeof(unsigned long) >= 8 的時候利用迴圈再將 mask 做進一步的填充，這邊其實可以改成
  ​​​​mask = d;
  ​​​​for (unsigned int i = 8; i < LBLOCKSIZE * 8; i <<= 1)
  ​​​​    mask |= mask << i;
  

• DETECT_CHAR 裡面將 X 與 mask 做 XOR ， 如果 X 裡面存在 c 該 byte 就會變成 NULL ， 此時就能使用 DETECT_NULL
• 最後用 while 迴圈檢查 c 實際出現的位置
  • 若 len >= sizeof(unsigned long) 且 c 存在於 str ，此時 src 已經被設定成 asrc ，迴圈至多跑 sizeof(unsigned long) 會找到實際位置
  • 若 len < sizeof(unsigned long) ，則會對 str 逐一檢查 c 是否存在
  • 若 str 不存在 c ， 回傳 NULL

# 第三周測驗三 ## 填空 - `AAAA`: `ENV_RUNNABLE` - `BBBB`: `attempts + 1` - `CCCC`: `coro_schedule` - `DDDD`: `coro_schedule` 錯了

第四周測驗一

• AAAA: 0xc38d26c4
• BBBB: 0xd3d3e1ab
• CCCC: 0xe330a81a
• DDDD: 0xf36e6f75
  

不要列出參考題解，專注題目本身