# 2018q3 Homework5 (bits) contributed by < [`p61402`](https://github.com/p61402) > ###### tags: `sysprog` ## 建立環境 安裝 32-bit 的開發套件時出現以下錯誤： ```bash $ sudo apt install libc6-dev:i386 gcc:i386 Reading package lists... Done Building dependency tree Reading state information... Done Some packages could not be installed. This may mean that you have requested an impossible situation or if you are using the unstable distribution that some required packages have not yet been created or been moved out of Incoming. The following information may help to resolve the situation: The following packages have unmet dependencies: gcc:i386 : Depends: cpp:i386 (>= 4:5.3.1-1ubuntu1) but it is not going to be installed Depends: gcc-5:i386 (>= 5.3.1-3~) but it is not going to be installed E: Unable to correct problems, you have held broken packages. ``` 看起來似乎是套件相依性的問題，試了好多方法都沒辦法解決，因此決定下載另外一個 cross-compiling 的套件[`gcc-multilib`](https://www.geeksforgeeks.org/compile-32-bit-program-64-bit-gcc-c-c/)試試看能不能 run： ```bash sudo apt-get install gcc-multilib ``` 安裝成功了！試著`make`看看能不能夠編譯： ```bash $ make gcc -O0 -g -Wall -Werror -m32 -lm -o btest bits.c btest.c decl.c tests.c gcc -O0 -g -Wall -Werror -m32 -o fshow fshow.c gcc -O0 -g -Wall -Werror -m32 -o ishow ishow.c ``` 總分是 228 分，但是 CMU 原版的作業滿分只有 76 分，稍微看了一下`bit.c`，發現這次作業要實作的 function 居然高達 85 個，看來得加把勁了！ ```bash ./btest ... ... Total points: 0/228 ``` --- ## 關卡一 來自正整數的戰帖：位元操作的挑戰 **關卡限制** - 只可使用`int`型別，最大能宣告範圍從`0 ~ 0xFF`，不可使用像是`0xFFFFFFFF`的大數 - 不可使用全域變數 - 只能使用下列運算子：`!` `~` `&` `^` `|` `+` `<<` `>>`，限制會隨著每道題目而有所不同，因此以每道題目的規定為主 - 不可使用`condition`、`loop`等 - 不可使用任何`macro` - 不可宣告、呼叫任何的函式 - 不可使用不可規定以外的運算子，例如：`&&` `||` `-` `?` - 不可使用任何轉型 (casting) - 不可使用任何衍生的型別，例如：`array` `union` `struct ` - `int`整數為 32-bit，使用二補數表示法 - 右移為 arithmetic right shift - 位移的單位小於 0 或是大於 31 都會導致不可預測的行為 ### absVal 幾週前的測驗題解法如下： ```c= int absVal(int x) { return (x ^ (x >> 31)) - (x >> 31); } ``` 但是不能使用`-`運算子，原本計算二補數的方法是取一補數加一，那麼改成減一再取一補數結果應該要是相同的。 在`x`為非負整數的情況下，由於 sign extension 的原因，`x >> 31`的值為`0`，因此計算的結果依然為`x`。 而在`x`為負整數的情況下，`x >> 31`的值為`0xFFFFFFFF`，因此結果等同於計算二補數。 ```c= int absVal(int x) { return (x + (x >> 31)) ^ (x >> 31); } ``` ### addOK 將 x 與 y 所有可能的組合列出來： |x|y|x+y|return| |:-:|:-:|:-:|:-:| |+|+|+|1| |+|+|-|0| |+|-|+|1| |+|-|-|1| |-|+|+|1| |-|+|-|1| |-|-|+|0| |-|-|-|1| 當兩個正數相加結果為負數，或是兩個負數相加結果為正數時，表示 overflow 發生。 因此當 x 與 y 的 sign bit 相同時，若 x + y 的 sign bit 與前者不同，即代表發生 overflow。 #### 版本一 ```c= int addOK(int x, int y) { return (((x ^ y) >> 31) & 0x1) || !((((x + y) ^ (x & y)) >> 31) & 0x1); } ``` 由於不能使用邏輯運算子`||`，所以改一下程式碼： #### 版本二 ```c= int addOK(int x, int y) { int same = !(((x ^ y) >> 31) & 0x1); int sign = ((x + y) >> 31) & 0x1; return !(same & (sign ^ ((x >> 31) & 0x1))); } ``` 總共使用 12 個運算子，規定上限為 20 個，還在範圍內，不過應該還能夠再更精簡。 ### allEvenBits #### 版本一 最直觀的做法，將所有偶數的 bit 取出進行比對，但很明顯地超出了可使用運算子的上限。 ```c= int allEvenBits(int x) { return x & (x >> 2) & (x >> 4) & (x >> 6) & (x >> 8) & (x >> 10) & (x >> 12) & (x >> 14) & (x >> 16) & (x >> 18) & (x >> 20) & (x >> 22) & (x >> 24) & (x >> 26) & (x >> 28) & (x >> 30) & 1; } ``` #### 版本二 參考 [stackoverflow](https://stackoverflow.com/questions/25952658/c-determining-all-if-all-even-bits-are-set-to-1) 上的方法，將`x`對折再對折，概念如下： ![allEvenBits](https://i.imgur.com/2HL79eu.png) `x &= x >> 16`這行程式碼將`x`與`x`右移 16-bit 的結果進行`&`，目的是將`x`的前半段與`x`的後半段對齊進行`&`計算，有意義的結果就會剩下`x`後半段的部分，以此類推不停地將`x`對折，直到剩下 2 個有意義的 bit 時，第 0 個 bit 就是我們要求的值， ```c= int allEvenBits(int x) { x &= x >> 16; x &= x >> 8; x &= x >> 4; x &= x >> 2; return x & 1; } ``` ### allOddBits 與`allEvenBits`的做法相同，只是要取的是第 1 個 bit。 ```c= int allOddBits(int x) { x &= x >> 16; x &= x >> 8; x &= x >> 4; x &= x >> 2; return (x >> 1) & 1; } ``` ### anyEvenBit 與`allEvenBits`的做法類似，但是將`&`改成`|`。 ```c= int anyEvenBit(int x) { x |= x >> 16; x |= x >> 8; x |= x >> 4; x |= x >> 2; return x & 1; } ``` ### anyOddBit 與`allOddBit`的做法類似，但是將`&`改成`|`。 ```c= int anyOddBit(int x) { x |= x >> 16; x |= x >> 8; x |= x >> 4; x |= x >> 2; return (x >> 1) & 1; } ``` ### bang 在不能用`!`的條件下實作`!x`。 要檢查`x`是否為`0`只能將所有 bit 檢查一輪，因此利用前幾題的技巧，將所有的 bit 進行`&`運算，若結果為`0`回傳`1`，反之則回傳`0`。 ```c= int bang(int x) { x |= x >> 16; x |= x >> 8; x |= x >> 4; x |= x >> 2; x |= x >> 1; return (x ^ 1) & 1; } ``` 剛好壓線使用 12 個運算子，不過看起來要再精簡應該有點困難。 ### bitAnd According to [De Morgan's Law](https://en.wikipedia.org/wiki/De_Morgan%27s_laws), $\overline{A \cap B} = \overline A \cup \overline B$ $\Rightarrow A \cap B = \overline{\overline A \cup \overline B}$ ```c= int bitAnd(int x, int y) { return ~(~x | ~y); } ``` ### BitCount #### 版本一 想破頭也想不出來的一題，利用 divide and conquer 將 bit 兩兩相加。 ```c= int bitCount(int x) { int c; c = (x & 0x55555555) + ((x >> 1) & 0x55555555); c = (c & 0x33333333) + ((c >> 2) & 0x33333333); c = (c & 0x0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F); c = (c & 0x00FF00FF) + ((c >> 8) & 0x00FF00FF); c = (c & 0x0000FFFF) + ((c >> 16) & 0x0000FFFF); return c; } ``` 以 8-bit 為例： ``` 11 01 01 00 # x 01 01 01 01 # 0x55 01 01 01 00 # x & 0x55 01 00 00 00 # (x >> 1) & 0x55 10 01 01 00 # c = (x & 0x55) + ((x >> 1) & 0x55) 00 11 00 11 # 0x33 00 01 00 00 # c & 0x33 00 10 00 01 # (c >> 2) & 0x33 00 11 00 01 # c = c & 0x33) + ((c >> 2) & 0x33) 00 00 11 11 # 0x0F 00 00 00 01 # c & 0x0F 00 00 00 11 # (c >> 4) & 0x0F 00 00 01 00 # c = (c & 0x0F) + ((c >> 4) & 0x0F) ``` #### 版本二 不能用大於`0xFF`的值，自己造！ ```c= int bitCount(int x) { int a0 = 0xFF | (0xFF << 8); int a1 = a0 ^ (a0 << 8); int a2 = a1 ^ (a1 << 4); int a3 = a2 ^ (a2 << 2); int a4 = a3 ^ (a3 << 1); x = (x & a4) + ((x >> 1) & a4); x = (x & a3) + ((x >> 2) & a3); x = (x & a2) + ((x >> 4) & a2); x = (x & a1) + ((x >> 8) & a1); x = (x & a0) + ((x >> 16) & a0); return x; } ``` ### BitMask 在 32-bit 的`int`中，從 lsb 到 msb 依序編號第 0 個 bit 到第 31 個 bit，回傳一個`int`型別的值，編號`lowbit`到`highbit`的 bit 設為 1 (inclusive)，其他設為 0。 以 8-bit 當做例子： ``` n = 1111 1111 n << 3 = 1111 1000 n << 5 = 1110 0000 # 左移 5 個 bit 只能設定 0 ~ 4 (n << 5 << 1) = 1100 0000 # 左移 6 個 bit 才能設定 0 ~ 5 ~(n << 5 << 1) = 0011 1111 (n << 3) & ~(n << 5 << 1) = 0011 1000 ``` 考量到`highbit`最大值等於`31`，由於不能一次位移`32`個位元，因此拆成兩個步驟寫成`n << highbit << 1`。 ```c= int bitMask(int highbit, int lowbit) { int n = ~0; return (n << lowbit) & ~(n << highbit << 1); } ``` ### bitMatch 比較`x`與`y`相同的 bit。 `x & y`可以得到兩個 bit 都是`1`的位置，`~x & ~y`可以得到兩個 bit 都是`0`的位置。 再將兩個結果做`|`運算，但是規定只能用`&`及`~`實作，因此再次呼叫 De Morgan's Law，利用`&`及`~`實作出`|`： $\overline{A \cup B} = \overline A \cap \overline B$ $\Rightarrow A \cup B = \overline{\overline A \cap \overline B}$ ```c= int bitMatch(int x, int y) { return ~(~(x & y) & ~(~x & ~y)); } ``` ### bitNor De Morgan's Law ```c= int bitNor(int x, int y) { return ~x & ~y; } ``` ### bitOr De Morgan's Law ```c= int bitOr(int x, int y) { return ~(~x & ~y); } ``` ### bitParity 奇數個 bit 回傳 1，偶數個 bit 回傳 0。 ```c= int bitParity(int x) { x ^= x >> 16; x ^= x >> 8; x ^= x >> 4; x ^= x >> 2; x ^= x >> 1; return x & 1; } ``` ### bitReverse 參考 [stackoverflow](https://stackoverflow.com/questions/746171/most-efficient-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c) 上的方法，由大至小兩兩交換： ![](https://i.imgur.com/6wdOxeh.jpg) 由於不能使用大於`0xFF`的值，因此得自己想辦法產生： ```c= int bitReverse(int x) { int a0 = 0xFF | (0xFF << 8); // 0x0000ffff int a1 = a0 ^ (a0 << 8); // 0x00ff00ff int a2 = a1 ^ (a1 << 4); // 0x0f0f0f0f int a3 = a2 ^ (a2 << 2); // 0x33333333 int a4 = a3 ^ (a3 << 1); // 0x55555555 x = (x << 16) | ((x >> 16) & a0); x = ((x & a1) << 8) | ((x >> 8) & a1); x = ((x & a2) << 4) | ((x >> 4) & a2); x = ((x & a3) << 2) | ((x >> 2) & a3); return ((x & a4) << 1) | ((x >> 1) & a4); } ``` 總共使用 33 個運算子。 ### bitXor $A\oplus B = \lnot ((A\land B)\lor (\lnot A\land \lnot B))$ 利用 De Morgan's Law 將 or 改為 and。 ```c= int bitXor(int x, int y) { return ~(x & y) & ~(~x & ~y); } ``` ### byteSwap - `n_shift`：`n` x 8 - `m_shift`：`m` x 8 - `remain`：`x`維持不變的 2 個 byte - `n_byte`：將第`n`個 byte 移到第`m`個位置 - `m_byte`：將第`m`個 byte 移到第`n`個位置 以`n_byte`為例，取出第`n`個 byte，右移到最左方後再移到第`m`個 byte，雖然將負數右移是 implementation-defined，但由於要取的 bit 不會受到影響，只要與`0xFF`做`&`的運算就可以去除其他的 bit。 ```c= int byteSwap(int x, int n, int m) { int a = 0xFF; int n_shift = n << 3; int m_shift = m << 3; int remain = x & ~((a << n_shift) | (a << m_shift)); int n_byte = (a & ((x & (a << n_shift)) >> n_shift)) << m_shift; int m_byte = (a & ((x & (a << m_shift)) >> m_shift)) << n_shift; return remain | n_byte | m_byte; } ``` ### conditional - `x = !!x`：將非零值變為`1`，零依舊為`0`。 - `x = ~x + 1`：將`x`做二補數，`1`變成`0xFFFFFFFF`，`0`依舊為`0`。 - `return (x & y) | (~x & z)`：`x`是`~x`分別為`0x0`與`0xFFFFFFF`，或是互換。 ```c= int conditional(int x, int y, int z) { x = !!x; x = ~x + 1; return (x & y) | (~x & z); } ``` ### countLeadingZero ```c= int countLeadingZero(int x) { int a0 = 0xFF | (0xFF << 8); int a1 = a0 ^ (a0 << 8); int a2 = a1 ^ (a1 << 4); int a3 = a2 ^ (a2 << 2); int a4 = a3 ^ (a3 << 1); x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x = ~x; x = (x & a4) + ((x >> 1) & a4); x = (x & a3) + ((x >> 2) & a3); x = (x & a2) + ((x >> 4) & a2); x = (x & a1) + ((x >> 8) & a1); x = (x & a0) + ((x >> 16) & a0); return x; } ``` ### copyLSB 取最後一個 bit 做二補數，因為`0`的二補數是`0`，`1`的二補數是`-1`。 ```c= int copyLSB(int x) { return ~(x & 1) + 1; } ``` ### distinctNegation 不解釋 >< ```c= int distinctNegation(int x) { return !!((~x + 1) ^ x); } ``` ### dividePower2 ```c= int dividePower2(int x, int n) { return (x + ((x >> 31) & ((1 << n) + ~0))) >> n; } ``` ### evenBits 複製再複製。 ```c= int evenBits(void) { int x = 0x55; x |= (x << 8); x |= (x << 16); return x; } ``` ### ezThreeFourths ```c= int ezThreeFourths(int x) { int add; x = (x << 1) + x; add = (x >> 31) & 3; return (x + add) >> 2; } ``` ### fitsBits ```c= int fitsBits(int x, int n) { int shift = 32 + (~n + 1); return !(x ^ (x << shift >> shift)); } ``` 以`x = 5`，`n = 3`為例： - `shift`= 32 - 3 = 29 - `(x << shift) >> shift`：利用 sign extension 的特性，得到 5 在 3-bit 時所代表的值，以 32-bit 表示 ``` x = 0000 0000 0000 0000 0000 0000 0000 0101 x << 29 = 1010 0000 0000 0000 0000 0000 0000 0000 x << 29 >> 29 = 1111 1111 1111 1111 1111 1111 1111 1101 ``` 若 5 可用 3-bit 表示，則`x`應該與`x >> 29 << 29`的值相同。 ### fitsShort 上一題在 n = 16 時的狀況。 ```c= int fitsShort(int x) { return !(x ^ (x << 16 >> 16)); } ``` --- ## 關卡二 逐漸解開的謎團：浮點數的奧秘 終於解放啦！ **整數關卡通關獎勵** - `unsigned`型別解鎖 - `condition`與`loop`解鎖 - 算數、邏輯、比較運算子解鎖 - 整數範圍限制解鎖，現在可以直接使用大於`0xFF`的數了 - 注意不可使用任何的 floating data type ### floatAbsVal 可以使用大數之後，要造出 mask 就簡單許多啦，記得考慮到`NaN`的處理就可以了。 ```c= unsigned floatAbsVal(unsigned uf) { unsigned exp = (uf & 0x7F800000) >> 23; unsigned frac = (uf & 0x007FFFFF); if (exp == 0xFF && frac != 0) return uf; return 0x7FFFFFFF & uf; } ``` ### floatFloat2Int 不斷 try and error 的一題...考驗對浮點數的熟悉度，看來我是不及格... 注意要點： - 若指數項小於`0`，回傳`0` - 若指數項超過`31`，即為 out of range，依照題目要求回傳`0x80000000u` - `frac`項只能擷取小數部分，小數點前方的`1`得自己補 - `frac`項佔據 23 個位元，當`exp`的值小於`23`時要右移，大於`23`時要左移，以移動到正確的位置 - 最後記得若`uf`表示的浮點數負數，要將結果進行二補數運算轉成負數 ```c= int floatFloat2Int(unsigned uf) { unsigned sign = (uf & 0x80000000) >> 31; int exp = ((uf & 0x7F800000) >> 23) - 127; unsigned frac = (uf & 0x007FFFFF) | 0x00800000; unsigned num; if (exp < 0) return 0; else if (exp > 31) return 0x80000000u; if (exp < 23) num = frac >> (23 - exp); else num = frac << (exp - 23); if (sign) return ~num + 1; return num; } ``` ### floatInt2Float 這題需要考慮到捨入的問題，想得頭很痛，之後再來補解釋。 ```c= unsigned floatInt2Float(int x) { int sign = x & 0x80000000; int exp = -1; int frac = 0; if (x == 0) return 0; else if (x == 0x80000000) return 0xcf000000; if (sign) x = ~x + 1; frac = x; while (x) { x /= 2; exp++; } if (exp <= 23) frac <<= (23 - exp); else { frac += (1 << (exp - 24)); if (!(frac << (55 - exp))) frac &= (0xFFFFFFFF << (exp - 22)); if (!(frac & (1 << exp))) exp++; frac >>= (exp - 23); } frac &= 0x007fffff; exp = (exp + 127) << 23; return sign | exp | frac; } ``` ### floatIsEqual ```c= int floatIsEqual(unsigned uf, unsigned ug) { unsigned uf_usb = uf & 0x7FFFFFFF, ug_sub = ug & 0x7FFFFFFF; if (!(uf_usb | ug_sub)) return 1; if (uf_usb > 0x7F800000 || ug_sub > 0x7F800000) return 0; return uf == ug; } ``` 什麼鬼，居然超時！到底有幾筆測試資料啊？ ```bash $ ./btest -f floatIsEqual Score Rating Errors Function ERROR: Test floatIsEqual failed. Timed out after 10 secs (probably infinite loop) Total points: 0/2 ``` 將`btest.c`的`TIMEOUT_LIMIT`設為 18 以上就可以通過了，代表我的 code 還需要增進 1/2 左右的效率，有空再回來想吧。 ### floatIsLess ```c= int floatIsLess(unsigned uf, unsigned ug) { unsigned uf_usb = uf & 0x7FFFFFFF, ug_sub = ug & 0x7FFFFFFF; unsigned uf_sign, ug_sign; unsigned uf_exp, ug_exp; unsigned uf_frac, ug_frac; if (uf_usb > 0x7F800000 || ug_sub > 0x7F800000) return 0; if (!(uf_usb | ug_sub)) return 0; uf_sign = !!(uf & 0x80000000); ug_sign = !!(ug & 0x80000000); if (uf_sign < ug_sign) return 0; else if (uf_sign > ug_sign) return 1; uf_exp = uf & 0x7F800000; ug_exp = ug & 0x7F800000; uf_frac = uf & 0x007FFFFF; ug_frac = ug & 0x007FFFFF; if (uf_sign == 0) { if (uf_exp < ug_exp) return 1; else if (uf_exp > ug_exp) return 0; return uf_frac < ug_frac; } else { if (uf_exp < ug_exp) return 0; else if (uf_exp > ug_exp) return 1; return uf_frac > ug_frac; } } ``` 又超時了我的天！我決定要把`TIME_LIMIT`改成 20，不要阻攔我！ ``` $ ./btest -f floatIsLess Score Rating Errors Function ERROR: Test floatIsLess failed. Timed out after 10 secs (probably infinite loop) Total points: 0/3 ``` ### floatNegate ```c= unsigned floatNegate(unsigned uf) { if ((uf & 0x7FFFFFFF) > 0x7F800000) return uf; return uf ^ 0x80000000; } ``` ### floatPower2 由於 2^x^ = 1 x 2^x^，`frac`的部分一定為`0`，`sign`的部分也是一定為`0`，因此只要更改`exp`的部分。 而`exp`的範圍是 0 ~ 255，0 代表是 denormalized，255 代表 infinity 或 NaN，扣掉 offset 127 之後範圍是 -127 ~ +128，因此依照題目要求，小於 -127 回傳 0，大於 128 回傳 +INF。 其餘部分則更改`exp`的部分，記得加上 offset 127。 ```c= unsigned floatPower2(int x) { if (x < -127) return 0; if (x > 128) return 0x7F800000; return (x + 127) << 23; } ``` ### floatScale1d2 當`uf`為 NaN 或 INF 時直接回傳`uf`；當`uf` * 0.5 的結果為 normalized 時，只要將`exp`的部分 -1 即可。 在`exp` = 0 or 1 的時候，-1 會造成結果成為 denormalized，這時就變成要改動`frac`的值，將`frac`的部分右移，這時又得考慮到捨入的問題，但由於只會損失一個 bit，以下列出四種狀況： |bit 1|bit0|| :-:|:-:|:-: |0|0|直接捨去 bit0| |0|1|round to even| |1|0|直接捨去 bit0| |1|1|round to even| 在`frac`最後兩個 bit 為`01`以及`10`的狀況時，需要向偶數捨入，`01`向偶數捨入的結果為`00`，等同於直接捨去 bit0，因此不用特別處理；但是`11`向偶數捨入的結果要 + 1，記得要加在 bit1 這一位。 ```c= unsigned floatScale1d2(unsigned uf) { unsigned sign = uf & 0x80000000; unsigned exp = uf & 0x7F800000; if (exp >= 0x7F800000) return uf; exp >>= 23; if (exp <= 1) { if ((uf & 3) == 3) uf += 2; return sign | ((uf >> 1) & 0x007FFFFF); } return (uf & 0x807FFFFF) | ((exp - 1) << 23); } ``` ### floatScale2 當`exp`部分為 255，即 INF 或 NAN 時，直接回傳`uf`。 當`exp`部分為 0，即 denormalized，將`frac`部分右移一個位元。 其餘狀況直接將`exp`+1，若結果恰好為 255，注意要回傳 INF 而非 NaN。 ```c= unsigned floatScale2(unsigned uf) { unsigned sign = uf & 0x80000000; unsigned exp = (uf & 0x7F800000) >> 23; if (exp == 255) return uf; if (exp == 0) return sign | (uf << 1); exp++; if (exp == 255) return sign | 0x7F800000; return (uf & 0x807FFFFF) | (exp << 23); } ``` ### floatScale64 想不出來，參考[《深入理解计算机系统/CSAPP》Data Lab - Pipapa](http://www.hh-yzm.com/index.php/archives/6/#%E8%B0%9C%E9%A2%9835-floatScale64) ```c= unsigned floatScale64(unsigned uf) { int exp = (uf & 0x7F800000) >> 23; int sign = uf & 0x80000000; int cnt = 22; if (exp == 0) { if (!(uf & 0x007E0000)) return (uf << 6) | sign; while (!(uf & (1 << cnt))) cnt--; uf <<= (23 - cnt); return sign | (uf & 0x807FFFFF) | ((cnt - 16) << 23); } if (exp == 255) return uf; exp += 6; if (exp >= 255) return 0x7F800000 | sign; return (uf & 0x807FFFFF) | (exp << 23); } ``` ### floatUnsigned2Float 直接拿`floatInt2Float`來改，把`sign`的部分移除就過了。 ```c= unsigned floatUnsigned2Float(unsigned u) { int exp = -1; int frac = 0; if (u == 0) return 0; frac = u; while (u) { u /= 2; exp++; } if (exp <= 23) frac <<= (23 - exp); else { frac += (1 << (exp - 24)); if (!(frac << (55 - exp))) frac &= (0xFFFFFFFF << (exp - 22)); if (!(frac & (1 << exp))) exp++; frac >>= (exp - 23); } frac &= 0x007fffff; exp = (exp + 127) << 23; return exp | frac; } ``` 在此 floating point 的處理告一個段落，雖然前面空了三題，不過目前分數已經到達 87 分應該還可以再高... ```bash Total points: 87/228 ``` 離滿分還有很大一段距離，看了一下居然還有 50 題要寫，要加把勁了:sob::sob::sob: --- ## 關卡三 燃起反擊的狼煙 二補數的進攻 **關卡限制** 似乎是又回到了第一關的限制 :scream: ### getByte ```c= int getByte(int x, int n) { return (x >> (n << 3)) & 0xFF; } ``` ### greatestBitPos 取出最高位的`1`。 這題想不出來，所以參考了 [stackoverflow](https://stackoverflow.com/questions/21413565/create-a-mask-that-marks-the-most-significant-set-bit-using-only-bitwise-operat) 上的方法： ```c= int greatestBitPos(int x) { x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; return x & ((~x >> 1) ^ 0x80000000); } ``` 上方程式碼 3 ~ 7 行將`x`最高位`1`右方的所有 bit 都設為`1`，接著將`x`取`not`後右移一個位元將最高位左方都設為`1`，再將兩個數進行`and`就可以取出最高位的`1`，以 8-bit 為例： ``` x = 0010 0101 x = 0011 1111 # line 3 to 7 ((~x >> 1) ^ 0x80000000) = 1110 0000 x & ((~x >> 1) ^ 0x80000000) = 0010 0000 ``` 不能使用大數，將`1`右移 31 個位元產生`0x80000000`。 ```c= int greatestBitPos(int x) { x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; return x & ((~x >> 1) ^ (1 << 31)); } ``` ### howManyBits 沒能想出來，參考 [Lab/datalab/bits.c - GitHub](https://github.com/jerrylzy/CS33/blob/master/Lab/datalab/bits.c#L145) ```c= int howManyBits(int x) { int sign, bit0, bit1, bit2, bit4, bit8, bit16; sign = x >> 31; x = (sign & ~x) | (~sign & x); bit16 = !!(x >> 16) << 4; x = x >> bit16; bit8 = !!(x >> 8) << 3; x = x >> bit8; bit4 = !!(x >> 4) << 2; x = x >> bit4; bit2 = !!(x >> 2) << 1; x = x >> bit2; bit1 = !!(x >> 1); x = x >> bit1; bit0 = x; return bit16 + bit8 + bit4 + bit2 + bit1 + bit0 + 1; } ``` ### implication 只有在`x`發生，`y`卻沒發生時是`false`，其他情況都為`true`。 ```c= int implication(int x, int y) { return (!x) | y; } ``` ### intLog2 結合`greatestBitPos`與`bitCount`的方法。 將最高位的`1`右邊全部的位元設為`1`，接著計算`1`的數量，最後將結果 -1。 輸入值不可能為負數，因為 2 的任何次方都不會產生負數。 ```c= int intLog2(int x) { int a0 = 0xFF | (0xFF << 8); int a1 = a0 ^ (a0 << 8); int a2 = a1 ^ (a1 << 4); int a3 = a2 ^ (a2 << 2); int a4 = a3 ^ (a3 << 1); x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x = (x & a4) + ((x >> 1) & a4); x = (x & a3) + ((x >> 2) & a3); x = (x & a2) + ((x >> 4) & a2); x = (x & a1) + ((x >> 8) & a1); x = (x & a0) + ((x >> 16) & a0); return x + ~0; } ``` ### isAsciiDigit 觀察`0x30`~`0x39`每個 bit 的組合。 可以發現`0x30`~`0x37`的 bit 組合都是`0011 0XXX`，因此只要符合這個 pattern 的值就一定在這個範圍之內，接著再額外對`0x38`及`0x39`單獨判斷即可。 ```c= int isAsciiDigit(int x) { return !((x >> 3) ^ 6) | !(x ^ 0x38) | !(x ^ 0x39); } ``` ### isEqual ```c= int isEqual(int x, int y) { return !(x ^ y); } ``` ### isGreater 以下三題都差不多。 ```c= int isGreater(int x, int y) { int sign_x = x >> 31; int sign_y = y >> 31; int equal = (!(sign_x ^ sign_y)) & ((~y + x) >> 31); int notEqual = sign_x & !sign_y; return !( equal | notEqual); } ``` ### isLess ```c= int isLess(int x, int y) { int sign_x = x >> 31; int sign_y = y >> 31; int equal = (!(sign_x ^ sign_y)) & ((~x + y) >> 31); int not_equal = (!sign_x) & sign_y; return !(equal | not_equal); } ``` ### isLessOrEqual ```c= int isLessOrEqual(int x, int y) { int sign_x = x >> 31; int sign_y = y >> 31; int equal = (!(sign_x ^ sign_y)) & !((~y + x) >> 31); int not_equal = (!sign_x) & sign_y; return !(equal | not_equal); } ``` ### isNegative ```c= int isNegative(int x) { return !!(x >> 31); } ``` ### isNonNegative ```c= int isNonNegative(int x) { return !(x >> 31); } ``` ### isNonZero ```c= int isNonZero(int x) { return !!x; } ``` ### isNotEqual ```c= int isNotEqual(int x, int y) { return !!(x ^ y); } ``` ### isPallindrome 話說題目好像拼錯了，應該是 palindrome 才對吧。 Palindrome (回文) 字串的重要特性就是，reverse 之後與原本字串相同。 所以直接拿之前寫過的`bitReverse`來用。 ```c= int isPallindrome(int x) { int x_ = x; int a0 = 0xFF | (0xFF << 8); int a1 = a0 ^ (a0 << 8); int a2 = a1 ^ (a1 << 4); int a3 = a2 ^ (a2 << 2); int a4 = a3 ^ (a3 << 1); x_ = (x_ << 16) | ((x_ >> 16) & a0); x_ = ((x_ & a1) << 8) | ((x_ >> 8) & a1); x_ = ((x_ & a2) << 4) | ((x_ >> 4) & a2); x_ = ((x_ & a3) << 2) | ((x_ >> 2) & a3); x_ = ((x_ & a4) << 1) | ((x_ >> 1) & a4); return !(x ^ x_); } ``` ### isPositive ```c= int isPositive(int x) { return !(x >> 31) & !!x; } ``` ### isPower2 思考這題的關鍵在於，如果`x`是 2 的次方，那麼首先`x`不能是負數或`0`，再來`x`的特性就是整個數列中只會出現一個`1`，其他都是`0`。 若`x`整個數列只有出現一次`1`，則`x`與`x - 1`一定不會有`1`出現在相同的位置；反之若`x`有兩個以上的`1`，則一定有位元不會受到影響，導致`x`與`x - 1`有兩個`1`出現在相同的位置。 並利用`!x`判斷`x`是否為`0`。 ```c= int isPower2(int x) { int minus_noe = (~0 ^ (x >> 31)); return !((x & (x + minus_noe)) | !x); } ``` ### isTmin 先看`isTmin`，判斷是否為 32-bit 二補數的最小值，也就是`-2147483648`。 這題我想到用一個二補數的特性來解，就是所有二補數能表示的值當中，只有對`0`跟`-2147483648`進行二補數的結果仍是自己本身，因此只要判斷`x`進行二補數的結果不變，並且`x`不為`0`即可。 ```c= int isTmin(int x) { return (!((~x + 1) ^ x)) & !!x; } ``` ### isTmax 利用另一個二補數的特性，`2147483647 + 1`的結果會變成`-2147483648`，因此將`x + 1`之後搭配上一題的方法就可以輕鬆解出這題。 ```c= int isTmax(int x) { x++; return (!((~x + 1) ^ x)) & !!x; } ``` ### isZero ```c= int isZero(int x) { return !x; } ``` ### leastBitPos 將`x`取二補數後，與`x`具有相同`1`的 bit 恰好只剩`x`最低位`1`的位置。 ``` x = 0010 0100 ~x = 1101 1011 ~x + 1 = 1101 1100 x & (~x + 1) = 0000 0100 ``` ```c= int leastBitPos(int x) { return x & (~x + 1); } ``` ### leftBitCount 稍微修改`countLeadingZero`。 ```c= int leftBitCount(int x) { int a0 = 0xFF | (0xFF << 8); int a1 = a0 ^ (a0 << 8); int a2 = a1 ^ (a1 << 4); int a3 = a2 ^ (a2 << 2); int a4 = a3 ^ (a3 << 1); x = ~x; x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x = ~x; x = (x & a4) + ((x >> 1) & a4); x = (x & a3) + ((x >> 2) & a3); x = (x & a2) + ((x >> 4) & a2); x = (x & a1) + ((x >> 8) & a1); x = (x & a0) + ((x >> 16) & a0); return x; } ``` ### logicalNeg 不能用`!`實作`!`，這題不就跟`bang`一樣嗎？:satisfied: ```c= int logicalNeg(int x) { x |= x >> 16; x |= x >> 8; x |= x >> 4; x |= x >> 2; x |= x >> 1; return (x ^ 1) & 1; } ``` ### logicalShift 造一個 mask 把 sign extension 消掉，由於不能左移`n - 1`個 bit (若 n = 0，位移 -1 個 bit 是未定義行為)，因此先左移`n`個 bit 再右移一個 bit。 ```c= int logicalShift(int x, int n) { return (x >> n) & (~(((1 << 31) >> n) << 1)); } ``` ### maximumOfTwo 燒腦... ```c= int maximumOfTwo(int x, int y) { int sign_x = x >> 31; int sign_y = y >> 31; int same = ~(!(sign_x ^ sign_y)) + 1; int larger = ~((x - y) >> 31); return (same & ((larger & x) | (~larger & y))) | (~same & ((sign_y & x) | (sign_x & y))); } ``` ### minimumOfTwo ```c= int minimumOfTwo(int x, int y) { int sign_x = x >> 31; int sign_y = y >> 31; int same = ~(!(sign_x ^ sign_y)) + 1; int larger = ~((x - y) >> 31); return (same & ((larger & y) | (~larger & x))) | (~same & ((sign_x & x) | (sign_y & y))); } ``` ### minusOne ```c= int minusOne(void) { return (1 << 31) >> 31; } ``` ### multFiveEighths 這題一開始完全想錯方向，以為是浮點數的 round to even，後來才想起來整數的捨入是無條件捨去法，真的是一陣尷尬 :sweat_smile: 當`5x`的結果為非負整數時，直接捨去右移被消除的 bit；而當`5x`的結果是負數時，加上`0111b`後再右移，注意不能右移後再`+1`。 ```c= int multFiveEighths(int x) { int add; x = (x << 2) + x; add = (x >> 31) & 7; return (x + add) >> 3; } ``` ### negate ```c= int negate(int x) { return ~x + 1; } ``` ### oddBits ```c= int oddBits(void) { int x = 0xAA; x |= x << 8; x |= x << 16; return x; } ``` ### remainderPower2 ```c= int remainderPower2(int x, int n) { int sign = x >> 31; int pos = x + (~((x >> n) << n) + 1); int neg; x = ~x + 1; neg = x + (~((x >> n) << n) + 1); neg = ~neg + 1; return (~sign & pos) | (sign & neg); } ``` ### replaceByte ```c= int replaceByte(int x, int n, int c) { int mask = 0xFF << (n << 3); return (mask & (c << (n << 3))) | (~mask & x); } ``` ### rotateLeft ```c= int rotateLeft(int x, int n) { int mask = ((1 << 31) >> (31 - n)); int r = (((((1 << 31) >> n) << 1) & x) >> (32 + (~n + 1))); return ((x << n) & mask) | (r & ~mask); } ``` ### rotateRight ```c= int rotateRight(int x, int n) { int mask = ((1 << 31) >> n) << 1; int r = (~((1 << 31) >> (31 + (~n + 1))) & x) << (32 + (~n + 1)); return ((x >> n) & ~mask) | (r & mask); } ``` ### satAdd ```c= int satAdd(int x, int y) { int sum = x + y; int sign = sum >> 31; int overflow = (((!(x >> 31) ^ (y >> 31)) & !!((sum >> 31) ^ (x >> 31))) << 31) >> 31; return (overflow & ((~sign & (1 << 31)) | (sign & ~(1 << 31)))) | (~overflow & sum); } ``` ### satMul2 ```c= int satMul2(int x) { int sign_x = x >> 31; int sign_2x = (x << 1) >> 31; int overflow = ~(!(sign_x ^ sign_2x)) + 1; return (overflow & (x << 1)) | (~overflow & ((~sign_x & ~(1 << 31)) | (sign_x & (1 << 31)))); } ``` ### satMul3 卡關...參考[CSAPP Data Lab - VcKir的博客](https://blog.csdn.net/VcKir/article/details/50407653) ```c= int satMul3(int x) { int x2 = x + x; int x3 = x + x2; int g = ((x ^ x2) | (x ^ x3)) >> 31; return ((~g) & x3) + (g & ((1 << 31) + ~(x >> 31))); } ``` ### sign ```c= int sign(int x) { return (x >> 31) | (!!x); } ``` ### signMag2TwosComp ```c= int signMag2TwosComp(int x) { int sign = x >> 31; int mag = x & ~(1 << 31); return (sign & (~mag + 1)) | (~sign & mag); } ``` ### specialBits ```c= int specialBits(void) { return ~(0xD7 << 14); } ``` ### subtractionOK |x|y|x-y|return| |:-:|:-:|:-:|:-:| |+|+|+|1| |+|+|-|1| |+|-|+|1| |+|-|-|0| |-|+|+|0| |-|+|-|1| |-|-|+|1| |-|-|-|1| ```c= int subtractionOK(int x, int y) { int x_y_not_same_sign = !!((x >> 31) ^ (y >> 31)); int y_sub_same_sign = !(((x - y) >> 31) ^ (y >> 31)); return !(x_y_not_same_sign & y_sub_same_sign); } ``` ### thirdBits ```c= int thirdBits(void) { int x = 0x49; x |= (x << 9); x |= (x << 18); return x; } ``` ### tmax ```c= int tmax(void) { return ~(1 << 31); } ``` ### tmin ```c= int tmin(void) { return 1 << 31; } ``` ### trueFiveEighths 參考 [stackoverflow](https://stackoverflow.com/questions/42288066/bitwise-multiply-by-5-8-watching-for-overflow) ```c= int trueFiveEighths(int x) { int const eights = x >> 3; int const rem = x & 7; return eights + (eights << 2) + ((rem + (rem << 2) + (x >> 31 & 7)) >> 3); } ``` ### trueThreeFourths ```c= int trueThreeFourths(int x) { int const four = x >> 2; int const rem = x & 3; return four + (four << 1) + ((rem + (rem << 1) + (x >> 31 & 3)) >> 2); } ``` ### twosComp2SignMag ```c= int twosComp2SignMag(int x) { int sign = x >> 31; int mag = (sign & (~x + 1)) | (~sign & x); return (sign & (1 << 31)) | mag; } ``` ### upperBits 不小心用了 11 個運算子，不知道能不能再改進。 ```c= int upperBits(int n) { int except = ~(!n) + 1; return (except & 0) | (~except & ((1 << 31) >> (n + ~0))); } ``` `except & 0`一定是`0`，可以省略，減少到 9 個運算子！ ```c= int upperBits(int n) { int except = ~(!n) + 1; return ~except & ((1 << 31) >> (n + ~0)); } ``` --- ## 分數結算 ```bash $ ./btest -g Score Rating Errors Function 4 4 0 absVal 3 3 0 addOK 2 2 0 allEvenBits 2 2 0 allOddBits 2 2 0 anyEvenBit 2 2 0 anyOddBit 4 4 0 bang 1 1 0 bitAnd 4 4 0 bitCount 3 3 0 bitMask 1 1 0 bitMatch 1 1 0 bitNor 1 1 0 bitOr 4 4 0 bitParity 4 4 0 bitReverse 1 1 0 bitXor 2 2 0 byteSwap 3 3 0 conditional 4 4 0 countLeadingZero 2 2 0 copyLSB 2 2 0 distinctNegation 2 2 0 dividePower2 1 1 0 evenBits 3 3 0 ezThreeFourths 2 2 0 fitsBits 1 1 0 fitsShort 2 2 0 floatAbsVal 4 4 0 floatFloat2Int 4 4 0 floatInt2Float 2 2 0 floatIsEqual 3 3 0 floatIsLess 2 2 0 floatNegate 4 4 0 floatPower2 4 4 0 floatScale1d2 4 4 0 floatScale2 4 4 0 floatScale64 4 4 0 floatUnsigned2Float 2 2 0 getByte 4 4 0 greatestBitPos 4 4 0 howManyBits 2 2 0 implication 4 4 0 intLog2 3 3 0 isAsciiDigit 2 2 0 isEqual 3 3 0 isGreater 3 3 0 isLess 3 3 0 isLessOrEqual 2 2 0 isNegative 2 2 0 isNonNegative 4 4 0 isNonZero 2 2 0 isNotEqual 4 4 0 isPallindrome 2 2 0 isPositive 4 4 0 isPower2 1 1 0 isTmax 1 1 0 isTmin 1 1 0 isZero 2 2 0 leastBitPos 4 4 0 leftBitCount 4 4 0 logicalNeg 3 3 0 logicalShift 4 4 0 maximumOfTwo 4 4 0 minimumOfTwo 1 1 0 minusOne 3 3 0 multFiveEighths 2 2 0 negate 2 2 0 oddBits 3 3 0 remainderPower2 3 3 0 replaceByte 3 3 0 rotateLeft 3 3 0 rotateRight 4 4 0 satAdd 3 3 0 satMul2 3 3 0 satMul3 2 2 0 sign 4 4 0 signMag2TwosComp 1 1 0 specialBits 3 3 0 subtractionOK 1 1 0 thirdBits 1 1 0 tmax 1 1 0 tmin 4 4 0 trueFiveEighths 4 4 0 trueThreeFourths 4 4 0 twosComp2SignMag 1 1 0 upperBits Total points: 228/228 ``` --- ## 應用案例探討 待補充 :grimacing: --- ## 心得 這次的作業真的是非常燒腦，不僅要熟悉 signed/unsigned integer 的特性，還可以訓練位元操作以及邏輯思考，寫完每一題會發現自己對位元的操作更加熟練了，雖然有些題目很可惜沒辦法自己想出來，因為自己思考過後得出答案所獲得的成就感，是遠比參考別人的想法後才實作出來高很多的。 不過確實透過這次的作業，我重新釐清了許多之前沒有搞懂的東西，包括回顧了有號/無號整數、浮點數的轉換與捨入，位元操作的技巧，也更加熟悉二補數的應用。 若有更好的方法，以上程式碼也會持續改進，還請各位看倌多多指教。 --- ## 開發環境 ```bash $ cat /etc/lsb-release DISTRIB_ID=Ubuntu DISTRIB_RELEASE=16.04 DISTRIB_CODENAME=xenial DISTRIB_DESCRIPTION="Ubuntu 16.04.5 LTS" ``` ```bash $ uname -a Linux qoo-S551LN 4.15.0-34-generic #37~16.04.1-Ubuntu SMP Tue Aug 28 10:44:06 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux ``` ```bash $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 69 Model name: Intel(R) Core(TM) i7-4500U CPU @ 1.80GHz Stepping: 1 CPU MHz: 1297.879 CPU max MHz: 3000.0000 CPU min MHz: 800.0000 BogoMIPS: 4788.95 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 4096K NUMA node0 CPU(s): 0-3 Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts flush_l1d ```
Last changed by  
 
QOO
958
Published on HackMD