## Linux 核心專題: Data Lab
> 執行人: Terry7Wei7
> [解說影片-1](https://youtu.be/Mqs41AB9sPM)
> [解說影片-2](https://youtu.be/01d1JSgaW_c)
### Reviewed by `Daniel-0224`
```c
int copyLSB(int x)
{
- return !!(x & 1) + ~0;
+ return (x & 1) * -1;
}
```
改為使用 `diff` 才能顯示出增加及刪減的程式碼。
```diff
int copyLSB(int x)
{
- return !!(x & 1) + ~0;
+ return (x & 1) * -1;
}
```
### Reviewed by `david965154`
>直接回傳 0X55555555 應該也可以
`int` 在 16 位元系統中並不適用直接回傳 0X55555555
參考 : [Integer (computer science)](https://en.wikipedia.org/wiki/Integer_(computer_science))
## 任務簡介
針對 CS:APP 的 [Data Lab](https://csapp.cs.cmu.edu/3e/labs.html)，提出有效的解法，規範：
* 自 GitHub 上 fork [datalab](https://github.com/sysprog21/datalab)，依據 [Data Lab: Manipulating Bits](http://csapp.cs.cmu.edu/3e/datalab.pdf)，補完欠缺的程式碼，並且通過自動測試
* 確保儘可能少的指令，可用 `$ gcc -S bits.c` 輸出組合語言並觀察 `bits.s` 的程式碼裡頭的 x86 指令
* 避免用分支 (branch)，設計時間複雜度為 $O(1)$ 的實作
* 選出其中 7 個位元操作的函式，詳細解釋其原理，需要比照 [clz 應用](https://hackmd.io/s/Bk-uxCYxz) 和 [bit-reverse](https://hackmd.io/s/ByzoiggIb) 的分析方式，==舉出真實世界中的應用案例== (最好在 Linux 核心找出相關程式碼)，解說應搭配有效的測試程式碼
* 探討讓 [datalab](https://github.com/sysprog21/datalab) 得以 64-bit friendly 的提案，並舉出實際程式碼修改
參考資訊:
* [CS:APP Data Lab 解題筆記](https://hackmd.io/@Chang-Chia-Chi/CSAPP_DataLab)
* [Data lab 紀錄](https://hackmd.io/@justapig9020/B1VUv6wX9)
* [Data Lab 作業區](https://hackmd.io/@sysprog/S1CRTc8jX)
## TODO: Data Lab 解題
> 確保儘可能少的指令
### absolute value
```c
/*
* 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;
:::danger
bit 的翻譯是「位元」，而非「位」，後者是量詞。
sign bit 的翻譯是「正負號位元」，避免濫用「符」這字。
參閱教育部重編國語詞典的「[符](https://dict.revised.moe.edu.tw/dictView.jsp?ID=1816)」的解釋。
:::
將 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
```c
/*
* 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);
}
```
:::danger
避免僅進行程式碼逐行解說 (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
```c
/*
* 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);
}
```
:::danger
避免僅進行程式碼逐行解說 (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
```c
/*
* 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);
}
```
:::danger
避免僅進行程式碼逐行解說 (ChatGPT 也會！)，而是你該從程式碼設計者的角度，闡述「你為何當初想要這樣作？」「更早之前我嘗試用別的方式，遇到什麼問題」等高階想法，避免淪落為「舉燭」。
:::
`int mask = 0x55555555;`
定義了一個位元遮罩，其所有偶數位元為 1。
`(x & mask)`
將 x 和 mask 進行位元運算，保留 x 中的所有偶數位元。
`!!(x & mask)`
將結果進行邏輯非運算兩次。第一次邏輯非將非零值轉換為 0，將零值轉換為 1。第二次邏輯非將其結果再次取反，即將非零值轉換為 1，將零值保持為 0。最終，如果有任意一個偶數位為 1，則回傳 1；否則回傳 0。
### anyOddBit
```c
/*
* 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);
}
```
:::danger
避免僅進行程式碼逐行解說 (ChatGPT 也會！)，而是你該從程式碼設計者的角度，闡述「你為何當初想要這樣作？」「更早之前我嘗試用別的方式，遇到什麼問題」等高階想法，避免淪落為「舉燭」。
:::
`int mask = 0xAAAAAAAA;`
定義一個位元遮罩，其所有奇數位為1。
`(x & mask)`
將 x 和 mask 進行位元運算，保留 x 中的所有奇數位元。
`!!(x & mask)`
將結果進行邏輯非運算兩次。第一次邏輯非將非零值轉換為0，將零值轉換為1。第二次邏輯非將其結果再次取反，即將非零值轉換為1，將零值保持為0。最終，如果有任意一個奇數位為1，則回傳1；否則回傳0。
### bang
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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 的個數
:::danger
避免僅進行程式碼逐行解說 (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
```c
/*
* 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 + \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
```
/*
* 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 = {\overline{A}} \cdot {\overline{B}}$
### bitOr
```c
/*
* 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{\overline{A+B}}$
$Y = \overline{\overline{A}\cdot\overline{B}}$
### bitParity
```c
/*
* 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
```c
/*
* 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)
```c
/*
* 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 {\overline {B}}+{\overline {A}}\cdot B}$
:::danger
在 108 課綱，譯作「笛摩根定律」
:::
<s>第摩根定理</s> 互換
${Y=\overline{{\overline {A\cdot {\overline {B}}}}\cdot{\overline {{\overline {A}}\cdot B}}}}$
### byteSwap
```c
/*
* 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()
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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)
```c
/*
* 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)
```c
/*
* 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
```c
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)
```c
/*
* 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?
```c
/*
* 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?
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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$的操作，同時確保向零舍入[捨入誤差](https://zh.wikipedia.org/zh-tw/%E6%8D%A8%E5%85%A5%E8%AA%A4%E5%B7%AE)。
可以理解成LSB的權重是 $2^0 = 1$，所以他是影響 X 是不是奇數的因素，其他位元皆可被 2 整除，所以我們在右移的時候要計算偏移量，將結果 +1
#### 為什麼只有在 X 為負數的時候需要考慮這個問題
右移操作對正數的行為
對於正數，右移操作相當於整數除以 2 的對應次方並向下取整。例如：
```C
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 次方（向下取整）。
```c
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
```C
/*
* 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
```C
/*
* 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?
```C
/*
* 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)
```c
/*
* 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)
```c
/*
* 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)
```c
/* 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)
```c
/*
* 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)
```c
/*
* 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)
```c
/*
* 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?
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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?
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* minusOne - return a value of -1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 2
* Rating: 1
*/
int minusOne(void)
{
return ~0;
}
```
### multFiveEighths
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* specialBits - return bit pattern 0xffca3fff
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 3
* Rating: 1
*/
int specialBits(void)
{
return 0xffca3fff;
}
```
### subtractionOK
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void)
{
return 1 << 31;
}
```
### trueFiveEighths
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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
```c
/*
* 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 個位置，從而建立所需的遮罩。
:::danger
注意書寫規範：
* 無論標題和內文中，**中文和英文字元之間要有空白字元** (對排版和文字搜尋有利)
* 留意科技詞彙的使用，請參見「[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)」和「[詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)」
* 不該出現任何簡體中文字，並使用本地詞彙
* 程式碼註解不該出現中文，總是用美式英語書寫
* 用流暢的漢語書寫
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
* 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","
:::
## TODO: 從 Data Lab 選出可對應到真實應用的案例
> 最好在 Linux 核心找出相關程式碼，解說應搭配有效的測試程式碼
### float_to_long
```c
/**
* 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
```C
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
```c
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
```c
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
```c
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
```c
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
```c
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)
:::danger
注意用語：
* bit 的翻譯是「位元」，而非「位」，後者是量詞
* compatible 是「相容」
* signed integer 是「有號整數」，而非「有符號」
* byte 是「位元組」，而非「字節」，抖音不要看太多
* 務必使用本課程教材的詞彙和慣例
:::
int 正整數，遇到 overflow 會產生溢出，從而變負數
浮點數，遇到 overflow 會產出特殊值 +ini
32 bits = 4 GB
64 bits = 16 GB
通常 64 位元可以相容 32 位元機器編譯的程式
:::danger
注意書寫規範：
* 無論標題和內文中，**中文和英文字元之間要有空白字元** (對排版和文字搜尋有利)
* 留意科技詞彙的使用，請參見「[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)」和「[詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)」
* 不該出現任何簡體中文字，並使用本地詞彙
* 程式碼註解不該出現中文，總是用美式英語書寫
* 用流暢的漢語書寫
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
* 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","
:::
| 有號 | 無號 | 32 位元<s>字節數</s> 位元組數量 | 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,其特性是位元組<s>字節</s> 大小固定,不隨編譯器和機器設置而變化
### 練習 2.10
:::danger
注意書寫規範：
* 無論標題和內文中，漢字和英語字元之間要有空白字元 (對排版和文字搜尋有利)
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
```c
void inplace_swap(int *x, int *y)
{
*x = *x ^ *y; // step1
*y = *x ^ *y; // step2
*x = *x ^ *y; // step3
}
```
透過 xor 運算達成數值交換。
位移運算與優先級問題
* 加法(和減法)優先級比移位運算高
* 由左至右結合性規則
:::danger
查閱 C 語言規格書，摘錄運算子優先權相關章節。
:::
| 符號 | 運算的類型 | 關聯性 |
| ---- | -------------------- | ---------- |
| [ ] ( ) . -> ++-- (後置) | 運算式 | 由左至右 |
| sizeof & * + - ~ ! ++-- (前置) | 一元 | 由右至左 |
| 類型轉換 | 一元 | 由右至左 |
| * / % | 乘法 | 由左至右 |
| + - | 加法 | 由左至右 |
| << >> | 位元移位 | 由左至右 |
| < > <= >= | 關聯式 | 由左至右 |
| == != | 等式 | 由左至右 |
| & | 位元 AND | 由左至右 |
| ^ | 位元互斥 OR | 由左至右 |
| \ | 位元包含 OR | 由左至右 |
| && | 邏輯 AND | 由左至右 |
| \\ | 邏輯 OR | 由左至右 |
| ? : | 條件運算式 | 由右至左 |
| = *= /= %= += -= <<= >>= &= ^= |= | 簡單和複合指派 | 由右至左 |
| , | 循序求值 | 由左至右 |
## 閱讀其他學員期末專題開發紀錄並提出建議
[井字遊戲模組-Willsonbo](https://hackmd.io/@sysprog/BkIOuG2VA)
[重作第四次作業-Ken-LuWeiRu](https://hackmd.io/ilF4J8G5SZ2D2OHGNcCDeQ)
[改進 ksort-yc199911](https://hackmd.io/@sysprog/SkjrHaxP0)
[改進 ksort-tintinjian12999](https://hackmd.io/@sysprog/BkqsnDc8R)
[改進 ttt 作為核心模組](https://hackmd.io/M5-ijGWrRLOgs2lHBtkTYw)
Sign in with Wallet
Connect another wallet