yenshipotato

@yenshipotato

Joined on Jan 14, 2020

  • contributed by < yenshipotato > 閱讀〈因為自動飲料機而延畢的那一年〉的啟發 「謹以這個故事獻給那些試圖打開真理之門的人們,或許回過頭看一切都是徒勞,但只要能夠再站起來,就能抵達任何地方。」 這個故事裡沒有快樂結局,沒有天外救星( Deus ex machina ),只有現實和妥協。這是我在閱讀完全 23 篇文章後獲得的最大收穫。作者在大學四年級時選擇延畢做一個專案,在同學都已經在讀研究所或工作時,全身心投入一個以上帝視角來看沒有未來的計劃,也理所當然地碰到了一堆問題。 :::success 為什麼會出問題呢?因為這裡是他媽的真實世界啊。 大多數人一直活在本來就應該這樣嗎的童話世界裡。 〈因為自動飲料機而延畢的那一年(3)〉
     Like  Bookmark
  • contributed by < yenshipotato > Quiz3 測驗一 解釋程式碼運作原理 首先,m 被初始化為小於或等於 x 的最高 4 的冪。這是通過 bitwise 完成的,即 1UL << ((31 - __builtin_clz(x)) & ~1UL)。 31 - __builtin_clz(x) 可以得到 x 中最高設定位的位置。使用 & ~1UL 清除該位置號碼中的最低有效位,以找到一個偶數位置,從而開始於小於或等於 x 的最高的 4 的冪。這樣可以確保程式從檢查最高有效位開始。函數的主要部分是一個 for 迴圈。在迴圈內部,每次迭代將 m 向右移 2 個 bit ,相當於除以 4。接著,計算 b 為 z + m 。取 z 的一半(即 z >>= 1),這代表我們在前一迭代中已確定的 bits 。之後用 if 來檢查 : 如果 x 大於或等於 b 的情況。這表示當前位應該設置為 1,因為我們可以從 x 中減去 b 而不會導致結果的平方大於原始的 x。如果條件成立,x 減去 b,並把當前位添加到 z 的結果中。這個過程會一直重複,直到 m 變成 0,此時所有可能設置的位都已經檢查過了。最終,結束後的 z 就是原始數字 x 的整數平方根 測驗二 參照《Hacker's Delight》和 CS:APP 第二章,解釋上述程式碼運作原理 根據前述證明得知,在對於小於 20 的非負整數 $tmp$ 而言,對 10 做 div 的整數結果將近似於 $\frac{13}{128}tmp$ 的結果,又 $13 = 8+4+1$ ,因此 $\frac{13tmp}{8}$ 可以 bitwise operation 表示,即:(tmp >> 3) + (tmp >> 1) + tmp)然而右移操作會導致位元資料消失,需要設定變數記憶消失的位元。得出 $13tmp$ 的結果後,右移7位便是 $\frac{13}{128}tmp \approx \frac{tmp}{10}$ 也就是除以 10 的商數。餘數部分,使用 tmp 減去 10 倍商數 (q*4+q)*2 即為結果。
     Like  Bookmark
  • contributed by < yenshipotato > Reviewed by yenslife q_reverse 將走訪到的節點之 prev 與 next 交換 利用 list API 來簡化 q_reverse 實作:其實可以用 list_move 直接將走訪到的節點移到開頭,增加程式碼可讀性。 struct list_head *cur, *next; list_for_each_safe (cur, next, head) {
     Like  Bookmark
  • contributed by < yenshipotato > 2024q1 第 1 週測驗題 - 測驗 1 延伸問題 1.解釋上述程式碼的運作原理 測驗 1 的 quick_sort 使用堆疊 begin 和 end 來保存每個子佇列的範圍,並在迴圈中不斷地處理這些子佇列,直到所有的子佇列都排序好為止。 node_t *begin[max_level], *end[max_level]; 每一次迭代會從堆疊 begin 和 end 中分別取出鏈結串列的起始與結束位置,並將它們分別指派給 L 與 R,這兩者代表著子佇列的起始與結尾。 node_t *L = begin[i], *R = end[i];
     Like  Bookmark