HackMDLinux 核心專題: Data Lab
Reviewed by Daniel-0224
改為使用 diff 才能顯示出增加及刪減的程式碼。
Reviewed by david965154
直接回傳 0X55555555 應該也可以
int 在 16 位元系統中並不適用直接回傳 0X55555555
參考 : Integer (computer science)
任務簡介
針對 CS:APP 的 Data Lab，提出有效的解法，規範：
- 自 GitHub 上 fork datalab，依據 Data Lab: Manipulating Bits，補完欠缺的程式碼，並且通過自動測試
- 確保儘可能少的指令，可用
$ gcc -S bits.c輸出組合語言並觀察bits.s的程式碼裡頭的 x86 指令 - 避免用分支 (branch)，設計時間複雜度為 \(O(1)\) 的實作
- 確保儘可能少的指令，可用
- 選出其中 7 個位元操作的函式，詳細解釋其原理，需要比照 clz 應用 和 bit-reverse 的分析方式，舉出真實世界中的應用案例 (最好在 Linux 核心找出相關程式碼)，解說應搭配有效的測試程式碼
- 探討讓 datalab 得以 64-bit friendly 的提案，並舉出實際程式碼修改
參考資訊:
TODO: Data Lab 解題
確保儘可能少的指令
absolute value
int mask = x >> 31;
bit 的翻譯是「位元」，而非「位」，後者是量詞。
sign bit 的翻譯是「正負號位元」，避免濫用「符」這字。
參閱教育部重編國語詞典的「符」的解釋。
將 x 右移 31 個位元，得到正負號位元。若 x 為負數，mask 為 0xFFFFFFFF（即 -1）；若 x 為正數，mask 為 0x00000000。
return (x ^ mask) - mask;
x ^ mask：如果 x 為負數，這將對 x 進行位元取反（相當於 ~x）；如果 x 為正數，這將保持 x 不變。
-mask：如果 x 為負數，這將再加 1，完成補數運算；如果 x 為正數，則減 0，則不會改變值。
addOK
避免僅進行程式碼逐行解說 (ChatGPT 也會！)，而是你該從程式碼設計者的角度，闡述「你為何當初想要這樣作？」「更早之前我嘗試用別的方式，遇到什麼問題」等高階想法，避免淪落為「舉燭」。
int sx = x >> 31; 和 int sy = y >> 31;
取得 x 和 y 的正負號位元。若 x 為正，sx 為 0；若 x 為負，sx 為 -1（即所有位元都為1）。
int sum = x + y;
計算 x 和 y 的和。
int ss = sum >> 31;
取得 sum 的正負號位元。
int same_sign = !(sx ^ sy);
檢查 x 和 y 的正負號位元是否相同。若相同，則 same_sign 為 1；否則為 0。
int overflow = (sx ^ ss);
檢查 x 的正負號位元與 sum 的正負號位元是否不同。如果不同，則 overflow 為 1；否則為 0。
return !(same_sign & overflow);
如果 same_sign 和 overflow 都為 1，表示發生了溢出，回傳 0；否則回傳 1。
allEvenBits
避免僅進行程式碼逐行解說 (ChatGPT 也會！)，而是你該從程式碼設計者的角度，闡述「你為何當初想要這樣作？」「更早之前我嘗試用別的方式，遇到什麼問題」等高階想法，避免淪落為「舉燭」。
int mask = 0x55555555;
定義一個位元遮罩，其所有偶數位元為1。
(x & mask)
將 x 和 mask 進行位元運算，保留 x 中的所有偶數位元。
((x & mask) ^ mask)
將結果與 mask 進行異或運算。如果 x 的所有偶數位元都是1，則 (x & mask) 應該等於 mask，因此異或的結果為0。
!((x & mask) ^ mask)
將異或的結果取反。如果異或結果為0，則表示 x 的所有偶數位都為1，取反後得到1；否則得到0。
anyEvenBit
避免僅進行程式碼逐行解說 (ChatGPT 也會！)，而是你該從程式碼設計者的角度，闡述「你為何當初想要這樣作？」「更早之前我嘗試用別的方式，遇到什麼問題」等高階想法，避免淪落為「舉燭」。
int mask = 0x55555555;
定義了一個位元遮罩，其所有偶數位元為 1。
(x & mask)
將 x 和 mask 進行位元運算，保留 x 中的所有偶數位元。
!!(x & mask)
將結果進行邏輯非運算兩次。第一次邏輯非將非零值轉換為 0，將零值轉換為 1。第二次邏輯非將其結果再次取反，即將非零值轉換為 1，將零值保持為 0。最終，如果有任意一個偶數位為 1，則回傳 1；否則回傳 0。
anyOddBit
避免僅進行程式碼逐行解說 (ChatGPT 也會！)，而是你該從程式碼設計者的角度，闡述「你為何當初想要這樣作？」「更早之前我嘗試用別的方式，遇到什麼問題」等高階想法，避免淪落為「舉燭」。
int mask = 0xAAAAAAAA;
定義一個位元遮罩，其所有奇數位為1。
(x & mask)
將 x 和 mask 進行位元運算，保留 x 中的所有奇數位元。
!!(x & mask)
將結果進行邏輯非運算兩次。第一次邏輯非將非零值轉換為0，將零值轉換為1。第二次邏輯非將其結果再次取反，即將非零值轉換為1，將零值保持為0。最終，如果有任意一個奇數位為1，則回傳1；否則回傳0。
bang
這一題可以用到的特性 Tmax + 1 = 0
x | (~x + 1)
~x + 1 計算 -x（即 x 的二進位補數表示）。
對於非零的 x，x 和 -x 至少一個最高位元（正負號位元）為 1，因此 x | -x 的最高位元為 1。
((x | (~x + 1)) >> 31)
右移 31 位元，將正負號位元移到最低位元。若最高位元為 1，結果為 -1（即所有位元都為1）；若最高位元為 0，則結果為 0。
+1
取反加 1（或簡單取反即可）。對於非零的 x，((x | (~x + 1)) >> 31) + 1 將給出 0；對於 0，結果為 1。
bitAnd
這題參考笛摩根定律
bitCount
逐步計算 1 的個數
避免僅進行程式碼逐行解說 (ChatGPT 也會！)，而是你該從程式碼設計者的角度，闡述「你為何當初想要這樣作？」「更早之前我嘗試用別的方式，遇到什麼問題」等高階想法，避免淪落為「舉燭」。
使用遮罩和移位操作逐步累積每組的 1 的個數。
x = (x & mask1) + ((x >> 1) & mask1); ： 每 2 個位元為一組，計算每組的 1 的個數。
x = (x & mask2) + ((x >> 2) & mask2); ： 每 4 個位元為一組，計算每組的 1 的個數。
x = (x & mask4) + ((x >> 4) & mask4); ： 每 8 個位元為一組，計算每組的 1 的個數。
x = (x & mask8) + ((x >> 8) & mask8); ： 每 16 個位元為一組，計算每組的 1 的個數。
x = (x & mask16) + ((x >> 16) & mask16); ： 每 32 個位元一組，計算每組的 1 的個數。
bitMatch
若位元 x 和 y 在某個位置相同，結果遮罩的該位置應為 1，否則應為 0。
int sameBits = x & y;
計算 x 和 y 中相同位元的情況。
int diffBits = ~x & ~y;
計算 x 和 y 中不同位元的情況。
遇到位元配對題型可以聯想到 xor、xnor 來輸出，但題目限制所以可以試著拆解
特性:
xor 奇數一為一，偶數一為零
xnor 偶數一為一，奇數一為零
這邊用 xnor 來實作看看
\(Y = \overline{A \oplus B}\)
\(Y = A \cdot B + \overline{A} \cdot \overline{B}\)
但題型不能使用 or 閘，改成
\(Y = \overline{\overline{A \cdot B} \cdot \overline{\overline{A} \cdot \overline{B}}}\)
\(=>\)
\(Y = \overline{\overline{sameBits} \cdot \overline{diffBits}}\)
bitNor
\(Y = \overline{A+B}\)
\(Y = {\overline{A}} \cdot {\overline{B}}\)
bitOr
\(Y = A+B\)
\(Y = \overline{\overline{A+B}}\)
\(Y = \overline{\overline{A}\cdot\overline{B}}\)
bitParity
利用異或運算來逐步減少 x 中 1 的個數，直到只剩下一個 1。如果最終結果為 1，則表示 x 中包含奇數個 0，否則表示包含偶數個 0。
x ^= x >> 16;：將 x 右移16位，與原來的 x 異或，將高16位和低16位進行異或。
x ^= x >> 8;：將 x 右移8位，與上一步結果異或，將高8位和低8位進行異或。
x ^= x >> 4;：將 x 右移4位，與上一步結果異或，將高4位和低4位進行異或。
x ^= x >> 2;：將 x 右移2位，與上一步結果異或，將高2位和低2位進行異或。
x ^= x >> 1;：將 x 右移1位，與上一步結果異或，將高1位和低1位進行異或。
return x & 1;：檢查最終 x 的最低位元是否為 1，如果是則回傳 1，否則回傳 0。
bitReverse
將整數分成兩半，交換左右兩半的位元。
繼續將每半部分成更小的部分並交換，直到所有位元都被交換。
x = ((x >> 1) & m1) | ((x & m1) << 1); 交換每一個相鄰的位元。
x = ((x >> 2) & m2) | ((x & m2) << 2); 交換每兩個相鄰的位元。
x = ((x >> 4) & m4) | ((x & m4) << 4); 交換每四個相鄰的位元。
x = ((x >> 8) & m8) | ((x & m8) << 8); 交換每八個相鄰的位元。
x = ((x >> 16) & m16) | ((x & m16) << 16); 交換每十六個相鄰的位。
bitXor(x,y)
| A | B | \[Y=A \oplus B\] |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
\({Y=A\cdot {\overline {B}}+{\overline {A}}\cdot B}\)
在 108 課綱，譯作「笛摩根定律」
第摩根定理 互換
\({Y=\overline{{\overline {A\cdot {\overline {B}}}}\cdot{\overline {{\overline {A}}\cdot B}}}}\)
byteSwap
計算位元組偏移量
n_offset = n << 3;：將 n 左移3位，相當於乘以8，得到第 n 個位元組的偏移量。
m_offset = m << 3;：將 m 左移3位，相當於乘以8，得到第 m 個位元組的偏移量。
擷取位元組
byte_n = (x >> n_offset) & 0xFF;：將 x 右移 n_offset 位，然後與 0xFF 進行與操作，提取第 n 個位元組。
byte_m = (x >> m_offset) & 0xFF;：將 x 右移 m_offset 位，然後與 0xFF 進行與操作，提取第 m 個位元組。
清除和插入位元組
清除第 n 和第 m 個位元組：x = x & ~(0xFF << n_offset); 和 x = x & ~(0xFF << m_offset);
插入交換後的位元組：x = x | (byte_n << m_offset); 和 x = x | (byte_m << n_offset);
tmin()
int 類型是 32 位元，即 4 bytes。二補數最小值就是正負號位元為 1，其餘全為 0。
對 0x1 進行位移運算。
istmax
以 4 bits，二補數表示法演示
| 十進位 | 二補數 |
|---|---|
| 7 | 0111 |
| 6 | 0110 |
| 5 | 0101 |
| 4 | 0100 |
| 3 | 0011 |
| 2 | 0010 |
| 1 | 0001 |
| 0 | 0000 |
| -1 | 1111 |
| -2 | 1110 |
| -3 | 1101 |
| -4 | 1100 |
| -5 | 1011 |
| -6 | 1010 |
| -7 | 1001 |
| -8 | 1000 |
可以看出 0111(7) 為最大值，1000(-8) 為最小值
利用 0111 + 1 會溢出成為 1000 的特性
如果是最大值 0111 與最小值 1000 相加，會等於 1111(-1)
allOddBits
判斷是否有號數 x 的所有奇數位元都為 1
先利用奇數位元遮罩 0xAAAAAAAA 做 & 運算，留下奇數位元，將偶數位元變 0
接著做位元運算 xor，如果奇數位元都是 1 的話會與奇數位元遮罩相等，所以會是 0
如果不是 0，代表奇數位元不全都是 1
negate(x)
二補數，對 x 取反向 +1
ex: 0001(1) 取反 = 1110，加 1 = 1111(-1)
1111(-1) 取反 = 0000，加 1 = 0001(1)
isAsciiDigit(x)
原本想先篩選掉 x 不是 0x3 開頭的, 接著透過 x 減去 9，看是否 >0
但第二段還沒想出怎麼做
看了其他人的解法
設定一個 UpperBound，讓大於 0x39 的數加上它會溢出變成負數
設定一個 LowerBound，讓小於 0x30 的數加上會為負數
將輸入 x 分別加上 UpperBound & LowerBound，右移 31 bit 後與 sign 做 & 操作判斷數值的正負
當有任何一個數為負時，代表超出範圍，!(upperBound|lowerBound) 回傳 0; 反之回傳 1
conditional(x, y, z)
題意為若 X 為真(即非 0 )，則輸出 Y，反之輸出 Z
這邊用兩層反向邏輯判斷 X，如果輸入是非 0，最後 x 會是 0xFFFFFFFFE + 1 = 0xFFFFFFFFF，如果輸入是 0，最後 x 會是 0xFFFFFFFFF + 1 = 溢位 0x00000000，再跟 Y,Z 做位元運算
countLeadingZero?
copyLSB?
x & 1 取得 x 的 LSB。如果 x 的 LSB 是 1，則 x & 1 結果是 1；如果 x 的 LSB 是 0，則 x & 1 結果是 0。
將 x & 1 乘以 -1。如果x & 1 是1，則乘以-1 的結果是-1（在32 位元整數中表示為0xFFFFFFFF）；如果x & 1 是0，則乘以-1 的結果是0（在32 位元整數中表示為0x00000000）。
distinctNegation
對於整數 x，只有當 x = 0 時，x == -x ，因為在二補數表示中，只有零的相反數是它自己。
x != -x：利用比較運算子判斷 x 是否不等於它的相反數。如果 x 不等於 -x，則回傳1；否則回傳0。
dividePower2
int sign = x >> 31;：計算 x 的符號位，如果 x 是正數，sign 為 0；如果 x 是負數，sign 為 -1。
(1 << n) + ~0：計算 \(2^n −1\)，這是為了在對負數 x 進行右移操作之前，先將其調整為向零舍入。
(sign & ((1 << n) + ~0))：根據 sign 的值選擇性地加上 \(2^n −1\)。若 x 是正數，sign 為0，加法不會改變結果；若 x 是負數，sign 為全1，相當於加上
\(2^n −1\)。
\(>>n\)：右移 n 位，實現除以 \(2^n−1\)的操作，同時確保向零舍入捨入誤差。
可以理解成LSB的權重是 \(2^0 = 1\)，所以他是影響 X 是不是奇數的因素，其他位元皆可被 2 整除，所以我們在右移的時候要計算偏移量，將結果 +1
為什麼只有在 X 為負數的時候需要考慮這個問題
右移操作對正數的行為
對於正數，右移操作相當於整數除以 2 的對應次方並向下取整。例如：
上面的程式碼中，9 右移 1 位的結果是 4，相當於 9 除以 2 的 1 次方（向下取整）。
向下取整與向零取整
向下取整和向零取整的差別在於：
向下取整（floor）：結果是小於或等於輸入值的最大整數。
向零取整（truncate）：結果是絕對值較小的整數，也就是直接去掉小數部分。
對於正數，向下取整和向零取整的結果是相同的。
evenBits
直接回傳 0X55555555 應該也可以
ezThreeFourths
int mult3 = (x << 1) + x;：將 x 左移1位元得到 x * 2，再加上 x 得到 x * 3。
int sign = mult3 >> 31;：取得 mult3 的符號位，如果 mult3 是正數，sign 為0；如果 mult3 是負數，sign 為-1。
(mult3 + (sign & 3)) >> 2：
mult3 + (sign & 3)：對於正數 x，(sign & 3) 結果為0，不影響結果；對於負數 x，(sign & 3) 結果為 3，相當於在 mult3 上加上3，用於向零舍入。
\(>> 2\)：將結果右移 2 位，即將 mult3 除以4，
fitsBits?
isLessOrEqual(x,y)
這題要比較 x 是否小於等於 y
我的想法是先比較 x,y 的符號位元
若 x 是負數 sign x 為 1，y 是正數 sign y 為 0，result = 1
若符號位元相同，則再進行減法比較，若 y-x 為正，result = 1
logicalNeg(x)
透過與自身 二補數相加會產生溢位得到 0 的特性完成
除了 0 和最小數的補數是自身，但一樣能透過篩選符號位元完成
howManyBits(x)
b16 = !!(x >> 16) << 4; 檢查高 16 位是否有 1，如果有，b16 為 16。
x = x >> b16; 如果 b16 為 16，則右移 16 位，否則不變。
重複這個過程對 b8、b4、b2、b1 進行檢查和位移。
b0 = x; 獲取剩餘的最低位
將所有計算出的位數加起來，並加上1表示符號位，得到最終的位數。
floatScale2(f)
先提取出指數位的部分，觀察後可發現指數位加 1，就等於乘法 *2
並且透過指數位篩選掉 0、NaN、無窮大、無窮小
floatFloat2Int(f)
過濾出符號位、指數位、尾數位，再去做特殊況處理
如果指數位全為 1，返回 0x80000000u。
若全為 0 直接返回 0。
單精度浮點數的偏置值是 127，因此實際指數為 exp - 127。
如果實際指數小於 0，則浮點數的小數部分在整數為 0
若大於 31，則超出 32 位有號整數的範圍，返回 0x80000000u。
尾數部分加上隱含的 1 位（即 1.xxxxx 變成 1xxxxx），如果指數大於等於 23，則將尾數左移，否則右移。
如果符號位為1，取負值。
floatPower2(x)
單精度浮點數的指數偏置值是 127。
2 的 x 次方的指數表示為 x + 127。
如果 x + 127 小於 0，則結果太小，返回 0。
如果 x + 127 大於 255，則結果太大，返回正無窮大（+INF）。
指數位設置為 x + 127。
尾數位設置為 0，因為 2 的 x 次方的尾數部分為 1.0（隱含位）。
fitsShort?
int sign = x >> 15;：將 x 右移 15 位，得到 x 的最高位（符號位）。
(x >> 15)：得到 x 的符號位的複製。
sign ^ (x >> 15)：如果 x 是正數，則sign 為0，結果為0；如果 x 是負數，則sign 為 -1，結果為 -1；如果 x 的符號位不一致，則結果為 -1。
!(sign ^ (x >> 15))：如果 x 的符號位元和 x 本身在合法範圍內，結果為 1；否則結果為 0。
floatAbsVal
floatInt2Float
sign：記錄 x 的符號位，如果 x 小於 0，則設定為 1，表示負數。
frac：初始化為 x 的絕對值，表示尾數。
exp：初始化為適當的指數值，透過不斷左移 frac 直到最高有效位元為 1 來調整。
u：使用 sign、exp 和 frac 建構最終的單精度浮點數位級表示。
floatIsEqual
NaN 檢測
如果 uf 或 ug 是 NaN（指數位全為1且尾數位非全0），則直接回傳0。
±0 判定
若 uf 和 ug 的位級表示表示均為 ±0，即符號位元和尾數位元均為0，則傳回1。
一般情況比較
將 uf 和 ug 的位元級表示直接進行比較，如果完全相同則回傳1，否則回傳0。
floatIsLess
NaN 檢測
如果 uf 或 ug 是 NaN（指數位全為1且尾數位非全0），則直接回傳0。
±0 判定
如果 uf 和 ug 的位級表示表示均為 ±0，即符號位和尾數位均為0，則回傳0。
符號位比較
如果 uf 和 ug 的符號位不同，可以直接根據符號位來判斷大小關係。
一般情況比較
如果符號位相同，需要比較它們的位級表示來判斷大小關係。
floatNegate
NaN 檢測：透過檢查指數位是否全為 1 且尾數位非全 0 來判斷是否為 NaN。
正負號位元取反：對於非 NaN 的情況，直接透過異或運算 uf ^ 0x80000000 來將正負號位元取反，從而得到 -f 的位級表示。
floatPower2
特殊情況處理：
如果 x 大於 127，則傳回單精度浮點數的正無窮大表示（0x7F800000）。
如果 x 小於 -126，則傳回 0，因為此時 2.0^x 太小無法表示成規格化浮點數。
規格化浮點數處理：
對於處於規格化範圍內的 x，計算 2.0^x 的指數部分，並使用左移操作建立單精度浮點數的表示。
floatScale1d2
特殊情況處理：
如果參數 uf 是 NaN 或無限大（指數部分為 0x7F800000），直接回傳 uf。
規格化浮點數處理：
對於規格化浮點數，首先提取出符號位、指數位和尾數位。
如果是規格化浮點數，則需要將指數部分減去 0x00800000（相當於減去 1），以達到乘以 0.5 的效果。
將調整後的指數和原尾數重新組合成單精確度浮點數的位元級表示。
非規格化浮點數處理：
對於非規格化浮點數（指數部分為 0），直接將尾數右移一位即可達到乘以 0.5 的效果。
floatScale2
特殊情況處理：
如果參數 uf 是 NaN 或無限大（指數部分為 0x7F800000），直接回傳 uf。
規格化浮點數處理：
對於規格化浮點數，首先提取出符號位、指數位和尾數位。
如果是規格化浮點數，需要將指數部分加上 0x00800000（相當於加上 1），以達到乘以 2 的效果。
如果乘以 2 後超過了單精確度浮點數的表示範圍（指數部分超過 0x7F800000），則傳回 +INF。
非規格化浮點數處理：
對於非規格化浮點數（指數部分為 0），直接將尾數左移一位即可達到乘以 2 的效果。
getByte
(n << 3)：將 n 乘以 8 來計算位元組偏移量
x >> (n << 3)：將 x 右移 (n << 3) 位，將位置 n 處的位元組帶到最低有效位元組位置。
& 0xFF：應用遮罩 (0xFF) 來提取最低有效位元組。
howManyBits
如果 x 為 0，則只需要 1 位。
如果 x 是 0x80000000，則需要 32 位元。
透過取其絕對值 (abs_x) 並考慮其符號 (sign_bit) 來標準化 x 。
使用二分查找法確定所需的最小位數：
逐漸檢查更大的位元大小，直到找到在 abs_x 中設定的最高位元。
這涉及到將 abs_x 右移 2 的冪並檢查結果數字是否非零。
根據abs_x中最高設定位的位置決定所需的位數。
如果 x 為負，則調整結果以考慮正負號號位元。
implication
intLog2
isEqual
isLessOrEqual
isNegative
isNonNegative
isNonZero?
isNotEqual
isPallindrome
鏡像結構（mirroredX）：
將 mirroredX 初始化為0。
迭代 originalX 的每一位：
提取 originalX 的最低有效位。
將 mirroredX 向左移動一位後，將此位元附加到 mirroredX。
將 originalX 右移一位以處理下一位。
比較 (!(mirroredX ^ x))：
使用 XOR (^) 將 MirroredX 與 x 進行比較。
如果 mirroredX 等於x，則表達式 mirroredX ^ x 將得到0。
應用邏輯非 (!) 將結果轉換為 1（如果相等）或 0（如果不相等）。
isPositive
isPower2
(x & (x - 1)) == 0：
檢查 x 是否恰好有一位元為 1。按位與運算 x & (x - 1) 將得到 0。
(x > 0)：
確保 x 為正數，因為負數不能是 2 的冪。
邏輯非（！）：
如果 x 是 2 的冪，則將 (x & (x - 1)) == 0 && (x > 0) 的結果轉換為 1，否則轉換為 0。
isZero
leastBitPos
(~x + 1)：
~x + 1 有效隔離 x 的最低有效 1 位元並將所有較低位元設為 0。
(x & (~x + 1))：
此操作會產生一個掩碼，其中僅 x 的最低有效 1 位元被設定為 (1)，所有其他位元均為 0。
logicalShift
1 << 31 建立僅設定正負號位元 (0x80000000) 的遮罩。
\(>> n\) 將此遮罩右移 n 個位置，以與算術移位中移動的位置數對齊。
\(<< 1\) 將其左移 1 個位置以建立一個遮罩，該遮罩清除算術移位期間從左移入的位元。
~ 補充遮罩以準備按位 AND。
對算術移位結果套用遮罩（&mask）會清除從左移入的位元
maximumOfTwo
minimumOfTwo
minusOne
multFiveEighths
(x << 2) + x 使用左移 (<<) 乘以 4，然後加上 x 來計算 x * 5。
mult5 >> 3 透過右移 (>> 3) 來計算 (x * 5) / 8，這相當於除以 8。
isNegative 計算 x 是否為負數（負數為 0xFFFFFFFF，否則為 0）。
adjustment 是僅當 x 為負 (isNegative) 且 x * 5 除以 8 (mult5 & 7) 的餘數非零 (&& 1) 時才應用的校正項。
oddBits
遮罩為 0xAA，表示二進位模式 10101010，覆寫最低有效位元組。
oddMask 將該遮罩與自身左移 8 位元結合，產生 0xAAAA，覆蓋 32 位元結果的前 16 位元。
最後，oddMask 與自身組合左移 16 位元以覆蓋所有 32 位，得到 0xAAAAAAAA（二進位 10101010101010101010101010101010）。
oddMask 將該遮罩與自身左移 8 位元結合，產生 0xAAAA，覆蓋 32 位元結果的前 16 位元。
最後，oddMask 與其自身組合左移 16 位以覆蓋所有 32 位，得到 0xAAAAAAAA（二進位 10101010101010101010101010101010）。
remainderPower2
replaceByte
shift = n << 3 計算到達 x 中的位元組 n 所需的位移位。
mask = ~(0xFF << shift) 建立一個掩碼，其中除了與位置 n 處的位元組相對應的位元外，所有位元均已設定。
Clear_x = x & mask 透過與遮罩的逆值進行「與」操作來清除 x 中位置 n 處的位元組。
replacement = c << shift 將位元組 c 移至位置 n。
返回clear_x | replacement 使用位元或將cleared_x（位置n處的位元組清除）和replacement（將位元組c插入位置n）組合起來。
rotateLeft
shift_mask: ((0) << n) 建立一個遮罩，其中最右邊的 n 位元為 1，擷取將旋轉到最左側的位元。
rotate_mask: ((0) << (32 - n)) 建立一個遮罩，其中最左邊的 n 位為 1，捕獲將從最左側環繞到最右側的位元。
rotated_bits: (x >> (32 - n)) & shift_mask 透過將 x 右移 (32 - n) 個位置並應用 shift_mask 來隔離這些位，從而提取將旋轉到最左側的位。
結果：(x << n) | rotated_bits 透過將 x 向左移動 n 個位置來執行左旋轉，然後將其與rotated_bits 進行「或」(|) 運算，以將旋轉後的位元與移位後的 x 組合起來。
rotateRight
satAdd
sum：計算 x 和 y 的總和。
溢位：透過檢查 x、y 和 sum 的符號是否一致來偵測溢位。如果發生溢出，溢出將為 -1。
max_int 和 min_int：定義最大正值 (0x7fffffff) 和最小負值 (0x80000000) 的常數。
saturated_result：根據是否發生溢位計算結果。如果發生溢出（溢出為 -1），則根據 x 的符號選擇 max_int 或 min_int。如果沒有溢出，則傳回總和。
satMul2
satMul3
sign
x >> 31：將 x 右移 31 位，擷取符號位。如果 x 為非負 (sign_bit = 0)，則此操作有效地將所有位元設為 0；如果 x 為負（sign_bit = -1，二進位補碼），則將所有位元設為 1。
!!x：如果 x 非零，則計算結果為 1；如果 x 為零，則計算結果為 0。這處理 x 為零的情況，確保函數在這種情況下傳回 0。
符號位 | (!!x)：合併結果，對於正 x 回傳 1，對於負 x 回傳 -1，對於零 x 傳回 0。
signMag2TwosComp
sign_bit = x >> 31：將 x 右移 31 位元，隔離正負號位元。非負數為 0，負數為 1。
mask = sign_bit << 31：建立一個遮罩，如果 x 為非負數，則該遮罩為 0；如果 x 為負數，則該遮罩為 0x80000000（最高有效位集）。
x ^ mask：如果 x 為負，則 XOR 運算會翻轉 x 的所有位元（因為 mask 將為 0x80000000），將其轉換為二進位補數。
(sign_bit & 1)：如果 x 為負數，則結果加 1，從而有效調整二進位補數表示形式。
specialBits
subtractionOK
signX = (x >> 31) & 1：擷取 x 的符號位元。將 x 右移 31 位元，僅保留正負號位元。然後用 1 屏蔽以隔離符號位元。
signY = (y >> 31) & 1：與 signX 類似，提取 y 的符號位。
(x - y) >> 31：計算結果 x - y 的正負號位元。
signResult = ((x - y) >> 31) & 1：擷取 x - y 的正負號位元。
differentSigns =signX^signY：檢查 x 和 y 是否有不同的符號。
Overflow = differentSigns & (signX ^ signResult)：根據 x、y 和 x - y 的符號檢查是否有溢出情況。
如果 x - y 可以在不溢出 (!overflow) 的情況下計算，則傳回 1；如果有溢出，則傳回 0。
thirdBits
TMax
(1 << 31) 將二進位數 1 左移 31 位元。
對結果的每一位元取反。對於 0x80000000，位元 NOT 運算結果為 0x7FFFFFFF，這是二進位補數表示形式的最大正值
tmin
trueFiveEighths
mult5 = (x << 2) + x 使用位移位有效地計算 5 * x，這透過使用加法和左移的屬性來避免溢位。
mult5 >> 31 提取 mult5 的正負號位元，如果 mult5 為負，則產生 -1 (0xFFFFFFFF)；如果為非負，則產生 0 (0x00000000)。
除以 8：mult5 >> 3 將 mult5 右移 3 位，實現除以 8。
捨去調整：(sign & (x >> 31)) 根據 x 的符號調整結果。如果 x 為負（x >> 31 產生 -1），則此調整有效地將結果調整為朝零舍入。
trueThreeFourths
乘以 3：(x << 1) + x 使用位移位有效地計算 3 * x，這透過使用加法和左移的屬性來避免溢位。
mult3 >> 31 提取 mult3 的正負號位元，如果 mult3 為負，則產生 -1 (0xFFFFFFFF)；如果為非負，則產生 0 (0x00000000)。
除以 4：mult3 >> 2 將 mult3 右移 2 位，實現除以 4。
捨去調整：(sign & (x >> 31)) 根據 x 的符號調整結果。如果 x 為負（x >> 31 產生 -1），則此調整有效地將結果調整為朝零舍入。
twosComp2SignMag
提取正負號位元：x >> 31 提取 x 的正負號位元。對於負 x，符號將為 -1 (0xFFFFFFFF)，對於非負 x，符號將為 0 (0x00000000)。
絕對值計算：
如果 x 為負數（符號 = -1），x ^ 符號會切換 x 的所有位，從而有效地計算二進位補碼中的 -x - 1。
(~sign + 1) 將反轉後的值加 1，以獲得 x 的絕對值。
構造符號幅度表示：
如果 x 為負，(sign & 0x80000000) 將符號位元設為 0x80000000。
| absX 將符號位元與絕對值組合起來形成 x 的符號-數值表示。
upperBits
!!n：這會將 n 轉換為布林值（如果 n 為 0，則為 0，否則為 1）。這用於建立一個遮罩，如果 n 為零，則該遮罩以所有位元 0 開頭；如果 n 不為零，則所有位元都設為開頭。
<< 31：將布林結果左移 31 位元，如果 n 非零，則結果為 0x80000000；如果 n 為零，則結果為 0x00000000。
\(>> (n + ~0)\)：將遮罩右移 (32 - n) 個位置。當 n 為 0 時，這會導致所有位元向右移動 32 個位置，從而有效地將遮罩清除為 0x00000000。對於非零 n，這會將 1 位元移動到較高的 n 個位置，從而建立所需的遮罩。
注意書寫規範：
TODO: 從 Data Lab 選出可對應到真實應用的案例
最好在 Linux 核心找出相關程式碼，解說應搭配有效的測試程式碼
float_to_long
遇到浮點數問題通常都會用到這 3 種遮罩
0x007FFFFF 過濾出尾數部分
0x7F800000 過濾出指數部分
0x80000000 過濾出正負號位元
parity check
通常用在傳輸位元組的錯誤檢測
函數根據輸入參數 i 的奇偶性返回兩個固定模式之一：
當 i 是奇數時：
i % 2 結果為 1，返回值為 0x55555555。
0x55555555 在二進位制中為 01010101010101010101010101010101。
當 i 是偶數時：
i % 2 結果為 0，返回值為 0xAAAAAAAA。
0xAAAAAAAA 在二進位制中為 10101010101010101010101010101010。
clk_zero
tmax: 根據 tmin 的值來設定，如果 tmin 大於255，則 tmax 設為511，否則設為255。
read_reg
這裡的 0xff 確保讀取的數據只保留低 8 位元
reverse_bytes
指定的位元長度 len，使用多種位元操作來反轉整數 b 的位元順序。每個 case 語句後的 fallthrough 允許繼續執行下一個 case，
machine_restart
當系統出現故障或陷入無限循環時，看門狗定時器可以強制重啟系統。設置這個位元確保了看門狗定時器的啟用，使其能夠在必要時觸發系統重啟。
hsync_polarity_show
提取HSYNC配置中的正負號位元（第31位）
CS:APP 閱讀筆記
三種最重要數值表示方式
1.無號數 (unsigned)
2.二補數 (two's-complement)
3.浮點數 (floating-point)
注意用語：
- bit 的翻譯是「位元」，而非「位」，後者是量詞
- compatible 是「相容」
- signed integer 是「有號整數」，而非「有符號」
- byte 是「位元組」，而非「字節」，抖音不要看太多
- 務必使用本課程教材的詞彙和慣例
int 正整數，遇到 overflow 會產生溢出，從而變負數
浮點數，遇到 overflow 會產出特殊值 +ini
32 bits = 4 GB
64 bits = 16 GB
通常 64 位元可以相容 32 位元機器編譯的程式
注意書寫規範：
| 有號 | 無號 | 32 位元 |
64 位元組數量 |
|---|---|---|---|
| char | unsigned char | 1 | 1 |
| short | unsigned short | 2 | 2 |
| int | unsigned int | 4 | 4 |
| long | unsigned long | 4 | 8 |
| int32_t | uint32_t | 4 | 4 |
| int64_t | uint64_t | 8 | 8 |
char * |
4 | 8 | |
| float | 4 | 4 | |
| double | 8 | 8 |
- ISO C99 引入 int32_t,int64_t,其特性是位元組
字節大小固定,不隨編譯器和機器設置而變化
練習 2.10
注意書寫規範：
- 無論標題和內文中，漢字和英語字元之間要有空白字元 (對排版和文字搜尋有利)
- 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
透過 xor 運算達成數值交換。
位移運算與優先級問題
- 加法(和減法)優先級比移位運算高
- 由左至右結合性規則
查閱 C 語言規格書，摘錄運算子優先權相關章節。
| 符號 | 運算的類型 | 關聯性 |
|---|---|---|
| [ ] ( ) . -> ++– (後置) | 運算式 | 由左至右 |
| sizeof & * + - ~ ! ++– (前置) | 一元 | 由右至左 |
| 類型轉換 | 一元 | 由右至左 |
| * / % | 乘法 | 由左至右 |
| + - | 加法 | 由左至右 |
| << >> | 位元移位 | 由左至右 |
| < > <= >= | 關聯式 | 由左至右 |
| == != | 等式 | 由左至右 |
| & | 位元 AND | 由左至右 |
| ^ | 位元互斥 OR | 由左至右 |
| \ | 位元包含 OR | 由左至右 |
| && | 邏輯 AND | 由左至右 |
| \ | 邏輯 OR | 由左至右 |
| ? : | 條件運算式 | 由右至左 |
| = *= /= %= += -= <<= >>= &= ^= | = | 簡單和複合指派 |
| , | 循序求值 | 由左至右 |
