祕密

祕密

學習練習

簡介

二進位數字最終直接對應到你 CPU 或 RAM 中的電晶體,以及每一個電晶體是「開啟」還是「關閉」。

低階操作,也就是俗稱的「位元操作」,在系統程式語言中特別重要。

像 Julia 這樣的高階語言通常會把這些細節抽象掉。 不過,基礎語言本身就提供了完整的位元層級運算。

注意: 若想在 REPL 中看到人類可讀的二進位輸出,下面幾乎所有範例都需要用 bitstring() 函式包起來。 這樣在視覺上很干擾,所以這個函式的出現大多已經被省略了。

位元位移運算

整數型別,無論是有號還是無號,都可以表示成一串 1 和 0。

julia> bitstring(UInt8(5))
"00000101"

位元位移只是把所有的位元向左或向右移動指定的位置數。 使用 UInt 型別時,有些位元會從一端掉落,另一端則補上零:

julia> ux::UInt8 = 5
5

julia> bitstring(ux)
"00000101"

julia> ux << 2 # left by 2
"00010100"

julia> ux >> 1 # right by 1
"00000010"

每次左移會讓值加倍,每次右移則會減半(可能被截斷)。 這在十進位表示法下更明顯:

julia> 3 << 2
12

julia> 24 >> 3
3

這種位元位移比「正規」的算術快得多,因此這個技巧在低階程式設計中非常受歡迎。

處理有號整數時,我們得稍微小心一點。

左移相對簡單:

julia> sx = Int8(5)
5

julia> sx # positive integer
"00000101"

julia> sx << 2
"00010100"

julia> -sx # negative integer
"11111011"

julia> -sx << 2
"11101100"

因此,對正的有號整數左移,和對無號整數左移是一樣的。

負值以二補數形式儲存,這表示最左邊的位元是 1。 左移沒問題,但右移時,最左邊的位元要怎麼補呢?

julia> sx >> 2 # simple for positive values!
"00000001"

julia> -sx # negative integer
"11111011"

julia> -sx >> 2 # pad with repeated sign bit
"11111110"

julia> -sx >>> 2 # pad with 0
"00111110"

>> 運算子執行算術位移,會保留符號位元。

>>> 運算子執行邏輯位移,補上零,就像這個數字是無號的一樣。

位元邏輯

我們在前面某個概念中看到,運算子 &&(and)、||(or)和 !(not)用於布林值。

也有對應的運算子 &(位元 AND)、|(位元 OR)和 ~(波浪號,位元 NOT),可以用來比較兩個整數中的位元。

julia> 0b1011 & 0b0010 # bit is 1 in both numbers
"00000010"

julia> 0b1011 | 0b0010 # bit is 1 in at least one number
"00001011"

julia> ~0b1011 # flip all bits
"11110100"

julia> xor(0b1011, 0b0010) # bit is 1 in exactly one number, not both
"00001001"

這裡的 xor() 是互斥或,以函式的形式使用。

說明

你的朋友剛傳了一則訊息給你,裡面有個重要的秘密。 他不想讓別人輕易讀懂,所以把訊息經過一連串的位元操作加密了。 你需要撰寫函式來協助解密這則訊息。

1. 將位元移回去

解密訊息的第一步,就是把加密時做的移位還原,將位元往右移回去。 解密過程後續還有一些步驟,會假設是從左側補進 0。

實作shift_back()函式,它接受一個值和要移位的位數,並執行移位。

shift_back(0b1001, 2) # => 0b0010

2. 設定一些位元

接下來,有些位元需要設為 1。

實作set_bits()函式,它接受一個值和一個遮罩,並回傳把值中的位元設為 1 的結果。 當 mask 中的某個位元是 1 時,value 中對應的位元也應該設為 1。 其他所有位元則保持不變。

set_bits(0b0110, 0b0101) # => 0b0111

3. 翻轉特定的位元

加密時有些位元會被翻轉。 要解密訊息,就得把它們翻轉回來。

實作flip_bits()函式,它接受一個值和一個遮罩。 遮罩指出值中哪些位元要翻轉。 如果 mask 中的位元是 1,value 中的該位元就會被翻轉。 其他所有位元則保持不變。

flip_bits(0b1100, 0b0101) # => 0b1001

4. 清除特定的位元

最後,還有一些特定的位元解密後一定是 0。

實作clear_bits()函式,它接受一個值和一個遮罩。 當遮罩中的位元是 1 時,value 中對應的位元應設為 0。 其他所有位元則保持不變。

clear_bits(0b0110, 0b0101) # => 0b0010
透過 GitHub 編輯 連結會在新視窗或分頁中開啟
Julia Exercism

準備好開始 祕密 了嗎?

註冊 Exercism,透過 35 個概念128 個練習 和真人引導來學習並精通 Julia,全部免費。