Linux 核心專題: Data Lab

執行人: Terry7Wei7
解說影片-1
解說影片-2

Reviewed by Daniel-0224

int copyLSB(int x)
{
    
-    return !!(x & 1) + ~0;
+    return (x & 1) * -1;
    
}

改為使用 diff 才能顯示出增加及刪減的程式碼。

int copyLSB(int x)
{
    
-    return !!(x & 1) + ~0;
+    return (x & 1) * -1;
    
}

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 的提案，並舉出實際程式碼修改

參考資訊:

• CS:APP Data Lab 解題筆記
• Data lab 紀錄
• Data Lab 作業區

TODO: Data Lab 解題

確保儘可能少的指令

absolute value

/*
 * absVal - absolute value of x
 *   Example: absVal(-1) = 1.
 *   You may assume -TMax <= x <= TMax
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 4
 */
int absVal(int x)
{
    int mask = x >> 31;
    return (x ^ mask) - mask;
}

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

/*
 * addOK - Determine if can compute x+y without overflow
 *   Example: addOK(0x80000000, 0x80000000) = 0,
 *            addOK(0x80000000, 0x70000000) = 1,
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int addOK(int x, int y)
{
    int sum = x + y;
    int sx = x >> 31;
    int sy = y >> 31;
    int ss = sum >> 31;
    int same_sign = !(sx ^ sy);
    int overflow = (sx ^ ss);
    return !(same_sign & overflow);
}

避免僅進行程式碼逐行解說 (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

/*
 * allEvenBits - return 1 if all even-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allEvenBits(int x)
{
    // Define the mask with all even bits set to 1
    int mask = 0x55555555;
    // Check if all even bits in x are set to 1
    // (x & mask) should equal to mask if all even bits are 1
    return !((x & mask) ^ mask);
}

避免僅進行程式碼逐行解說 (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

/*
 * anyEvenBit - return 1 if any even-numbered bit in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples anyEvenBit(0xA) = 0, anyEvenBit(0xE) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int anyEvenBit(int x)
{
    // Define the mask with all even bits set to 1
    int mask = 0x55555555;
    // Check if any even bit in x is set to 1
    // (x & mask) should be non-zero if any even bit is 1
    return !!(x & mask);
}

避免僅進行程式碼逐行解說 (ChatGPT 也會！)，而是你該從程式碼設計者的角度，闡述「你為何當初想要這樣作？」「更早之前我嘗試用別的方式，遇到什麼問題」等高階想法，避免淪落為「舉燭」。

int mask = 0x55555555;
定義了一個位元遮罩，其所有偶數位元為 1。
(x & mask)
將 x 和 mask 進行位元運算，保留 x 中的所有偶數位元。
!!(x & mask)
將結果進行邏輯非運算兩次。第一次邏輯非將非零值轉換為 0，將零值轉換為 1。第二次邏輯非將其結果再次取反，即將非零值轉換為 1，將零值保持為 0。最終，如果有任意一個偶數位為 1，則回傳 1；否則回傳 0。

anyOddBit

/*
 * anyOddBit - return 1 if any odd-numbered bit in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples anyOddBit(0x5) = 0, anyOddBit(0x7) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int anyOddBit(int x)
{
    // Define the mask with all odd bits set to 1
    int mask = 0xAAAAAAAA;
    // Check if any odd bit in x is set to 1
    // (x & mask) should be non-zero if any odd bit is 1
    return !!(x & mask);
}

避免僅進行程式碼逐行解說 (ChatGPT 也會！)，而是你該從程式碼設計者的角度，闡述「你為何當初想要這樣作？」「更早之前我嘗試用別的方式，遇到什麼問題」等高階想法，避免淪落為「舉燭」。

int mask = 0xAAAAAAAA;
定義一個位元遮罩，其所有奇數位為1。
(x & mask)
將 x 和 mask 進行位元運算，保留 x 中的所有奇數位元。
!!(x & mask)
將結果進行邏輯非運算兩次。第一次邏輯非將非零值轉換為0，將零值轉換為1。第二次邏輯非將其結果再次取反，即將非零值轉換為1，將零值保持為0。最終，如果有任意一個奇數位為1，則回傳1；否則回傳0。

bang

/*
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
 */
int bang(int x)
{
    // x | -x will set the highest bit to 1 if x is not 0
    // Shift 31 bits to get the sign bit, negate + 1 to get the logical negation
    // result
    return ((x | (~x + 1)) >> 31) + 1;
}

這一題可以用到的特性 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

/*
 * bitAnd - x&y using only ~ and |
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |
 *   Max ops: 8
 *   Rating: 1
 */
int bitAnd(int x, int y)
{
    return ~(~x | ~y);
}

這題參考笛摩根定律

bitCount

/*
 * bitCount - returns count of number of 1's in word
 *   Examples: bitCount(5) = 2, bitCount(7) = 3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 40
 *   Rating: 4
 */
int bitCount(int x)
{
    // Masks for bit manipulation
    int mask1 = 0x55555555;   // 01010101010101010101010101010101
    int mask2 = 0x33333333;   // 00110011001100110011001100110011
    int mask4 = 0x0F0F0F0F;   // 00001111000011110000111100001111
    int mask8 = 0x00FF00FF;   // 00000000111111110000000011111111
    int mask16 = 0x0000FFFF;  // 00000000000000001111111111111111

    // Step 1: Pair-wise count
    x = (x & mask1) + ((x >> 1) & mask1);

    // Step 2: 4-bit counts
    x = (x & mask2) + ((x >> 2) & mask2);

    // Step 3: 8-bit counts
    x = (x & mask4) + ((x >> 4) & mask4);

    // Step 4: 16-bit counts
    x = (x & mask8) + ((x >> 8) & mask8);

    // Step 5: 32-bit counts
    x = (x & mask16) + ((x >> 16) & mask16);

    return x;
}

逐步計算 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

/*
 * bitMatch - Create mask indicating which bits in x match those in y
 *            using only ~ and &
 *   Example: bitMatch(0x7, 0xE) = 0x6
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitMatch(int x, int y)
{
    int sameBits = x & y;
    int diffBits = ~x & ~y;
    return ~(~sameBits & ~diffBits);
}

若位元 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+\bar{A}\cdot \bar{B}$

但題型不能使用 or 閘，改成

$Y=\overline{\stackrel{―}{A\cdot B}\cdot \stackrel{―}{\stackrel{―}{A}\cdot \stackrel{―}{B}}}$

$=>$

$Y=\overline{\stackrel{―}{sameBits}\cdot \stackrel{―}{diffBits}}$

bitNor

/*
 * bitNor - ~(x|y) using only ~ and &
 *   Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
 *   Legal ops: ~ &
 *   Max ops: 8
 *   Rating: 1
 */
int bitNor(int x, int y)
{
    return ~x & ~y;
}

$Y=\overline{A+B}$

$Y=\bar{A}\cdot \bar{B}$

bitOr

/*
 * bitOr - x|y using only ~ and &
 *   Example: bitOr(6, 5) = 7
 *   Legal ops: ~ &
 *   Max ops: 8
 *   Rating: 1
 */
int bitOr(int x, int y)
{
    return ~(~x & ~y);
}

$Y=A+B$

$Y=\overline{\stackrel{―}{A+B}}$

$Y=\overline{\stackrel{―}{A}\cdot \stackrel{―}{B}}$

bitParity

/*
 * bitParity - returns 1 if x contains an odd number of 0's
 *   Examples: bitParity(5) = 0, bitParity(7) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 4
 */
int bitParity(int x)
{
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return x & 1;
}

利用異或運算來逐步減少 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

/*
 * bitReverse - Reverse bits in a 32-bit word
 *   Examples: bitReverse(0x80000002) = 0x40000001
 *             bitReverse(0x89ABCDEF) = 0xF7D3D591
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 45
 *   Rating: 4
 */
