contributed by <rwe0214
>
rwe0214
題目:
給定 B 為 2 的某次方 (power of 2),那麼是否 A % B 會等價於 (A & (B - 1))?
(a) 是
(b) 否
延伸問題:
想法 & 思考
從取餘數這個角度出發,一開始我先以十進位來做思考,假設我們要取某數 A 除以 power of 10 的餘數,我們很自然就會把 A 的個位數往前數幾個 B 的次方值。
e.g. 12345 除以 10 的餘數就是從十進制的個位開始取兩個數 45。
回到題目並以二進位的角度來看:
e.g. 123 = 1111011 除以 2 的餘數就是從二進制的個位開始取四個數 1011 = 11
所以我們可以確定了一件事,當取 power of 2 的餘數時,擷取被除數之次方個位數即可。接著我們來看 power of 2 的二進制表示
2 = 1000, 2 - 1 = 0111
2 = 100000, 2 - 1 = 011111
由上面可以看出 (power of 2) - 1 的值剛好在我們想要擷取的位元上都是 1,反之都是 0,如此一來便可以透過 bit mask 的手法將我們的所求位元求出,即題目所述 (A & (B - 1))!
在電腦科學裡,計算 memory 分配進哪一個 cache block 的 index 和 tag 值手法也類似於本題的求餘數。根據 cache 的關聯度 (power of 2) 去分割 memory address bits。
e.g. 一個關聯度為 4 的 cache,假設一個 set 有 4 個 blocks,且一個 block 是以四個 位元祖為單位
某一 memory address 為 m 的資料被放進 cache 時,其 index = m / (set size) / 關聯度,tag = (m / (set size)) % 關聯度。
所以 cpu 在計算上也可以直接使用 bit-operator 來求得答案。
題目:
完成 float / 2 的程式碼 :
想法 & 思考
首先我把程式碼分成三個部份:
IEEE754 數字分類:
基於以上規則,A1 ~ A6 的答案也呼之欲出了!
而 A1 ~ A6 之中最讓我感興趣的部份則是 A3 和 A4:
如果根據註解來推論這個部份應該是除以 2 之後會是 denormalized 數,而 denormalized 的 exp 值固定為 0,既然這樣為什麼還要大費周章的使用一些運算來求得 exp 呢?
於是我假設有一種情形,一個 normalized 經過以上運算,它確實有可能變成 denormalized,但是最後的結果卻還是 normalized ,先猜測,是這個條件下的最大值。
取二個數其 IEEE754 表示法分別為
0 00000001 11111111111111111111111
和
0 00000001 11111111111111111111110
並分別紀錄 3,4,5 行並比較其執行結果為
和
哦!抓到了!原來真的有特例會在最後結果仍為 normalized!
所以為了為了保持其正確性才把這部份使用運算來計算而不是直接 assign 為 0。
題目:
預期會得到
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -
填補以下程式碼使得輸出為
1 -> 2 -> 3 -> 4 -> 5 ->
並且包含換行符號 ( \n )
想法 & 思考
這題當初在測驗的時候因為前面幾題花費較多時間,所以最後沒有時間作答。
不過這題的題目乍看之下很複雜,但是把遞迴展開一些後,便能豁然開朗。
以要填補的程式碼為例,展開幾項後:
由以上過程可得知若要包含最後的換行符號 ( \n ),則 p(1,10) 必須回傳 true,所以 Q1 為 ~p!