CS:APP Data Lab 解題筆記

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

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.