int bitReverse(int x)
{
    int mask1 = 0x55555555;  // 01010101010101010101010101010101
    int mask2 = 0x33333333;  // 00110011001100110011001100110011
    int mask3 = 0x0F0F0F0F;  // 00001111000011110000111100001111
    int mask4 = 0x00FF00FF;  // 00000000111111110000000011111111
    int mask4 = 0x0000FFFF;  // 00000000000000001111111111111111
    x = ((x >> 1) & mask1) | ((x & mask1) << 1);
    x = ((x >> 2) & mask2) | ((x & mask2) << 2);
    x = ((x >> 4) & mask3) | ((x & mask3) << 4);
    x = ((x >> 8) & mask4) | ((x & mask4) << 8);
    x = (x >> 16) & mask5  | ((x & mask5) << 16);

    return x;
}

將整數分成兩半，交換左右兩半的位元。
繼續將每半部分成更小的部分並交換，直到所有位元都被交換。
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)

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
//Find only one bit in X and Y that is 1, assuming X=1010, Y=1011
//~(x&~y) == 1010&0100 = 0000, negation=1111,
//~(~x&y) == 0101&1011 = 0001, negation=1110,
//~(~(x&~y)&~(~x&y)) == 1111&1110 = 1110, negation=0001
int bitXor(int x, int y)
{
    return ~(~(x&~y)&~(~x&y));
}

A	B	$$Y=A\oplus B$$
0	0	0
0	1	1
1	0	1
1	1	0

$Y=A\cdot \bar{B}+\bar{A}\cdot B$

在 108 課綱，譯作「笛摩根定律」

第摩根定理 互換

$Y=\overline{\stackrel{―}{A\cdot \stackrel{―}{B}}\cdot \stackrel{―}{\stackrel{―}{A}\cdot B}}$

byteSwap

/*
 * byteSwap - swaps the nth byte and the mth byte
 *  Examples: byteSwap(0x12345678, 1, 3) = 0x56341278
 *            byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD
 *  You may assume that 0 <= n <= 3, 0 <= m <= 3
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 25
 *  Rating: 2
 */
int byteSwap(int x, int n, int m)
{
    int n_offset = n << 3;  // n * 8
    int m_offset = m << 3;  // m * 8

    int byte_n = (x >> n_offset) & 0xFF;  // Extract nth byte
    int byte_m = (x >> m_offset) & 0xFF;  // Extract mth byte

    // Clear nth and mth bytes in x
    x = x & ~(0xFF << n_offset);
    x = x & ~(0xFF << m_offset);

    // Insert swapped bytes into x
    x = x | (byte_n << m_offset);
    x = x | (byte_m << n_offset);

    return x;
}

計算位元組偏移量

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()

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void)
{
     return 0x1 << 31;
}

int 類型是 32 位元，即 4 bytes。二補數最小值就是正負號位元為 1，其餘全為 0。
對 0x1 進行位移運算。

istmax

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) {
    int y = x + 1;              // y = x + 1 = 1000
    x = x + y;                  // x = x + y = 1111
    x = ~x;                     // 0000
    y = !y;                     // 0 ,y is 0 only if x was Tmax
    x = x | y;                  // 0 ,combine both conditions
    return !x;                  // return 1 if x is Tmax, 0 otherwise
}

以 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

/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
    // 0xAAAAAAAA is a constant where all odd-numbered bits are 1
    int mask = 0xAAAAAAAA;

    // Perform bitwise AND with the mask and compare with the mask
    return !((x & mask) ^ mask);
}

判斷是否有號數 x 的所有奇數位元都為 1
先利用奇數位元遮罩 0xAAAAAAAA 做 & 運算，留下奇數位元，將偶數位元變 0
接著做位元運算 xor，如果奇數位元都是 1 的話會與奇數位元遮罩相等，所以會是 0
如果不是 0，代表奇數位元不全都是 1

negate(x)

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return ~x+1;
}

二補數，對 x 取反向 +1
ex: 0001(1) 取反 = 1110，加 1 = 1111(-1)
1111(-1) 取反 = 0000，加 1 = 0001(1)

isAsciiDigit(x)

/* 
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x) {

  int mask = 0x30; //filter out ASCII codes for characters '0' to 'f'
  int high_mask = 0x39;
  int num = !((mask>>4) ^ (x>>4)); // if x = '0' to 'f' return 0
  int dis = !((x) +(~ (high_mask))); // if x < 'a' return 0
  return !(num & dis);
}

原本想先篩選掉 x 不是 0x3 開頭的, 接著透過 x 減去 9，看是否 >0
但第二段還沒想出怎麼做

看了其他人的解法
設定一個 UpperBound，讓大於 0x39 的數加上它會溢出變成負數
設定一個 LowerBound，讓小於 0x30 的數加上會為負數
將輸入 x 分別加上 UpperBound & LowerBound，右移 31 bit 後與 sign 做 & 操作判斷數值的正負
當有任何一個數為負時，代表超出範圍，!(upperBound|lowerBound) 回傳 0; 反之回傳 1

int isAsciiDigit(int x) {
  int sign = 0x1<<31;
  int upperBound = ~(sign|0x39);
  int lowerBound = ~0x30;
  upperBound = sign&(upperBound+x)>>31;
  lowerBound = sign&(lowerBound+1+x)>>31;
  return !(upperBound|lowerBound);
}

conditional(x, y, z)

/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(3,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
  x = !!x;
  x = ~x+1;
  return (x&y)|(~x&z);
}

題意為若 X 為真(即非 0 )，則輸出 Y，反之輸出 Z
這邊用兩層反向邏輯判斷 X，如果輸入是非 0，最後 x 會是 0xFFFFFFFFE + 1 = 0xFFFFFFFFF，如果輸入是 0，最後 x 會是 0xFFFFFFFFF + 1 = 溢位 0x00000000，再跟 Y,Z 做位元運算

countLeadingZero?

/*
 * countLeadingZero - count the number of zero bits preceding the
 *                    most significant one bit
 *   Example: countLeadingZero(0x00000F00) = 20,
 *            countLeadingZero(0x00000001) = 31
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 50
 *   Rating: 4
 */
int countLeadingZero(int x)
{
    int mask, count;

    // Ensure the bits of x are in the MSB position
    mask = ~(x >> 1);  // mask becomes 0xFFFFFFFF if x is not zero
    x |= mask;         // set all bits to 1 after the MSB

    // Now count leading zeros using a series of bit shifts
    count = !(x & (0xFFFF8000 << 16)) << 4;
    count |= !(x & (0xFF800000 << (count + 8))) << 3;
    count |= !(x & (0xF8000000 << (count + 4))) << 2;
    count |= !(x & (0xE0000000 << (count + 2))) << 1;
    count |= !(x & (0xC0000000 << (count + 1)));

    return count;
}

copyLSB?

/*
 * copyLSB - set all bits of result to least significant bit of x
 *   Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int copyLSB(int x)
{
-    return !!(x & 1) + ~0;
+    return (x & 1) * -1;
}

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

/*
 * distinctNegation - returns 1 if x != -x.
 *     and 0 otherwise
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 5
 *   Rating: 2
 */
int distinctNegation(int x)
{
    return x != -x;
}

對於整數 x，只有當 x = 0 時，x == -x ，因為在二補數表示中，只有零的相反數是它自己。
x != -x：利用比較運算子判斷 x 是否不等於它的相反數。如果 x 不等於 -x，則回傳1；否則回傳0。

dividePower2

