2018q3 Homework5 (bits) === contributed by<[LiuJuiHung](https://github.com/LiuJuiHung/datalab)> ## 實驗環境 ``` $ 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: 1 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 58 Model name: Intel(R) Core(TM) i5-3470 CPU @ 3.20GHz Stepping: 9 CPU MHz: 1617.917 CPU max MHz: 3600.0000 CPU min MHz: 1600.0000 BogoMIPS: 6400.24 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 6144K NUMA node0 CPU(s): 0-3 ``` ## 無法 make make 時發現以下錯誤 ``` $ make Git commit hooks are installed successfully. gcc -O0 -g -Wall -Werror -m32 -lm -o btest bits.c btest.c decl.c tests.c In file included from /usr/include/stdio.h:27:0, from btest.c:17: /usr/include/features.h:367:25: fatal error: sys/cdefs.h: No such file or directory compilation terminated. In file included from /usr/include/stdio.h:27:0, from decl.c:1: /usr/include/features.h:367:25: fatal error: sys/cdefs.h: No such file or directory compilation terminated. In file included from /usr/include/limits.h:25:0, from /usr/lib/gcc/x86_64-linux-gnu/5/include-fixed/limits.h:168, from /usr/lib/gcc/x86_64-linux-gnu/5/include-fixed/syslimits.h:7, from /usr/lib/gcc/x86_64-linux-gnu/5/include-fixed/limits.h:34, from tests.c:3: /usr/include/features.h:367:25: fatal error: sys/cdefs.h: No such file or directory compilation terminated. Makefile:13: recipe for target 'btest' failed make: *** [btest] Error 1 ``` [解決方法](https://stackoverflow.com/questions/4643197/missing-include-bits-cconfig-h-when-cross-compiling-64-bit-program-on-32-bit)，下`$ sudo apt install gcc-multilib`指令安裝`gcc-multilib`即可 ## 修改 bit.c ### absVal :::info 規定： * absVal - absolute value of x * Example: absVal(-1) = 1. * You may assume -TMax <= x <= TMax * Legal ops: ! ~ & ^ | + << >> * Max ops: 10 * Rating: 4 ::: 簡單推導如下，以 4-bits 進行推導： ``` 1 0 0 1 x (因 x 為有號數，所以此二進制的 "1001" 代表十進制的 "-7") 1 1 1 1 y = x >> 3 ------------------ 0 1 1 0 （y ^ x） 0 0 0 1 （~y + 1） ------------------ 0 1 1 1 （y ^ x）+ (~y + 1) result "7" ``` ```Clike=1 int absVal(int x) { int y = x >> 31; return (y ^ x) + (~y + 1); } ``` ### addOK :::info 規定： * 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 ::: * 正加正，負加負兩者皆可能有溢位產生 * 正加負不會造成溢位 ```Clike=1 int addOK(int x, int y) { int z = x + y; return !(((x ^ z) & (y ^ z)) >> 31); } ``` ### allEventBits :::info 規定： * 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 ::: 利用 `&` 來確認是否每個偶數位元都等於 `1` ```Clike=1 int allEvenBits(int x) { x &= x >> 16; x &= x >> 8; x &= x >> 4; x &= x >> 2; return x & 0x1; } ``` ### allOddBits :::info 規定： * 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 ::: 利用 `&` 來確認是否每個奇數位元都等於 `1`，並在最後`>> 1‵ ```Clike=1 int allOddBits(int x) { x &= x >> 16; x &= x >> 8; x &= x >> 4; x &= x >> 2; x = x >> 1; return x & 0x1; } ``` ### anyEvenBit :::info 規定： * 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 ::: 只要任意偶數位元有 `1`， 則輸出 `1`;若偶數位元皆為 `0`，則輸出 `0` ```Clike=1 int anyEvenBit(int x) { x |= x >> 16; x |= x >> 8; x |= x >> 4; x |= x >> 2; return x & 0x1; } ``` ### anyOddBit ::: info 規定： * 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 ::: 只要任意奇數位元有 `1`， 則輸出 `1`;若奇數位元皆為 `0`，則輸出 `0` ```Clike=1 int anyOddBit(int x) { x |= x >> 16; x |= x >> 8; x |= x >> 4; x |= x >> 2; x = x >> 1; return x & 0x1; } ``` ### bang :::info 規定： * bang - Compute !x without using ! * Examples: bang(3) = 0, bang(0) = 1 * Legal ops: ~ & ^ | + << >> * Max ops: 12 * Rating: 4 ::: 讓非 `0` 的數變成 `0`，讓 `0` 變成 `1` ```Clike=1 int bang(int x) { return (1 & (1 ^ ((x | (~x + 1)) >> 31))); } ``` ### bitAnd :::info 規定： * bitAnd - x&y using only ~ and | * Example: bitAnd(6, 5) = 4 * Legal ops: ~ | * Max ops: 8 * Rating: 1 ::: 利用 `De Morgan's laws` 做推導 $XY = \overline{\overline{\rm XY}} = \overline{ \overline{\rm X} \ + \ \overline{\rm Y}}$ ```Clike=1 int bitAnd(int x, int y) { return ~((~x) | (~y)); } ``` ### bitCount :::info 規定： * bitCount - returns count of number of 1's in word * Examples: bitCount(5) = 2, bitCount(7) = 3 * Legal ops: ! ~ & ^ | + << >> * Max ops: 40 * Rating: 4 ::: :::danger 先跳過 ::: ### bitMask :::info 規定： * bitMask - Generate a mask consisting of all 1's * lowbit and highbit * Examples: bitMask(5, 3) = 0x38 * Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31 * If lowbit > highbit, then mask should be all 0's * Legal ops: ! ~ & ^ | + << >> * Max ops: 16 * Rating: 3 ::: :::danger 先跳過 ::: ### bitMatch :::info 規定： * 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 ::: :::danger 先跳過 ::: ### bitNor :::info 規定： * bitNor - ~(x|y) using only ~ and & * Example: bitNor(0x6, 0x5) = 0xFFFFFFF8 * Legal ops: ~ & * Max ops: 8 * Rating: 1 ::: 利用 `De Morgan's laws` 做推導 $\overline{\rm X+Y} \ = \ \overline{\rm X} \bullet \overline{\rm Y}$ ```Clike=1 int bitNor(int x, int y) { return (~x) & (~y); } ``` ### bitOr :::info 規定： * bitOr - x|y using only ~ and & * Example: bitOr(6, 5) = 7 * Legal ops: ~ & * Max ops: 8 * Rating: 1 ::: 利用 `De Morgan's laws` 做推導 $X+Y = \overline{\overline{\rm X+Y}} = \overline{\overline{\rm X} + \overline{\rm Y}}$ ```Clike=1 int bitOr(int x, int y) { return ~((~x) & (~y)); } ``` ### bitParity :::info 規定： * 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 ::: 透過 `shift right` 與 `XOR` 計算 1 有偶數還是奇數個，以下為 8-bit 為例推導 ``` 10101010 x 00001010 x >> 4 ------------------ 10100000 y = x ^ (x>>4) 00101000 z = y >> 2 ------------------ 10001000 a = y ^ z 01000100 b = a >> 1 ------------------ 11001100 LSB = 0，為偶數個1 ============================== 10101000 x 00001010 x >> 4 ------------------ 10100010 y = x ^ (x>>4) 00101000 z = y >> 2 ------------------ 10001010 a = y ^ z 01000101 b = a >> 1 ------------------ 11001111 LSB = 1，為奇數個1 ``` ```Clike=1 int bitParity(int x) { x ^= x >> 16; x ^= x >> 8; x ^= x >> 4; x ^= x >> 2; x ^= x >> 1; return x & 1; } ``` ### bitReverse :::info 規定： * bitReverse - Reverse bits in a 32-bit word * Examples: * bitReverse(0x80000002) = 0x40000001 * bitReverse(0x89ABCDEF) = 0xF7D3D591 * Legal ops: ! ~ & ^ | + << >> * Max ops: 45 * Rating: 4 ::: :::danger 先跳過 ::: ### bitXOR :::info 規定： * bitXor - x^y using only ~ and & * Example: bitXor(4, 5) = 1 * Legal ops: ~ & * Max ops: 14 * Rating: 1 ::: 利用 `De Morgan's laws`，`真值表`，`XOR等價公式` 做推導 $X \oplus Y = (\overline{\rm X} \bullet Y) + (X \bullet \overline{\rm Y})$ ```Clike=1 int bitXor(int x, int y) { return ((~x) & y) + (x & (~y)); } ``` ### byteSwap :::info 規定： * 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 :::