contributed by < lorian0738
>
一個字元 1 byte (位元組)
') // 得到 'a'
') // 得到 'a'_
') // 得到 'A'_
') // 得到 'A'
') // 得到 'A'
') // 得到 'a'在 boot manager 或 boot loader 資源有限
主記憶體可能不能用
sizeof
不是 function 是 operator (運算子)
=> 回傳型態:unsigned interger
整數型態和 unsigned interger 做運算時,會整個變成 unsigned interger
考慮 next_pow2 可針對給定無號 64 位元數值 x,找出最接近且大於等於 2 的冪的值,例如:
上述程式碼將 x 和自己右移的值做 bitwise or 運算,目的是希望將比 x 的 MSB 低位的數字都變成 1,因此總共右移了 63 個位元,如此再 +1 進位後就會是想找的 2 的冪的值
疑惑點:
題目描述要找「最接近且大於等於 2 的冪的值」指的應該是最接近 x 且大於等於 x 的 2 的冪的值,但若是 x 本身就是 2 的冪,例如 1000₂ ,做完運算後會得到 10000₂ ,但依照題目敘述應該求的是 1000₂
int __builtin_clzl (unsigned long) 會回傳前導 0 的位數,例如 input 為 9 (1001₂) 時,回傳 64 - 4 = 60
則可以知道最高有效位在最低位往高位數第 4 位,可知想求的值為 1 左移四個位數,即為 10000₂
經同學提醒,才想到 return 那邊若直接寫 1 會預設是 int ,因此若輸入超過 32 位元的值會溢位,需要特別標示型別為 uint64_t
。
提示: 可執行 cc -O2 -std=c99 -S next_pow2.c 並觀察產生的 next_pow2.s 檔案,確認 bsrq 指令 (表示 “Bit Scan Reverse”)
LeetCode 1680. Concatenation of Consecutive Binary Numbers 給定一整數 n ,回傳將 1 到 n 的二進位表示法依序串接在一起所得到的二進位字串,其所代表的十進位數字 之值。
此程式碼將 1 到 n 依序串接進 ans,若 i & (i-1)
為 0,表示 i 為 2 的冪,則 i 比 i - 1 的位數多一位,ans 在左移準備串接 i 時,要比串接 i - 1 時多左移一位,因此將記錄左移位數的 len + 1。
再利用左移足夠位數後填補的 0 的部分,與要串接的數字做 bitwise or 達到二進位制相加的效果。
例如當 n 為 4 時:
SWAR 實作如下:
首先把字串轉為 uint64_t 的形式存在 *qword
接著 len >> 3 即為 len / 8,長度除以 8 (無條件捨去到整數位) 可知該字串有幾個 8 bytes(64 bits) 一組,加上 qword 可得最後一組的位址
題目中提到:
若輸入的字串是一個有效的 UTF-8 序列,則計算其中的後續位元組數量,並將此數字從總字串長度中減去,即可確定字元數量。
後續位元組的位原模式如題目所述為 not bit6 and bit7
因此接著跑 for 迴圈一次處理 64 個位元,計算想求的後續位元組數量:(如測驗題目說明)
再來將算出來的數字 count 用總字串長度減去
而須注意的是目前只做了可以 64 bits 一組處理的部分,也就是這裡的總長度不應該用原本字串的總長度,而是要先用 len / 8 計算做了幾組,再乘 8 (1 << 3),算出目前已計算的總長度,再減去 count
最後計算有沒有多出來不能 64 bits 一組一起算的部分,以 len & 7 判斷,也就是 len % 8,若有的話再用 count_utf8 計算並加進 count,其長度為 len & 7,也就是以 8 bytes 為一組剩餘的長度;若沒有的話就加 0。
判定 16 位元無號整數是否符合特定樣式 (pattern):
可以看出符合程式碼的樣式:
可觀察到從最左邊開始為連續的 1 ,接著是連續的 0
更精簡的程式碼:
這種樣式下將 x 做 bitwise not 會將原本的 1 變成 0、0 變成 1,例如:1111 0000 0000 0000
變成 0000 1111 1111 1111
,加一後變成 0001 0000 0000 0000
,與 x 做 bitwise xor 後會將 x 最低位的 1 去掉,得到比 x 小的值。
而若非此樣式的,例如 1101 0000 0000 0000
,非連續 1 接上 0,bitwise not 後會變成 0010 1111 1111 1111
,加 1 後變成 0011 0000 0000 0000
,會有兩個位數是 1 ,再做 bitwise xor 會變成 1110 0000 0000 0000
反而會進位。
而 1 接上非連續 0 的情況,例如 1111 0001 0000 0000
,bitwise not 再加一後會變成 0000 1111 0000 0000
,也會有不只一個位數是 0,做 bitwise 後會變成 1111 1110 0000 0000
,數值也會比較大。
可知只有連續 1 接連續 0 的情況下作這些操作後可去掉最低位的 1 ,得到比原本更小的數值。