/*
 * dividePower2 - Compute x/(2^n), for 0 <= n <= 30
 *                Round toward zero
 *   Examples: dividePower2(15, 1) = 7, dividePower2(-33, 4) = -2
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int dividePower2(int x, int n)
{
    int sign = x >> 31;  // sign is either 0 or -1 (0xFFFFFFFF)

    // For positive x, directly shift right by n
    // For negative x, add (1 << n) - 1 before shifting right by n
    return (x + (sign & ((1 << n) + ~0))) >> n;
}

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 的對應次方並向下取整。例如：

int x = 8;   // 0b00001000
int result = x >> 1;  // 0b00000100, result = 4

int x = 9;   // 0b00001001
int result = x >> 1;  // 0b00000100, result = 4

上面的程式碼中，9 右移 1 位的結果是 4，相當於 9 除以 2 的 1 次方（向下取整）。

int x = -8;  // 0b11111000 
int result = x >> 1;  // 0b11111100, result = -4

int x = -9;  // 0b11110111 
int result = x >> 1;  // 0b11111011, result = -5

向下取整與向零取整
向下取整和向零取整的差別在於：

向下取整（floor）：結果是小於或等於輸入值的最大整數。
向零取整（truncate）：結果是絕對值較小的整數，也就是直接去掉小數部分。
對於正數，向下取整和向零取整的結果是相同的。

evenBits

/*
 * evenBits - return word with all even-numbered bits set to 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 1
 */
int evenBits(void)
{
    int pattern = 0x55;                   // Binary: 01010101
    int mask = (pattern << 8) | pattern;  // Binary: 0101010101010101

    return (mask << 16) | mask;  // Binary: 01010101010101010101010101010101
}

直接回傳 0X55555555 應該也可以

ezThreeFourths

/*
 * ezThreeFourths - multiplies by 3/4 rounding toward 0,
 *                  Should exactly duplicate effect of C expression (x*3/4),
 *                  including overflow behavior.
 *   Examples: ezThreeFourths(11) = 8
 *             ezThreeFourths(-9) = -6
 *             ezThreeFourths(1073741824) = -268435456 (overflow)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 3
 */
int ezThreeFourths(int x)
{
    int mult3 = (x << 1) + x;  // Equivalent to x * 3
    int sign = mult3 >> 31;    // Sign of mult3 (either 0 or -1)

    // For positive x, just divide by 4
    // For negative x, add 3 to mult3 before dividing by 4 to handle rounding
    // toward zero
    return (mult3 + (sign & 3)) >> 2;
}

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?

/*
 * fitsBits - return 1 if x can be represented as an n-bit, two's complement
 *            integer.
 *            1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int fitsBits(int x, int n)
{
    int sign = x >> 31;

    // For positive numbers, check if they are in the range [0, 2^(n-1)-1]
    // For negative numbers, check if they are in the range [-2^(n-1), -1]

    return !(~(x >> (n + ~0)) & sign) & !(x >> (n + ~0) & !sign);
}

isLessOrEqual(x,y)

/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y) {
   // Compute the sign bits of x and y
    int signX = x >> 31 & 1;
    int signY = y >> 31 & 1;

    // Case 1: x is negative, y is positive (x <= y is true)
    int xNegYPos = signX & ~signY;

    // Case 2: Both have the same sign
    int sameSign = !(signX ^ signY);

    // Calculate y - x
    int diff = y + (~x + 1);  
    int diffSign = diff >> 31 & 1;

    // If sameSign is 1, we check the sign of the difference
    int lessOrEqualSameSign = sameSign & ~diffSign;

    // Combine the cases
    return xNegYPos | lessOrEqualSameSign;
}

這題要比較 x 是否小於等於 y
我的想法是先比較 x,y 的符號位元
若 x 是負數 sign x 為 1，y 是正數 sign y 為 0，result = 1
若符號位元相同，則再進行減法比較，若 y-x 為正，result = 1

logicalNeg(x)

/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */

int logicalNeg(int x) {

  return ((x|(~x+1))>>31)+1;
}

透過與自身 二補數相加會產生溢位得到 0 的特性完成
除了 0 和最小數的補數是自身，但一樣能透過篩選符號位元完成

howManyBits(x)

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  int b16,b8,b4,b2,b1,b0;
  int sign=x>>31;
  x = (sign&~x)|(~sign&x);
    
  b16 = !!(x>>16)<<4;
  x = x>>b16;
  b8 = !!(x>>8)<<3;
  x = x>>b8;
  b4 = !!(x>>4)<<2;
  x = x>>b4;
  b2 = !!(x>>2)<<1;
  x = x>>b2;
  b1 = !!(x>>1);
  x = x>>b1;
  b0 = x;
  return b16+b8+b4+b2+b1+b0+1;
}

b16 = !!(x >> 16) << 4; 檢查高 16 位是否有 1，如果有，b16 為 16。
x = x >> b16; 如果 b16 為 16，則右移 16 位，否則不變。
重複這個過程對 b8、b4、b2、b1 進行檢查和位移。
b0 = x; 獲取剩餘的最低位
將所有計算出的位數加起來，並加上1表示符號位，得到最終的位數。

floatScale2(f)

/* 
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf) {
    // Extract sign bit, exponent bit and mantissa bit
    unsigned sign = uf >> 0x80000000;
    unsigned exp = (uf & 0x7F800000) >> 23;
    unsigned frac = uf & 0x007FFFFF;
    // If the exponent bit is 255 (that is, all 1), it is infinity or NaN, and uf is returned directly.
    if (exp == 255) {
        return uf;
    }
    if (exp == 0) {
        // Shift the mantissa one position to the left, which is equivalent to multiplying by 2
        frac <<= 1;
        // Keep the sign bit and reassemble the result to return
        return sign | frac;
    }
    exp += 1;
    // If the exponent becomes 255 after adding 1, it means it reaches infinity and returns infinity.
    if (exp == 255) {
        return sign | 0x7F800000;
    }
    // Retain the sign bit and new exponent and mantissa bits
    return sign | (exp << 23) | frac;
}

先提取出指數位的部分，觀察後可發現指數位加 1，就等於乘法 *2
並且透過指數位篩選掉 0、NaN、無窮大、無窮小

floatFloat2Int(f)

/* 
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
    unsigned sign = uf >> 31;
    int exp = ((uf >> 23) & 0xFF) - 127;
    unsigned frac = (uf & 0x7FFFFF) | 0x800000; 
    if ((uf & 0x7F800000) == 0x7F800000) {
        return 0x80000000u;
    }
    if (exp < 0) {
        return 0;
    }
    if (exp > 31) {
        return 0x80000000u;
    }
    if (exp > 23) {
        frac <<= (exp - 23);
    } else {
        frac >>= (23 - exp);
    }
    if (sign) {
        frac = -frac;
    }
    return frac;
}

過濾出符號位、指數位、尾數位，再去做特殊況處理
如果指數位全為 1，返回 0x80000000u。
若全為 0 直接返回 0。

單精度浮點數的偏置值是 127，因此實際指數為 exp - 127。

如果實際指數小於 0，則浮點數的小數部分在整數為 0
若大於 31，則超出 32 位有號整數的範圍，返回 0x80000000u。

尾數部分加上隱含的 1 位（即 1.xxxxx 變成 1xxxxx），如果指數大於等於 23，則將尾數左移，否則右移。
如果符號位為1，取負值。

floatPower2(x)

/* 
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *   (2.0 raised to the power x) for any 32-bit integer x.
 *
 *   The unsigned value that is returned should have the identical bit
 *   representation as the single-precision floating-point number 2.0^x.
 *   If the result is too small to be represented as a denorm, return
 *   0. If too large, return +INF.
 * 
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
 *   Max ops: 31 
 *   Rating: 4
 */
unsigned floatPower2(int x)
{
    int exp = x + 127;
    if (exp <= 0)
        return 0;
    if (exp >= 255)
        return 0x7f800000;
    return exp << 23;
}

單精度浮點數的指數偏置值是 127。
2 的 x 次方的指數表示為 x + 127。

如果 x + 127 小於 0，則結果太小，返回 0。
如果 x + 127 大於 255，則結果太大，返回正無窮大（+INF）。

指數位設置為 x + 127。
尾數位設置為 0，因為 2 的 x 次方的尾數部分為 1.0（隱含位）。

fitsShort?

