# CS:APP Data Lab 解題筆記
###### tags: `cs:app`
Data Lab 是 CS:APP 的第一個實驗，主要是訓練學員對於位元操作、整數和浮點數的相關概念。
## bitXor
題目需求：對兩個整數輸入 x & y, 僅使用 `~, &` 完成 XOR 函數操作
題解：
1. 先利用 ==XOR = (x & ~y) | (~x & y)== 的特性，那接下來的問題就是要如何用 `~, &` 來表示 |
2. 利用集合的概念， ==A|B = ~ (~A & ~B)==
```cpp
/*
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
int bitXor(int x, int y) {
return ~(~(x & (~y)) & ~(y & (~x)));
}
```
## tmin
題目需求：回傳最小二補數整數值
題解：將 1 左移 31 即可
```cpp
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 0x01 << 31;
}
```
## istmax
題目需求: 判斷輸入有號整數 x 是否為 Tmax
題解:
1. 利用 ==Tmax + 1 會溢出成 Tmin== 的特性， ((Tmax + 1) = Tmin) ^ Tmax + 1 = 0，對 0 做 `!` 操作為 1，寫成 bit operation 為 `!(((x+1)^x) + 1)`
2. 承 1.，由於 ==-1== 為另一個符合上述條件的數字，需要額外判斷
3. 承 2.，利用 ==!!(Tmax + 1) = !!Tmin = 1==，==!!(-1 + 1) = !! 0 = 0==
4. 將 1. & 3. 用 `&` 結合得到最終輸出
```cpp
/*
* 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) {
return !(((x+1)^x) + 1) & (!!(x+1));
}
```
## allOddBits
題目要求: 判斷是否有號整數 x 的所有奇數位元都為 1
題解:
1. 先利用==奇數位元遮罩 `~evenmask = 0xAAAAAAAA`== 將 x 所有的奇數位元取出
2. 將 1. 的結果與==偶數位元的遮罩 `evenmask = 0x55555555`== 進行 ==XOR== 操作
3. 承 2. 若 x 所有==奇數位元都是 1==，則 2. 的結果一定為 ==`0xFFFFFFFF`==
4. 將 3. 的結果 `+ 1`，如果 x 所有奇數位元都是 1 的話，會==溢出變成 0==
5. 取 `!` 得到最終結果
```cpp
/*
* 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) {
int evenmask = 0x55;
evenmask = evenmask | evenmask << 4;
evenmask = evenmask | evenmask << 8;
evenmask = evenmask | evenmask << 16;
return !(((x & ~evenmask) ^ evenmask) + 1);
}
```
## negate
題目要求: 回傳 -x
題解: 利用二補數的特性，有號整數 x 的負數為 ==(not x) + 1==
```cpp
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 0x01;
}
```
## isAsciiDigit
題目要求: 判斷輸入有號整數是否為 ASCII code 的數字 0~9 (0x30 ~ 0x39)
題解:
1. 先觀察 `0x30` & `0x39`，將兩數表達成二進位分別是 `00110000` & `00111001`，==高位的 4 個 bit 都是 `0011`==
2. 對 `0x30` 及輸入==往右偏移 4 位==將低位捨去，==再取 XOR==確認輸入 x 的 4~7 位 bit 是否符合 `0011`，若不符合則該項為 1
`int h_bit_comp = (0x30>>4) ^ (x>>4);`
3. 接著我們再觀察 `0x3a` ~ `0x3f`，其二進位低 4 位 bit 中，==第 2 或第 3 位一定其中 1 個為 1==，==第 4 位一定為 1==
4. 承 3.
- 將輸入右移 1 & 2後與 0x01(001) 取 `|` 確認 x 第 2 或第 3 位是否有 1
`int two_bit_comp = (x >> 1) & 0x01;`
`int three_bit_comp = (x >> 2) & 0x01;`
- 將輸入右移 3 後與 0x01(0001) 取 `&` 確認 x 第 4 位是否為 1，若為 1 則該項為 1
`int forth_bit_comp = (x >> 3) & 0x01;`
5. 對第 4. 點兩個表達式的結果先單獨取 & ，當==兩個條件都符合時，代表低 4 位大於 9==
6. 對第 2. 點及第 5. 點的結果個別取 `!` 後再取 `&` 即為答案
```cpp
/*
* 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 h_bit_comp = (0x30>>4) ^ (x>>4);
int two_bit_comp = (x >> 1) & 0x01;
int three_bit_comp = (x >> 2) & 0x01;
int forth_bit_comp = (x >> 3) & 0x01;
return !h_bit_comp & !((two_bit_comp | three_bit_comp) & forth_bit_comp);
}
```
這題覺得自己有點硬解了，所以上網查了其他人的實作，以下參考[[連結]](https://zhuanlan.zhihu.com/p/59534845) ，個人認為比較符合題目設定的目的，也解得漂亮許多:
1. 設定一個 UpperBound，讓==大於 `0x39` 的數加上它會溢出變成負數==
2. 設定一個 LowerBound，讓==小於 `0x30` 的數加上會為負數==
3. 將輸入 x 分別加上 UpperBound & LowerBound，右移 31 bit 後與 `sign` 做 `&` 操作判斷數值的正負
4. 當有任何一個數為負時，代表超出範圍，`!(upperBound|lowerBound)` 回傳 0; 反之回傳 1
```cpp
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
題目要求: 以位元運算達到三元運算的功能
題解:
1. 當 x != 0 時，要回傳 y；反之要回傳 z，因此解題的邏輯為 y & z 各利用一個表達式計算回傳值，==符合條件的表達式回傳原數值 (y or z)；不符條件的表達式回傳 0==，再用 Or 操作回傳非 0 項
2. 對 y 來說， x != 0 時要回傳 y，反之回傳 0，所以要設計一個表達式，x != 0 時為 `0xFFFFFFFF`；x = 0 時為 `0x00000000` --> `~((!x<<31)>>31)`
3. 對 z 來說， x != 0 時要回傳 0，反之回傳 z，所以要設計一個表達式，x != 0 時為 `0x00000000`；x = 0 時為 `0xFFFFFFFF` --> `((!x<<31)>>31)`
4. 將兩個表達式取 `Or` 得到最終答案
```cpp
/*
* conditional - same as x ? y : z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) {
int cond_1 = ~((!x<<31)>>31)&y;
int cond_2 = ((!x<<31)>>31)&z;
return cond_1 | cond_2;
}
```
## isLessOrEqual
題目要求: 利用位元運算完成 `<=` 的邏輯操作
題解:
1. 一些基本的解題方向如下
- x <= y 等同於判斷 ==x - y <= 0== 是否為真
- x - y 在==沒有溢出==的情況下可寫成 ==`x + ~y + 1`==
- 承 2.，在 x & y ==同號的情況下不會溢出==，僅在不同號時有機會發生
- 因此若 x & y 不同號則改判斷是否 ==`x > 0 & y < 0`==
2. 當 x & y 同號時，我們判斷 x - y 為正或負值，另外==需考慮 `=` 的情況==，所以多了
`| !x_minus_y`
`same_sign & ((x_minus_y >> 31) | !x_minus_y)`
3. 若 x & y 不同號則判斷是否 `x > 0 & y < 0`
`(!(~sign_x & 0x1) & !(sign_y & 0x1))`
4. 第 2. & 3. 點有一個條件為真代表 `x <= y`
```cpp
/*
* 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) {
int sign_x = x >> 31;
int sign_y = y >> 31;
int same_sign = !(sign_x ^ sign_y);
int x_minus_y = x + (~y) + 1;
return (same_sign & ((x_minus_y >> 31) | !x_minus_y)) | (!(~sign_x & 0x1) & !(sign_y & 0x1));
}
```
## 練習題 2.66 leftmost_one
額外練習習題 2.66，給定一個 32-bit 無號數，回傳最大 bit 為 1 的遮罩，如 0xFF00 -> 0x8000，若 x = 0 則回傳 0
1. 先將==最高位(含)以下==的位元全部以 1 填滿，透過 ==`mask |= mask >> 2^n`== 的操作，每次填滿 2 的冪次個 1，由 n = 0 -> n = 4 即可填滿 32 位元
2. 填滿後==先右移 1 個位元== (先加 1 有可能 overflow) ==再加上 1==
3. 要考慮 x 為零的情況，所以要==與自身做 `&` 運算==
```cpp
int leftmost_one(unsigned x) {
unsigned mask = x;
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;
return x & ((mask >> 1) + 1);
}
int main() {
printf("Left most bit of 0xff00 is 0x%x\n", leftmost_one(0xff00));
printf("Left most bit of 0x6600 is 0x%x\n", leftmost_one(0x6600));
printf("Left most bit of 0x0001 is 0x%x\n", leftmost_one(0x0001));
printf("Left most bit of 0x0000 is 0x%x\n", leftmost_one(0x0000));
}
Left most bit of 0xff00 is 0x8000
Left most bit of 0x6600 is 0x4000
Left most bit of 0x0001 is 0x1
Left most bit of 0x0000 is 0x0
```
## logicalNeg
題目要求: 以位元操作完成 `!` 運算子，注意不得使用 `!`
題解:
1. 本題重點要利用 ==`~0 + 1 = 0`== 的特性
2. `~x + 1` 在二補數系統下，等於 x 取負號，除了 0 以外，其他==整數與其負數的最高位 bit 必定一個為 0 一個為 1==
3. 總和 1. & 2.，x = 0 時 ==`(~x + 1) | x`== 最高位一定為 0；反之一定為 1
4. 將==最高位 bit 右移 31 之後取 `~`== ， x = 0 時為 `0xFFFFFFFF`；反之為 `0x00000000`
5. 將第 4. 點之結果與 ==`0x1` 取 &== 將最低位 bit 抓出來即為回傳值
```cpp
/*
* 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 + 1) | x) >> 31) & 0x1;
}
```
## Reference
1. [Computer Systems: A Programmer's Perspective, 3/E (CS:APP3e)](http://csapp.cs.cmu.edu/3e/labs.html)
Sign in with Wallet
Connect another wallet