contributed by [dcciou](https://github.com/dcciou) # Q3 ## 測驗1:計算開平方根 這個問題考查的是如何計算一個整數的開平方根。給定的演算法透過逐位試探的方法逐漸逼近真實的平方根值。第一個版本使用了 log2(N) 來確定最高有效位，而第二個版本則透過位移操作逐漸找到最高有效位。這種方法的關鍵在於逐步縮小搜尋範圍，每次迭代都將可能的平方根值的範圍減半，直到找到精確的平方根值或最接近的整數值。 ## 測驗2:字串加法的最佳化 這個問題探討了在執行字串加法時如何最佳化效能。在給定的程式碼中，透過逐位計算和進位的方式將兩個數字字串相加。最佳化的關鍵在於減少因除法和模運算帶來的效能開銷。透過一次性計算除以10的商數和餘數來避免直接的除法和modulus運算，從而提高演算法的效率。 ## 測驗3:計算以2為底的對數 這個問題的核心在於使用位元操作而不是循環來計算以2為底的對數。透過檢查整數的位元表示，可以直接得出其以2為底的對數。例如，如果整數是16（二進制10000），它的以2為底的對數是4。使用GCC內建的__builtin_clz函數（計算前導零的數量）可以快速實現此計算。 ## 測驗4:指數加權移動平均（EWMA） EWMA 是一種統計手段，這種演算法通常用於平滑時間序列數據，其特點是最近的數據點有更高的權重，而舊數據的權重指數級則減少。這個問題檢查了如何實現 EWMA 的計算，主要挑戰在於如何在不損失精度的前提下處理權重的遞減以及平均值的更新。 ## 測驗5:位元操作和除法優化 與測驗 2 類似，這個問題也是關於如何透過位元操作來最佳化原本需要透過除法和modulus運算實現的計算。透過巧妙的演算法設計，可以利用位元操作來逼近除法的結果，從而減少計算成本，提高效能。 # Q4 ## 測驗1:Population Count (Popcount) Popcount 函數的目的是計算一個數值的二進位表示中有多少位是 1。這對於稀疏矩陣的處理或是計算兩個字串的 Hamming 距離等應用非常有用。 popcount_naive 透過不斷清除最低位的 1 直到數值變成 0，計算其中 1 的數量。 popcount_branchless 是一種無分支的實作方式，透過一系列的位元操作，能在常數時間複雜度內計算 popcount 值。 ## 測驗2:Remainder by Summing Digits 這個問題探討如何透過和位元運算結合的方式，不用除法就能計算一個數除以另一個數的餘數。這依賴於除數滿足特定條件，透過位元操作和 population count 函數來實現。這種方法展示了位元操作在算術運算中的強大用途，尤其是在性能敏感的應用中。 ## 測驗3:XTree 和 Linux 核心的紅黑樹 XTree 是一個嘗試結合 AVL 樹和紅黑樹部分特性的二元搜尋樹（BST）實現，重點在於快速的插入/刪除操作和合理的查找速度。它使用 hint 作為平衡因子來決定是否需要旋轉，hint 的更新僅在呼叫 xt_update 時進行。這種設計反映了對現有樹結構平衡機制的最佳化嘗試，旨在找到插入/刪除和查找速度之間的最佳平衡點。