# 2018q3 Homework5 (bits) contributed by <`krimson8`> ## 開發環境 ``` gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0 Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 6 On-line CPU(s) list: 0-5 Thread(s) per core: 1 Core(s) per socket: 6 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 158 Model name: Intel(R) Core(TM) i5-8400 CPU @ 2.80GHz Stepping: 10 CPU MHz: 800.012 CPU max MHz: 4000.0000 CPU min MHz: 800.0000 BogoMIPS: 5616.00 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 9216K NUMA node0 CPU(s): 0-5 ``` ## 安裝 32-bits 開發套件 與 遇到的問題 ### 安裝 binutils g++-multilib `sudo apt install libc6-dev:i386 gcc:i386 cpp-7:i386 g++-multilib` 其中 `cpp-7:i386` 是 `gcc:i386` 的 dependencies ### 遇到的問題 自 Ubuntu 17.10 開始便放棄自家的unity 桌面系統，改用 gnome 桌面系統，而 ubuntu 使用的gnome 是有特別訂製某些 interface 的，而安裝了上述的32 bits 開發套件過後會導致這些interface 不能用，進而導致桌面系統崩潰（連帶nvidia 的 driver 也一併崩潰） ### 解決方法 把上面安裝的套件逐一 purge 掉，然後 autoremove 再來 `sudo apt-get install --reinstall ubuntu-gnome-desktop` nvidia 驅動部分也是 purge 掉重裝就好 ## datalab 因爲實在衆多，只附上花了比較多時間思考的題目 ### addOK ```clike= int addOK(int x, int y) { unsigned temp_x = x; unsigned temp_y = y; int x_sign = (temp_x >> 31); int y_sign = (temp_y >> 31); int x_y_sign = ((temp_x + temp_y) >> 31); return (((x_sign ^ y_sign) & 1) | (~((x_sign & y_sign) ^ x_y_sign) & 1)); } ``` 套用一下真值表可推 |x|y|z|r| |-|-|-|-| |0|0|0|1| |0|0|1|0| |0|1|0|1| |0|1|1|1| |1|0|0|1| |1|0|1|1| |1|1|0|0| |1|1|1|1| `(x ^ y) | ~((x & y) ^ z )` 意義在於，x 和 y sign 不一樣的話一定成功，一樣的話則判斷加法過後 的 sign 有無變化，若不變則正確 ### allEvenBits ```clike= int allEvenBits(int x) { // first solution /* int p1 = (x >> 24) & 0xFF; int p2 = (x >> 16) & 0xFF; int p3 = (x >> 8) & 0xFF; int p4 = x & 0xFF; x = p1 & p2 & p3 & p4; return !((x & 0x55) ^ 0x55); */ // second solution x &= x >> 16; x &= x >> 8; x &= x >> 4; x &= x >> 2; return x & 1; } ``` 有想到兩種解法，第二種用的OP 較少 ### bang ```clike= int bang(int x) { x |= x >> 16; x |= x >> 8; x |= x >> 4; x |= x >> 2; x |= x >> 1; return ~x & 1; } ``` 任一點爲一，則最後一bit 爲一，取最後一 bit 的not ### bitAnd ```clike= int bitAnd(int x, int y) { // DeMorgan's Theorem (A x B)' = A' + B' return ~(~x | ~y); } ``` ### bitMask ```clike= int bitMask(int highbit, int lowbit) { int x = ~0; // 0xFFFFFFFF int high = (x << highbit) << 1; int low = x << lowbit; return (high ^ low) & low; } ``` 左移highbit 和 lowbit 個 數量後，兩者差異的地方便是答案 ### bitMatch ```clike= int bitMatch(int x, int y) { // use solution in bitOr because "|" not available // ~((~x) & (~y)) -- bitOr return ~((~(x & y)) & (~(~x & ~y))); } ``` 做 XNOR ### bitParity 如課堂測驗所教 ### bitXor ```clike= int bitXor(int x, int y) { return ~((~(x & ~(x & y))) & (~(y & ~(x & y)))); } ``` 凡是 or 和 and 的組合都可以參考下列網址 [nand logic](https://en.wikipedia.org/wiki/NAND_logic) ### byteSwap ```clike= int byteSwap(int x, int n, int m) { n <<= 3; m <<= 3; int pn = (x >> n) & 0xFF; int pm = (x >> m) & 0xFF; x = x ^ (pn << n) ^ (pm << m); return x | (pn << m) | (pm << n); } ``` 先提取出來，將那個地方清空（和自己 xor），在進行填空 ### conditional ```clike= int conditional(int x, int y, int z) { x |= x << 16; x |= x << 8; x |= x << 4; x |= x << 2; x |= x << 1; x = x >> 30 >> 1; // sign extension return (x & y) | (~x & z); } ``` 把 or 的結果集中在 sign bit，往右移extend 成 全0 或 全1 ### distinctNegation ```clike= int distinctNegation(int x) { // when x is 0 and 0x80000000(largest negative) x = x << 1; return !!(x); } ``` ### evenBits ```clike= int evenBits(void) { int x = 0x55; return x | (0x55 << 8) | (0x55 << 16) | (0x55 << 24); } ``` 不能使用超過 0cFF 的常數~~（好多同學都在用呢QQ）~~ ### ezThreeFourths ```clike= int ezThreeFourths(int x) { x += (x << 1); return (x + ((x >> 30 >> 1) & 3)) >> 2; } ``` 先×3，如果結果是負數則 +3，在除2 ### fitBits ```clike= int fitsBits(int x, int n) { return !(((x >> (n + ~0)) + 1) >> 1); } ``` 參考同學的解答，先往右移 n-1 bit，考慮極端情況便是4 bit 的負數 往右移 3 bit，那還剩下 sign bit “1”，則加 1 再 往右移會導致結果不爲 0 ### floatAbsVal ```clike= unsigned floatAbsVal(unsigned uf) { unsigned exp = (uf >> 23) & 0xFF; unsigned fraction = uf & 0x7FFFFF; if (exp == 0xFF && fraction != 0) { return uf; } return uf & 0x7FFFFFFF; } ``` 提取 exp 和 fraction ，根據NaN 的定義 return uf，否則移除sign bit 即可 ### loatFloat2Int ```clike= int floatFloat2Int(unsigned uf) { // value of float // (-1) ^ S * 2 ^ (E - 127) * 1.fraction unsigned sign = (uf >> 31) & 1; int exp = ((uf >> 23) & 0xFF) - 127; unsigned fraction = uf & 0x7FFFFF; fraction |= 0x800000; // 補上 1，成爲1.XXX if(exp < 0) { return 0; } else if(exp > 31) { return 0x80000000u; } // 23 bit of fraction 1.XX....... // if exp < 23 because is already a unsigned, then must right shift // right shift 23 - exp // only if exp > 23 then left shift exp - 23(may be 0) // if exp < 0 then 23 + abs(exp) if(exp < 23) { fraction >>= 23 - exp; } else if(exp > 23) { fraction <<= exp - 23; } if(sign) { fraction = ~fraction + 1; } return fraction; } ``` 參考程式碼內的註解 ### floatIsEqual ```clike= int floatIsEqual(unsigned uf, unsigned ug) { unsigned esf = uf & 0x7FFFFFFF; // exp + fraction unsigned esg = ug & 0x7FFFFFFF; // printf("f : %x -- g : %x\n", esf, esg); if(!esf && !esg) { return 1; } if(esf > 0x7F800000 || esg > 0x7F800000) { return 0; } return uf == ug; } ``` 我在效能慢一點的筆電測試需要調整 btest 內的timeout value 至 20 才能成功，快一點的電腦也需要18 左右，看了很多同學的共筆貌似都有這個問題，但是實在想不到更快的方式了 ### floatIsLess ```clike= int floatIsLess(unsigned uf, unsigned ug) { int uf_sign = (uf >> 31) & 1; int ug_sign = (ug >> 31) & 1; int uf_exp = (uf >> 23) & 0xFF; int ug_exp = (ug >> 23) & 0xFF; int uf_frac = uf & 0x7FFFFF; int ug_frac = ug & 0x7FFFFF; unsigned esf = uf & 0x7FFFFFFF; // exp + fraction unsigned esg = ug & 0x7FFFFFFF; // printf("f : %x -- g : %x\n", uf_exp, ug_exp); if(!esf && !esg) { return 0; } if(esf > 0x7F800000 || esg > 0x7F800000) { return 0; } if(uf_sign == ug_sign) { if(uf_exp == ug_exp) { if(uf_frac == ug_frac) { return 0; } return (uf_frac < ug_frac) ^ uf_sign; } else { return (uf_exp < ug_exp) ^ uf_sign; } } else { return uf_sign > ug_sign; // negative is 1 so > 0 } return 0; } ``` 依次比較 sign，exp，fraction 即可，注意 sign 因爲 1 是負，所以判斷條件和另外兩個不一樣 ### floatNegate ```clike= unsigned floatNegate(unsigned uf) { unsigned esf = uf & 0x7FFFFFFF; if(esf > 0x7F800000) return uf; return uf ^ 0x80000000; } ``` 判斷 NaN 即可，然後吧sign bit 做negate ### floatPower2 ```clike= unsigned floatPower2(int x) { // bias = 127, 255 > 127 + x >= 0 if(x < -127) return 0; if(x > 127) return 0x7F800000; x += 127; return x <<= 23; } ``` 這題想題目想了很久。。。fraction 是不會變的，只要調整exp 即可，因此 x + bias 然後放入 exp 的位子即可 ### floatScale1d2 ```clike= unsigned floatScale1d2(unsigned uf) { unsigned esf = uf & 0x7FFFFFFF; if(esf >= 0x7F800000) return uf; int sign = uf & 0x80000000; int exp = (uf >> 23) & 0xFF; // printf("-- %x --%x\n", exp, uf); if(exp > 1) { // bias=127, so exp<=0 right shift fraction exp -= 1; exp <<= 23; return (uf &= 0x807FFFFF) | exp; } if((uf & 0x3) == 0x3) { uf = uf + 0x2; } return ((uf >> 1) & 0x7fffff) | sign; } ``` 參考程式碼註解，exp > 1 則調整exp，小於 1 則注意舍入問題 ### greatestBitsPos ```clike= int greatestBitPos(int x) { x |= x >> 16; x |= x >> 8; x |= x >> 4; x |= x >> 2; x |= x >> 1; // change the left side of most_significant bit to 1 // then right shift 1, and take the & result // if x>= 0, sign bit = 0, no influence // if x is neg, sign = 1, after ~x it becomes all 0 // thus ^ 0x80000000 to give the sign bit value 1 return x & ((~x >> 1) ^ 0x80000000); } ``` 參考程式碼註解 ### implication ```clike= int implication(int x, int y) { return (!x) | (x & y); } ``` 0 —> 0/1 都是對的，若 x 成立 則 y 必須成立，因此用and :::info 持續更新中 :::