/*
 * fitsShort - return 1 if x can be represented as a 16-bit, two's complement
 *             integer.
 *   Examples: fitsShort(33000) = 0, fitsShort(-32768) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 1
 */
int fitsShort(int x)
{
    // Shift x right by 15 bits to get the highest bit of x
    int sign = x >> 15;

    // Checks whether the most significant bit of x and x match the 16-bit two's
    // complement representation
    return !(sign ^ (x >> 15));
}

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

/*
 * floatAbsVal - Return bit-level equivalent of absolute value of f for
 *               floating point argument f.
 *               Both the argument and result are passed as unsigned int's,
 *               but they are to be interpreted as the bit-level
 *               representations of single-precision floating point values.
 *               When argument is NaN, return argument..
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 10
 *   Rating: 2
 */
unsigned floatAbsVal(unsigned uf)
{
 
    unsigned int n = *(unsigned int*)&uf;
  
    unsigned int mask = 0x7FFFFFFF;
    
    unsigned int abs_n = n & mask;
    
    return *((float*)&abs_n);
}

floatInt2Float

/*
 * floatInt2Float - Return bit-level equivalent of expression (float) x
 *                  Result is returned as unsigned int, but it is to be
 *                  interpreted as the bit-level representation of a
 *                  single-precision floating point values.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatInt2Float(int x)
{
    unsigned sign;
    unsigned frac;
    unsigned exp;
    unsigned u;

    if (x == 0) {
        return 0;
    }

    if (x < 0) {
        sign = 1u << 31;
        x = -x;
    } else {
        sign = 0;
    }

    frac = x;
    exp = 158;  // 127 + 31 (bias)

    while (!(frac & 0x80000000)) {
        frac <<= 1;
        exp--;
    }

    u = sign | (exp << 23) | (frac & 0x7FFFFF);

    return u;
}

sign：記錄 x 的符號位，如果 x 小於 0，則設定為 1，表示負數。
frac：初始化為 x 的絕對值，表示尾數。
exp：初始化為適當的指數值，透過不斷左移 frac 直到最高有效位元為 1 來調整。
u：使用 sign、exp 和 frac 建構最終的單精度浮點數位級表示。

floatIsEqual

/*
 * floatIsEqual - Compute f == g for floating point arguments f and g.
 *                Both the arguments are passed as unsigned int's, but
 *                they are to be interpreted as the bit-level representations
 *                of single-precision floating point values.
 *                If either argument is NaN, return 0.
 *                +0 and -0 are considered equal.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 25
 *   Rating: 2
 */
int floatIsEqual(unsigned uf, unsigned ug)
{
    // Check for NaN
    if ((uf & 0x7FFFFFFF) > 0x7F800000 || (ug & 0x7FFFFFFF) > 0x7F800000) {
        return 0;
    }

    // Handle ±0 case
    if ((uf & 0x7FFFFFFF) == 0 && (ug & 0x7FFFFFFF) == 0) {
        return 1;
    }

    // Compare bit-level representations
    return uf == ug;
}

NaN 檢測

如果 uf 或 ug 是 NaN（指數位全為1且尾數位非全0），則直接回傳0。
±0 判定

若 uf 和 ug 的位級表示表示均為 ±0，即符號位元和尾數位元均為0，則傳回1。
一般情況比較

將 uf 和 ug 的位元級表示直接進行比較，如果完全相同則回傳1，否則回傳0。

floatIsLess

/*
 * floatIsLess - Compute f < g for floating point arguments f and g.
 *               Both the arguments are passed as unsigned int's, but
 *               they are to be interpreted as the bit-level representations
 *               of single-precision floating point values.
 *               If either argument is NaN, return 0.
 *               +0 and -0 are considered equal.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 3
 */
int floatIsLess(unsigned uf, unsigned ug)
{
    // Check for NaN
    if ((uf & 0x7FFFFFFF) > 0x7F800000 || (ug & 0x7FFFFFFF) > 0x7F800000) {
        return 0;
    }

    // Handle ±0 case
    if ((uf & 0x7FFFFFFF) == 0 && (ug & 0x7FFFFFFF) == 0) {
        return 0;
    }

    // Compare sign bits
    int sign_f = uf >> 31;
    int sign_g = ug >> 31;
    if (sign_f != sign_g) {
        return sign_f < sign_g;
    }

    // Compare bit-level representations
    return uf < ug;
}

NaN 檢測

如果 uf 或 ug 是 NaN（指數位全為1且尾數位非全0），則直接回傳0。
±0 判定

如果 uf 和 ug 的位級表示表示均為 ±0，即符號位和尾數位均為0，則回傳0。
符號位比較

如果 uf 和 ug 的符號位不同，可以直接根據符號位來判斷大小關係。
一般情況比較

如果符號位相同，需要比較它們的位級表示來判斷大小關係。

floatNegate

/*
 * floatNegate - Return bit-level equivalent of expression -f for
 *               floating point argument f.
 *               Both the argument and result are passed as unsigned int's,
 *               but they are to be interpreted as the bit-level
 *               representations of single-precision floating point values.
 *               When argument is NaN, return argument.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 10
 *   Rating: 2
 */
unsigned floatNegate(unsigned uf)
{
    // Check for NaN
    if ((uf & 0x7FFFFFFF) > 0x7F800000) {
        return uf;
    }

    // Toggle the sign bit
    return uf ^ 0x80000000;
}

NaN 檢測：透過檢查指數位是否全為 1 且尾數位非全 0 來判斷是否為 NaN。
正負號位元取反：對於非 NaN 的情況，直接透過異或運算 uf ^ 0x80000000 來將正負號位元取反，從而得到 -f 的位級表示。

floatPower2

