or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
2022q1 Homework4 (quiz4)
contributed by <
cyrong
>測驗
1
在此程式中使用了 4 個數字作為類似 bitmask 的作用
分別是
0xFFFF
,0xFF
,0xF
,0x3
將他們以 2 進位在 32 位元表示的話
0xFFFF
: 0000 0000 0000 0000 1111 1111 1111 11110x00FF
: 0000 0000 0000 0000 0000 0000 1111 11110x000F
: 0000 0000 0000 0000 0000 0000 0000 11110x0003
: 0000 0000 0000 0000 0000 0000 0000 0011以這些數字每次將位元數分成兩半,讓變數
r
紀錄ceil_log2
值中 2 的冪的部份。而
shift
最終會有兩種結果,分別是 0, 2,是在程式碼第 14 行處決定最後的值,shift
會從 0 開始分別在x
的值在 2 的偶數次方之後交替,也就是x
= 2(\(2^0 + 1\)) ~ 4(\(2^2\)),shift
= 0x
= 5(\(2^2 + 1\)) ~ 16(\(2^4\)),shift
= 2x
= 17(\(2^4 + 1\)) ~ 64(\(2^6\)),shift
= 0x
= 65(\(2^6 + 1\)) ~ 256(\(2^8\)),shift
= 2以此類推,
shift
用意在於紀錄r
所紀錄不到的ceil_log2
中 2 的倍數的部份。最後是
x
,x
最終會有三種結果,分別是 1, 2, 3,原因是經過程式碼中 7, 9, 12, 15行,若是符合條件x
將分別被向右移 16, 8, 4, 2位元,因此最終只會存在x
的前兩位元,又因為x
> 1,因此只會有 1, 2, 3 三種可能,觀察這三個值\(1_{10}\) = \(01_{2}\)
\(2_{10}\) = \(10_{2}\)
\(3_{10}\) = \(11_{2}\)
當
x
= 2, 3 時,代表ceil_log2
的值會比x
= 1 時多 1 ,因此在回傳時將x
向右位移以得知x
是否為 2 或 3 。而在 return 的最後的地方 +1 其用意在於取 ceiling 的部份,上述程式碼可以計算出的值為
x
中包含的 2 的指數,也就是說取得的是 \(\lfloor log_2(x) \rfloor\), 但為了避免 2 的指數(\(2^n\))被計算錯誤為 (\(2^{n+1}\)),因此在程式碼最開始有x--
測驗 2
第 16 行先將
shift
往右位移 1 位,因此shift
的值會是BITS_PER_LONG
>> 1 ,也就是 64 >> 1 = 32 ,t
中的值會是前 32 位元為 0 後 32 位元為 1 。而在後面的 while 迴圈中,每次將
shift
向右位移 1 位、t
向右位移shift
位,這樣的操作下會把t
的位元中 1 的個數每次減半while 迴圈中對於
x
,o
的操作則是用t
判斷x
中值為 1 最低位元位置,若是
x & t
== 0 代表x
中值為 1 的最低位元在t
的位元中的左半邊 0 的區域,這時就將x
向右位移shift
位並且將o
+=shift
,也就是將x
中在最低位元為 1 右側的shift
個 0 給消除,並用o
將消除掉的個數進行紀錄。最終會紀錄下消除掉的 0 的個數,但因為
ffs
要尋找的是第一個 1 的位置,因此o
的初始值為 1。測驗 3
測驗 5