/*
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *               (2.0 raised to the power x) for any 32-bit integer x.
 *
 *               The unsigned value that is returned should have the
 *               identical bit representation as the single-precision
 *               floating-point number 2.0^x.
 *               If the result is too small to be represented as a denorm,
 *               return 0. If too large, return +INF.
 *
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatPower2(int x)
{
    // Check for overflow
    if (x > 127) {
        return 0x7F800000;  // +INF
    }

    // Check for too small to be represented as denorm
    if (x < -126) {
        return 0;  // Too small to be denorm
    }

    // Calculate exponent
    unsigned exp = 127 + x;

    // Construct the single-precision float representation
    return exp << 23;
}

特殊情況處理：

如果 x 大於 127，則傳回單精度浮點數的正無窮大表示（0x7F800000）。
如果 x 小於 -126，則傳回 0，因為此時 2.0^x 太小無法表示成規格化浮點數。
規格化浮點數處理：

對於處於規格化範圍內的 x，計算 2.0^x 的指數部分，並使用左移操作建立單精度浮點數的表示。

floatScale1d2

/*
 * floatScale1d2 - Return bit-level equivalent of expression 0.5*f for
 *                 floating point argument f.
 *                 Both the argument and result are passed as unsigned int's,
 *                 but they are to be interpreted as the bit-level
 *                 representation of single-precision floating point values.
 *                 When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale1d2(unsigned uf)
{
    unsigned sign = uf & 0x80000000;
    unsigned exp = uf & 0x7F800000;
    unsigned frac = uf & 0x007FFFFF;

    // Check for NaN or infinity
    if (exp == 0x7F800000) {
        return uf;  // Return uf if NaN or infinity
    }

    if (exp == 0) {
        // Denormalized case
        frac >>= 1;
        return sign | frac;
    } else {
        // Normalized case
        exp -= 0x00800000;  // Subtract 1 from exponent to divide by 2
        return sign | exp | frac;
    }
}

特殊情況處理：

如果參數 uf 是 NaN 或無限大（指數部分為 0x7F800000），直接回傳 uf。
規格化浮點數處理：

對於規格化浮點數，首先提取出符號位、指數位和尾數位。
如果是規格化浮點數，則需要將指數部分減去 0x00800000（相當於減去 1），以達到乘以 0.5 的效果。
將調整後的指數和原尾數重新組合成單精確度浮點數的位元級表示。
非規格化浮點數處理：

對於非規格化浮點數（指數部分為 0），直接將尾數右移一位即可達到乘以 0.5 的效果。

floatScale2

/*
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *               floating point argument f.
 *               Both the argument and result are passed as unsigned int's,
 *               but they are to be interpreted as the bit-level representation
 *               of single-precision floating point values.
 *               When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf)
{
    unsigned sign = uf & 0x80000000;
    unsigned exp = uf & 0x7F800000;
    unsigned frac = uf & 0x007FFFFF;

    // Check for NaN or infinity
    if (exp == 0x7F800000) {
        return uf;  // Return uf if NaN or infinity
    }

    if (exp == 0) {
        // Denormalized case
        frac <<= 1;
        return sign | frac;
    } else if (exp != 0x7F000000) {
        // Normalized case
        exp += 0x00800000;  // Add 1 to exponent to multiply by 2

        // Check for overflow
        if (exp >= 0x7F800000) {
            return 0x7F800000 | sign;  // Return +INF
        }

        return sign | exp | frac;
    } else {
        // Handle the case when the exponent is already at the maximum value
        // (infinite result)
        return uf;
    }
}

特殊情況處理：

如果參數 uf 是 NaN 或無限大（指數部分為 0x7F800000），直接回傳 uf。
規格化浮點數處理：

對於規格化浮點數，首先提取出符號位、指數位和尾數位。
如果是規格化浮點數，需要將指數部分加上 0x00800000（相當於加上 1），以達到乘以 2 的效果。
如果乘以 2 後超過了單精確度浮點數的表示範圍（指數部分超過 0x7F800000），則傳回 +INF。
非規格化浮點數處理：

對於非規格化浮點數（指數部分為 0），直接將尾數左移一位即可達到乘以 2 的效果。

getByte

/*
 * getByte - Extract byte n from word x
 *           Bytes numbered from 0 (least significant) to 3 (most significant)
 *   Examples: getByte(0x12345678,1) = 0x56
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int getByte(int x, int n)
{
    return (x >> (n << 3)) & 0xFF;
}

(n << 3)：將 n 乘以 8 來計算位元組偏移量
x >> (n << 3)：將 x 右移 (n << 3) 位，將位置 n 處的位元組帶到最低有效位元組位置。
& 0xFF：應用遮罩 (0xFF) 來提取最低有效位元組。

howManyBits

/* howManyBits - return the minimum number of bits required to represent x in
 *               two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x)
{
    int b16, b8, b4, b2, b1, b0;
    int sign = x >> 31;
    x = (sign & ~x) | (~sign & x);

    b16 = !!(x >> 16) << 4;
    x = x >> b16;
    b8 = !!(x >> 8) << 3;
    x = x >> b8;
    b4 = !!(x >> 4) << 2;
    x = x >> b4;
    b2 = !!(x >> 2) << 1;
    x = x >> b2;
    b1 = !!(x >> 1);
    x = x >> b1;
    b0 = x;
    return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}

如果 x 為 0，則只需要 1 位。
如果 x 是 0x80000000，則需要 32 位元。

透過取其絕對值 (abs_x) 並考慮其符號 (sign_bit) 來標準化 x 。

使用二分查找法確定所需的最小位數：
逐漸檢查更大的位元大小，直到找到在 abs_x 中設定的最高位元。
這涉及到將 abs_x 右移 2 的冪並檢查結果數字是否非零。

根據abs_x中最高設定位的位置決定所需的位數。
如果 x 為負，則調整結果以考慮正負號號位元。

implication

/*
 * implication - return x -> y in propositional logic - 0 for false,
 *               1 for true
 *   Example: implication(1, 1) = 1
 *            implication(1, 0) = 0
 *   Legal ops: ! ~ ^ |
 *   Max ops: 5
 *   Rating: 2
 */
int implication(int x, int y)
{
    return !(x & !y);
}

intLog2

/*
 * intLog2 - return floor(log base 2 of x), where x > 0
 *   Example: intLog2(16) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 90
 *   Rating: 4
 */
int intLog2(int x)
{
    int result = 0;
    // Check if the higher 16 bits have any 1s
    result = !!(x >> 16) << 4;  // if x >= 2^16, result = 16
    result = result + (!!(x >> (result + 8))
                       << 3);  // if x >= 2^(result+8), add 8 to result
    result = result + (!!(x >> (result + 4))
                       << 2);  // if x >= 2^(result+4), add 4 to result
    result = result + (!!(x >> (result + 2))
                       << 1);  // if x >= 2^(result+2), add 2 to result
    result = result +
             (!!(x >> (result + 1)));  // if x >= 2^(result+1), add 1 to result
    return result;
}

isEqual

/*
 * isEqual - return 1 if x == y, and 0 otherwise
 *   Examples: isEqual(5,5) = 1, isEqual(4,5) = 0
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int isEqual(int x, int y)
{
    return !(x ^ y);
}

isLessOrEqual

/*
 * isLessOrEqual - if x <= y  then return 1, else return 0
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y)
{
    // Compute the sign bits of x and y
    int signX = x >> 31 & 1;
    int signY = y >> 31 & 1;

    // Case 1: x is negative, y is positive (x <= y is true)
    int xNegYPos = signX & ~signY;

    // Case 2: Both have the same sign
    int sameSign = !(signX ^ signY);

    // Calculate y - x
    int diff = y + (~x + 1);
    int diffSign = diff >> 31 & 1;

    // If sameSign is 1, we check the sign of the difference
    int lessOrEqualSameSign = sameSign & ~diffSign;

    // Combine the cases
    return xNegYPos | lessOrEqualSameSign;
}

isNegative

/*
 * isNegative - return 1 if x < 0, return 0 otherwise
 *   Example: isNegative(-1) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int isNegative(int x)
{
    return !!(x >> 31);
}

isNonNegative

/*
 * isNonNegative - return 1 if x >= 0, return 0 otherwise
 *   Example: isNonNegative(-1) = 0.  isNonNegative(0) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int isNonNegative(int x)
{
    return !(x >> 31);
}

isNonZero?

/*
 * isNonZero - Check whether x is nonzero using
 *              the legal operators except !
 *   Examples: isNonZero(3) = 1, isNonZero(0) = 0
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 4
 */
int isNonZero(int x)
{
    int signMask =
        x >> 31;  // Extract sign bit (all 1s if negative, 0 if non-negative)
    int negationShifted =
        (~x + 1) >> 31;  // Negate x and shift, then extract sign bit
    return signMask | negationShifted;  // Combine both results
}

isNotEqual

/*
 * isNotEqual - return 0 if x == y, and 1 otherwise
 *   Examples: isNotEqual(5,5) = 0, isNotEqual(4,5) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int isNotEqual(int x, int y)
{
    return !!(x ^ y);
}

isPallindrome

/*
 * isPallindrome - Return 1 if bit pattern in x is equal to its mirror image
 *   Example: isPallindrome(0x01234567E6AC2480) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 45
 *   Rating: 4
 */
int isPallindrome(int x)
{
    int mask = 0x1;
    int numBits = 32;  // assuming x is 32-bit

    int mirroredX = 0;
    int originalX = x;

    // Build mirroredX from originalX
    for (int i = 0; i < numBits; ++i) {
        mirroredX = (mirroredX << 1) | (originalX & mask);
        originalX >>= 1;
    }

    // Compare originalX and mirroredX
    return !(mirroredX ^ x);
}

鏡像結構（mirroredX）：

將 mirroredX 初始化為0。
迭代 originalX 的每一位：
提取 originalX 的最低有效位。
將 mirroredX 向左移動一位後，將此位元附加到 mirroredX。
將 originalX 右移一位以處理下一位。
比較 (!(mirroredX ^ x))：

使用 XOR (^) 將 MirroredX 與 x 進行比較。
如果 mirroredX 等於x，則表達式 mirroredX ^ x 將得到0。
應用邏輯非 (!) 將結果轉換為 1（如果相等）或 0（如果不相等）。

isPositive

/*
 * isPositive - return 1 if x > 0, return 0 otherwise
 *   Example: isPositive(-1) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 2
 */
int isPositive(int x)
{
    return !(x >> 31);
}

isPower2

/*
 * isPower2 - returns 1 if x is a power of 2, and 0 otherwise
 *   Examples: isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
 *   Note that no negative number is a power of 2.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 4
 */
int isPower2(int x)
{
    // Check if x is greater than 0 and has exactly one bit set
    return (x > 0) && !(x & (x - 1));
}

(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

/*
 * isZero - returns 1 if x == 0, and 0 otherwise
 *   Examples: isZero(5) = 0, isZero(0) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 2
 *   Rating: 1
 */
int isZero(int x)
{
    return !x;
}

leastBitPos

/*
 * leastBitPos - return a mask that marks the position of the
 *               least significant 1 bit. If x == 0, return 0
 *   Example: leastBitPos(96) = 0x20
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int leastBitPos(int x)
{
    return x & (~x + 1);
}

(~x + 1)：
~x + 1 有效隔離 x 的最低有效 1 位元並將所有較低位元設為 0。
(x & (~x + 1))：
此操作會產生一個掩碼，其中僅 x 的最低有效 1 位元被設定為 (1)，所有其他位元均為 0。

logicalShift

/*
 * logicalShift - shift x to the right by n, using a logical shift
 *                Can assume that 0 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int logicalShift(int x, int n)
{
    // Arithmetic shift right by n
    int arith_shifted = x >> n;

    // Mask to clear the extra bits shifted in from the left
    int mask = ~(1 << 31 >> n << 1);

    // Combine with mask for logical shift effect
    return arith_shifted & mask;
}

1 << 31 建立僅設定正負號位元 (0x80000000) 的遮罩。

$>>n$ 將此遮罩右移 n 個位置，以與算術移位中移動的位置數對齊。

$<<1$ 將其左移 1 個位置以建立一個遮罩，該遮罩清除算術移位期間從左移入的位元。
~ 補充遮罩以準備按位 AND。

對算術移位結果套用遮罩（&mask）會清除從左移入的位元

maximumOfTwo

/*
 * maximumOfTwo - compute the maximum of two integers without branching
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 4
 */
int maximumOfTwo(int x, int y)
{
    // Calculate difference
    int diff = x - y;

    // Extract sign bit of diff
    int diff_sign = diff >> 31;  // 0 if x >= y, 1 if x < y

    // Generate mask based on sign of diff
    int mask = diff_sign;

    // Return maximum of x and y
    return (x & ~mask) | (y & mask);
}

minimumOfTwo

/*
 * minimumOfTwo - compute the minimum of two integers without branching
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 4
 */
int minimumOfTwo(int x, int y)
{
    // Calculate difference
    int diff = x - y;

    // Extract sign bit of diff
    int diff_sign = diff >> 31;  // 0 if x <= y, 1 if x > y

    // Generate mask based on sign of diff
    int mask = diff_sign;

    // Return minimum of x and y
    return (x & ~mask) | (y & mask);
}

minusOne

/*
 * minusOne - return a value of -1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 2
 *   Rating: 1
 */
int minusOne(void)
{
    return ~0;
}

multFiveEighths

/*
 * multFiveEighths - multiplies by 5/8 rounding toward 0.
 *                   Should exactly duplicate effect of C expression (x*5/8),
 *                   including overflow behavior.
 *   Examples: multFiveEighths(77) = 48
 *             multFiveEighths(-22) = -13
 *             multFiveEighths(1073741824) = 13421728 (overflow)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 3
 */
int multFiveEighths(int x)
{
    int mult5 = (x << 2) + x;  // Equivalent to x * 5
    int div8 = mult5 >> 3;     // Equivalent to (x * 5) / 8

    // Adjust for negative numbers to round towards zero
    int isNegative = x >> 31;  // 0xFFFFFFFF if x is negative, 0 otherwise
    int adjust = isNegative &
                 ((mult5 & 7) &&
                  1);  // Adjust only if x is negative and remainder is non-zero

    return div8 + adjust;
}

(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

/*
 * oddBits - return word with all odd-numbered bits set to 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 2
 */
int oddBits(void)
{
    int mask = 0xAA;  // Mask for odd-numbered bits: 10101010
    int oddMask =
        mask | (mask << 8);  // 10101010 | 10101010 << 8 = 1010101010101010
    return oddMask | (oddMask << 16);  // Combine with itself for 32 bits
}

遮罩為 0xAA，表示二進位模式 10101010，覆寫最低有效位元組。
oddMask 將該遮罩與自身左移 8 位元結合，產生 0xAAAA，覆蓋 32 位元結果的前 16 位元。
最後，oddMask 與自身組合左移 16 位元以覆蓋所有 32 位，得到 0xAAAAAAAA（二進位 10101010101010101010101010101010）。
oddMask 將該遮罩與自身左移 8 位元結合，產生 0xAAAA，覆蓋 32 位元結果的前 16 位元。
最後，oddMask 與其自身組合左移 16 位以覆蓋所有 32 位，得到 0xAAAAAAAA（二進位 10101010101010101010101010101010）。

remainderPower2

/*
 * remainderPower2 - Compute x%(2^n), for 0 <= n <= 30
 *                   Negative arguments should yield negative remainders
 *   Examples: remainderPower2(15, 2) = 3, remainderPower2(-35, 3) = -3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int remainderPower2(int x, int n)
{
    int mask = (1 << n) - 1;   // Mask with n lowest bits set to 1
    int lowerBits = x & mask;  // Extract the n lowest bits of x

    // Adjust for negative numbers
    int isNegative = x >> 31;            // -1 if x is negative, 0 otherwise
    int adjust = isNegative & (1 << n);  // Add 2^n if x is negative

    return lowerBits + adjust;
}

replaceByte

/*
 * replaceByte(x,n,c) - Replace byte n in x with c
 *                      Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: replaceByte(0x12345678, 1, 0xab) = 0x1234ab78
 *   You can assume 0 <= n <= 3 and 0 <= c <= 255
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 3
 */
int replaceByte(int x, int n, int c)
{
    int shift = n << 3;              // shift = n * 8
    int mask = ~(0xFF << shift);     // mask to clear byte at position n
    int cleared_x = x & mask;        // clear byte at position n in x
    int replacement = c << shift;    // shift c into position n
    return cleared_x | replacement;  // insert c into x
}

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

/*
 * rotateLeft - Rotate x to the left by n
 *              Can assume that 0 <= n <= 31
 *   Examples: rotateLeft(0x87654321, 4) = 0x76543218
 *   Legal ops: ~ & ^ | + << >> !
 *   Max ops: 25
 *   Rating: 3
 */
int rotateLeft(int x, int n)
{
    int shift_mask = ~((~0) << n);  // Mask to capture the bits that will rotate

    int rotated_bits =
        (x >> (32 - n)) &
        shift_mask;  // Bits that will rotate to the leftmost side
    int result =
        (x << n) | rotated_bits;  // Combine rotated bits with shifted x

    return result;
}

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

/*
 * rotateRight - Rotate x to the right by n
 *               Can assume that 0 <= n <= 31
 *   Examples: rotateRight(0x87654321, 4) = 0x76543218
 *   Legal ops: ~ & ^ | + << >> !
 *   Max ops: 25
 *   Rating: 3
 */
int rotateRight(int x, int n)
{
    int rotate_mask =
        (~0) << (32 - n);  // Mask to capture the bits that wrap around

    int rotated_bits =
        (x << (32 - n)) &
        rotate_mask;  // Bits that will rotate to the rightmost side
    int result =
        (x >> n) | rotated_bits;  // Combine rotated bits with shifted x

    return result;
}

satAdd

/*
 * satAdd - adds two numbers but when positive overflow occurs, returns
 *          maximum possible value, and when negative overflow occurs,
 *          it returns minimum positive value.
 *   Examples: satAdd(0x40000000, 0x40000000) = 0x7fffffff
 *             satAdd(0x80000000, 0xffffffff) = 0x80000000
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 30
 *   Rating: 4
 */
int satAdd(int x, int y)
{
    int sum = x + y;
    int overflow = ((x ^ sum) & (y ^ sum)) >> 31;  // Check if overflow happened

    // Calculate saturated result
    int saturated_result = (overflow & ((1 << 31) ^ x)) | (~overflow & sum);

    return saturated_result;
}

sum：計算 x 和 y 的總和。
溢位：透過檢查 x、y 和 sum 的符號是否一致來偵測溢位。如果發生溢出，溢出將為 -1。
max_int 和 min_int：定義最大正值 (0x7fffffff) 和最小負值 (0x80000000) 的常數。
saturated_result：根據是否發生溢位計算結果。如果發生溢出（溢出為 -1），則根據 x 的符號選擇 max_int 或 min_int。如果沒有溢出，則傳回總和。

satMul2

/*
 * satMul2 - multiplies by 2, saturating to Tmin or Tmax if overflow
 *   Examples: satMul2(0x30000000) = 0x60000000
 *             satMul2(0x40000000) = 0x7FFFFFFF (saturate to TMax)
 *             satMul2(0x80000001) = 0x80000000 (saturate to TMin)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int satMul2(int x)
{
    int doubled = x << 1;                // x * 2
    int overflow = (x ^ doubled) >> 31;  // Check if overflow happened

    // Calculate saturated result
    int saturated_result = (overflow & (x >> 31)) | (~overflow & doubled);

    return saturated_result;
}

satMul3

/*
 * satMul3 - multiplies by 3, saturating to Tmin or Tmax if overflow
 *   Examples: satMul3(0x10000000) = 0x30000000
 *             satMul3(0x30000000) = 0x7FFFFFFF (Saturate to TMax)
 *             satMul3(0x70000000) = 0x7FFFFFFF (Saturate to TMax)
 *              satMul3(0xD0000000) = 0x80000000 (Saturate to TMin)
 *             satMul3(0xA0000000) = 0x80000000 (Saturate to TMin)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 25
 *   Rating: 3
 */
int satMul3(int x)
{
    int tripled = (x << 1) + x;  // x * 3
    int overflow1 =
        (x ^ tripled) >> 31;  // Check if overflow happened for positive x
    int overflow2 =
        tripled & (1 << 31);  // Check if overflow happened for negative x

    // Calculate saturated result
    int saturated_result =
        (overflow1 & overflow2) | (~overflow1 & ~overflow2 & tripled);

    return saturated_result;
}

sign

/*
 * sign - return 1 if positive, 0 if zero, and -1 if negative
 *   Examples: sign(130) = 1
 *             sign(-23) = -1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 2
 */
int sign(int x)
{
    int sign_bit =
        x >> 31;  // Get sign bit of x (0 for non-negative, 1 for negative)
    return sign_bit | (!!x);  // Return sign_bit for negative or non-zero, and 1
                              // for positive
}

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

/*
 * signMag2TwosComp - Convert from sign-magnitude to two's complement
 *                    where the MSB is the sign bit
 *   Example: signMag2TwosComp(0x80000005) = -5.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 4
 */
int signMag2TwosComp(int x)
{
    int sign_bit =
        x >> 31;  // Extract sign bit (0 for non-negative, 1 for negative)
    int mask =
        sign_bit << 31;  // Create mask to fill with sign bits if negative
    return (x ^ mask) +
           (sign_bit & 1);  // Convert to two's complement if negative
}

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

/*
 * specialBits - return bit pattern 0xffca3fff
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 3
 *   Rating: 1
 */
int specialBits(void)
{
    return 0xffca3fff;
}

subtractionOK

/*
 * subtractionOK - Determine if can compute x-y without overflow
 *   Example: subtractionOK(0x80000000, 0x80000000) = 1,
 *            subtractionOK(0x80000000, 0x70000000) = 0,
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int subtractionOK(int x, int y)
{
    int signX =
        (x >> 31) & 1;  // Sign bit of x (0 for positive, 1 for negative)
    int signY =
        (y >> 31) & 1;  // Sign bit of y (0 for positive, 1 for negative)
    int signResult = ((x - y) >> 31) & 1;  // Sign bit of x - y
    // Check if x and y have different signs
    int differentSigns = signX ^ signY;
    // Check if the result sign differs from x's sign
    int overflow = differentSigns & (signX ^ signResult);
    // Return 1 if no overflow, 0 if overflow
    return !overflow;
}

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

/*
 * thirdBits - return word with every third bit (starting from the LSB)
 *             set to 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 1
 */
int thirdBits(void)
{
    return 0'b0010 0100 1001 0010 0100 1001 0010 0100;
}

TMax

/*
 * TMax - return maximum two's complement integer
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmax(void)
{
    return ~(1 << 31);
}

(1 << 31) 將二進位數 1 左移 31 位元。

對結果的每一位元取反。對於 0x80000000，位元 NOT 運算結果為 0x7FFFFFFF，這是二進位補數表示形式的最大正值

tmin

/*
 * tmin - return minimum two's complement integer
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void)
{
    return 1 << 31;
}

trueFiveEighths

/*
 * trueFiveEighths - multiplies by 5/8 rounding toward 0,
 *                   avoiding errors due to overflow
 *   Examples: trueFiveEighths(11) = 6
 *             trueFiveEighths(-9) = -5
 *             trueFiveEighths(0x30000000) = 0x1E000000 (no overflow)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 25
 *   Rating: 4
 */
int trueFiveEighths(int x)
{
    int mult5 = (x << 2) + x;  // Compute 5 * x using (x << 2) + x
    int sign = mult5 >>
               31;  // Get the sign of mult5 (-1 if negative, 0 if non-negative)
    int div8 = mult5 >> 3;  // Divide mult5 by 8

    // Adjust div8 based on the sign of x
    return div8 + (sign & (x >> 31));
}

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

/*
 * trueThreeFourths - multiplies by 3/4 rounding toward 0,
 *                    avoiding errors due to overflow
 *   Examples: trueThreeFourths(11) = 8
 *             trueThreeFourths(-9) = -6
 *             trueThreeFourths(1073741824) = 805306368 (no overflow)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 4
 */
int trueThreeFourths(int x)
{
    int mult3 = (x << 1) + x;  // Compute 3 * x using (x << 1) + x
    int sign = mult3 >>
               31;  // Get the sign of mult3 (-1 if negative, 0 if non-negative)
    int div4 = mult3 >> 2;  // Divide mult3 by 4

    // Adjust div4 based on the sign of x
    return div4 + (sign & (x >> 31));
}

乘以 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

/*
 * twosComp2SignMag - Convert from two's complement to sign-magnitude
 *                    where the MSB is the sign bit
 *                    You can assume that x > TMin
 *   Example: twosComp2SignMag(-5) = 0x80000005.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 4
 */
int twosComp2SignMag(int x)
{
    int sign = x >> 31;  // Get sign of x (0 for non-negative, -1 for negative)
    int absX = (x ^ sign) + (~sign + 1);  // Absolute value of x

    // If x is negative, convert to sign-magnitude
    return (sign & 0x80000000) | absX;
}

提取正負號位元：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

/*
 * upperBits - pads n upper bits with 1's
 *             You may assume 0 <= n <= 32
 *   Example: upperBits(4) = 0xF0000000
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 1
 */
int upperBits(int n)
{
    int mask = !!n << 31;  // If n == 0, mask will be 0x00000000; otherwise, it
                           // will be 0x80000000
    mask >>= (n + ~0);     // Shift mask to position 32-n bits of 1 at MSB
    return mask;
}

!!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 個位置，從而建立所需的遮罩。

注意書寫規範：

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」和「詞彙對照表」
• 不該出現任何簡體中文字，並使用本地詞彙
• 程式碼註解不該出現中文，總是用美式英語書寫
• 用流暢的漢語書寫
• 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","

TODO: 從 Data Lab 選出可對應到真實應用的案例

最好在 Linux 核心找出相關程式碼，解說應搭配有效的測試程式碼

float_to_long

/**
 * float_to_long - Convert ieee754 reading from hardware to an integer
 *
 * @data: Value read from the hardware
 * @precision: Units to multiply up to eg. 1000 = milli, 1000000 = micro
 *
 * Return: Converted integer reading
 *
 * Depending on the measurement type the hardware returns an ieee754
 * floating point value in either volts, amps or celsius. This function
 * will convert that into an integer in a smaller unit such as micro-amps
 * or milli-celsius. The hardware does not return NaN, so consideration of
 * that is not required.
 */
static long float_to_long(u32 data, u32 precision)
{
    u64 man = data & 0x007FFFFF;
    int exp = ((data & 0x7F800000) >> 23) - 127 - 23;
    bool negative = data & 0x80000000;
    long result;

    man = (man + (1 << 23)) * precision;

    if (fls64(man) + exp > (int)sizeof(long) * 8 - 1)
        result = LONG_MAX;
    else if (exp < 0)
        result = (man + (1ull << (-exp - 1))) >> -exp;
    else
        result = man << exp;

    return negative ? -result : result;
}

遇到浮點數問題通常都會用到這 3 種遮罩
0x007FFFFF 過濾出尾數部分
0x7F800000 過濾出指數部分
0x80000000 過濾出正負號位元

parity check

static unsigned int mtdswap_test_patt(unsigned int i)
{
        return i % 2 ? 0x55555555 : 0xAAAAAAAA;
}

通常用在傳輸位元組的錯誤檢測
函數根據輸入參數 i 的奇偶性返回兩個固定模式之一：

當 i 是奇數時：
i % 2 結果為 1，返回值為 0x55555555。
0x55555555 在二進位制中為 01010101010101010101010101010101。
當 i 是偶數時：
i % 2 結果為 0，返回值為 0xAAAAAAAA。
0xAAAAAAAA 在二進位制中為 10101010101010101010101010101010。

clk_zero

static void dsi_dphy_timing_calc_clk_zero(struct msm_dsi_dphy_timing *timing,
                                        s32 ui, s32 coeff, s32 pcnt)
{
        s32 tmax, tmin, clk_z;
        s32 temp;

        /* reset */
        temp = 300 * coeff - ((timing->clk_prepare >> 1) + 1) * 2 * ui;
        tmin = S_DIV_ROUND_UP(temp, ui) - 2;
        if (tmin > 255) {
                tmax = 511;
                clk_z = linear_inter(2 * tmin, tmin, pcnt, 0, true);
        } else {
                tmax = 255;
                clk_z = linear_inter(tmax, tmin, pcnt, 0, true);
        }

        /* adjust */
        temp = (timing->hs_rqst + timing->clk_prepare + clk_z) & 0x7;
        timing->clk_zero = clk_z + 8 - temp;
}

tmax: 根據 tmin 的值來設定，如果 tmin 大於255，則 tmax 設為511，否則設為255。

read_reg

int max8998_read_reg(struct i2c_client *i2c, u8 reg, u8 *dest)
{
        struct max8998_dev *max8998 = i2c_get_clientdata(i2c);
        int ret;

        mutex_lock(&max8998->iolock);
        ret = i2c_smbus_read_byte_data(i2c, reg);
        mutex_unlock(&max8998->iolock);
        if (ret < 0)
                return ret;

        ret &= 0xff;
        *dest = ret;
        return 0;
}

這裡的 0xff 確保讀取的數據只保留低 8 位元

reverse_bytes

static __u32 reverse_bytes(__u32 b, int len)
{
        switch (len) {
        case 32:
                b = ((b & 0xffff0000) >> 16) | ((b & 0x0000ffff) << 16);
                fallthrough;
        case 16:
                b = ((b & 0xff00ff00) >> 8) | ((b & 0x00ff00ff) << 8);
                fallthrough;
        case 8:
                b = ((b & 0xf0f0f0f0) >> 4) | ((b & 0x0f0f0f0f) << 4);
                fallthrough;
        case 4:
                b = ((b & 0xcccccccc) >> 2) | ((b & 0x33333333) << 2);
                fallthrough;
        case 2:
                b = ((b & 0xaaaaaaaa) >> 1) | ((b & 0x55555555) << 1);
        case 1:
        case 0:
                break;
        default:
                printk(KERN_ERR "DBRI reverse_bytes: unsupported length\n");
        }

        return b;
}

指定的位元長度 len，使用多種位元操作來反轉整數 b 的位元順序。每個 case 語句後的 fallthrough 允許繼續執行下一個 case，

machine_restart

static void machine_restart(char *command)
{
        local_irq_disable();

        /* reboot magic */
        ltq_w32(BOOT_PW1, (void *)BOOT_PW1_REG); /* 'LTQ\0' */
        ltq_w32(BOOT_PW2, (void *)BOOT_PW2_REG); /* '\0QTL' */
        ltq_w32(0, (void *)BOOT_REG_BASE); /* reset Bootreg RVEC */

        /* watchdog magic */
        ltq_w32(WDT_PW1, (void *)WDT_REG_BASE);
        ltq_w32(WDT_PW2 |
                (0x3 << 26) | /* PWL */
                (0x2 << 24) | /* CLKDIV */
                (0x1 << 31) | /* enable */
                (1), /* reload */
                (void *)WDT_REG_BASE);
        unreachable();
}

當系統出現故障或陷入無限循環時，看門狗定時器可以強制重啟系統。設置這個位元確保了看門狗定時器的啟用，使其能夠在必要時觸發系統重啟。

hsync_polarity_show

static ssize_t hsync_polarity_show(struct device *dev,
                                   struct device_attribute *attr, char *buf)
{
        struct video_device *vdev = to_video_device(dev);
        struct mgb4_vout_dev *voutdev = video_get_drvdata(vdev);
        u32 config = mgb4_read_reg(&voutdev->mgbdev->video,
          voutdev->config->regs.hsync);

        return sprintf(buf, "%u\n", (config & (1U << 31)) >> 31);
}

提取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 位元機器編譯的程式

注意書寫規範：

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」和「詞彙對照表」
• 不該出現任何簡體中文字，並使用本地詞彙
• 程式碼註解不該出現中文，總是用美式英語書寫
• 用流暢的漢語書寫
• 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","

有號	無號	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 確認一致

void inplace_swap(int *x, int *y)
{
    *x = *x ^ *y;  // step1
    *y = *x ^ *y;  // step2
    *x = *x ^ *y;  // step3
}

透過 xor 運算達成數值交換。

位移運算與優先級問題

• 加法(和減法)優先級比移位運算高
• 由左至右結合性規則

查閱 C 語言規格書，摘錄運算子優先權相關章節。

符號	運算的類型	關聯性
[ ] ( ) . -> ++– (後置)	運算式	由左至右
sizeof & * + - ~ ! ++– (前置)	一元	由右至左
類型轉換	一元	由右至左
* / %	乘法	由左至右
+ -	加法	由左至右
<< >>	位元移位	由左至右
< > <= >=	關聯式	由左至右
== !=	等式	由左至右
&	位元 AND	由左至右
^	位元互斥 OR	由左至右
\	位元包含 OR	由左至右
&&	邏輯 AND	由左至右
\	邏輯 OR	由左至右
? :	條件運算式	由右至左
= *= /= %= += -= <<= >>= &= ^=	=	簡單和複合指派
,	循序求值	由左至右

閱讀其他學員期末專題開發紀錄並提出建議

井字遊戲模組-Willsonbo

重作第四次作業-Ken-LuWeiRu

改進 ksort-yc199911

改進 ksort-tintinjian12999

改進 ttt 作為核心模組