# 2018q3 Homework5 (bits) contributed by < [`jason53415`](https://github.com/jason53415) > ## 測試環境 ```shell $ uname -a Linux scream-47860 4.15.0-38-generic #41-Ubuntu SMP Wed Oct 10 10:59:38 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux ``` ## 函式原理 ### allEvenBits 目標：回傳是否所有偶數位皆為 1 ```C= int allEvenBits(int x) { x = x & (x >> 16); x = x & (x >> 8); x = x & (x >> 4); x = x & (x >> 2); return x & 1; } ``` 類似於將整個 32 bits 不斷對折的概念，其結果等同於將所有的偶數位取出並兩兩做 AND 運算直到留下最後一個位元，因此只要其中一個偶數位是 0，則終將導致對後留在最低位的數字為 0。 ### bitMatch 目標：只利用 `~` 與 `&` 實做，使函式回傳 `x` 與 `y` 中哪些位元是相同的 ```C= int bitMatch(int x, int y) { return ~(~(x & y) & ~(~x & ~y)); } ``` 直觀的想法是做 XOR 運算後再取 NOT，就可以得到所有 `x` 與 `y` 中相同的位元，亦即 `~(x ^ y)`，不過因為題目限制的關係，所以要先把中間的 XOR 部份轉換成等價的 `~(x & y) & (x | y)`，最後因為 OR 同樣不能使用，所以再把 `(x | y)` 利用 De Morgan's laws 轉換成 `~(~x & ~y)` 就是最後的結果了。 ### bitReverse 目標：將 `x` 中的所有位元按順序顛倒過來 ```C= int bitReverse(int x) { int mask1 = 0xff | (0xff << 8); // 0x0000ffff int mask2 = 0xff | (0xff << 16); // 0x00ff00ff int mask3 = 0x0f | (0x0f << 8); mask3 = mask3 | (mask3 << 16); // 0x0f0f0f0f int mask4 = 0x33 | (0x33 << 8); mask4 = mask4 | (mask4 << 16); // 0x33333333 int mask5 = 0x55 | (0x55 << 8); mask5 = mask5 | (mask5 << 16); // 0x55555555 x = ((x >> 16) & mask1) | ((x & mask1) << 16); x = ((x >> 8) & mask2) | ((x & mask2) << 8); x = ((x >> 4) & mask3) | ((x & mask3) << 4); x = ((x >> 2) & mask4) | ((x & mask4) << 2); x = ((x >> 1) & mask5) | ((x & mask5) << 1); return x; } ``` 首先我們生成 5 個 mask，分別各是由低位到高位以 16、8、4、2、1 個連續的 1 與同樣數量連續的 0 交錯出現，亦即 `0x0000ffff`、`0x00ff00ff`、`0x0f0f0f0f`、`0x33333333`、`0x55555555`，每一個 mask 可以用來交換相鄰的連續 16、8、4、2、1 個位元的內容，因此只要而將所有位元利用這 5 個 mask 交換完後，就可以得到完全顛倒的結果了。 ### fitsBits 目標：如果 `x` 可以用 `n` 個位元的 2 補數表示的話回傳 1 ```C= int fitsBits(int x, int n) { int shift = 33 + ~n; return !((x << shift >> shift) ^ x); } ``` 如果一個數字可以用 `n` 個位元來表示的話，代表高位的 `32 - n` 個位元都跟 sing bit 相同，因此只要將數字左移 `32 - n` 再右移 `32 - n` 個位元後仍和原數字一樣，就代表這個數字是可以用 `n` 個位元來表示的。實做時因為題目限制不能使用減號，因此改使用 `32 + (1 + ~n)`，也就是 `33 + ~n` 來代替，並且以 shift 過後的值與原數字做 XOR 後是否等於 0 來判斷是否相等。 ### floatIsEqual 目標：判斷兩個浮點數是否相等 ```C= int floatIsEqual(unsigned uf, unsigned ug) { int same = !(uf ^ ug); int notnan = !!((~(uf >> 23) & 0xff) | !(uf << 9)); int iszero = !((uf | ug) ^ (0x1u << 31)); return (same & notnan) | ((!same) & iszero); } ``` 要判斷兩個浮點數是否相等可以從兩個條件下手： 1. 除了 NaN 之外，若兩個浮點數每一個位元都相同，則兩個浮點數必相等。 2. 除了 +0 與 -0 之外，若兩個浮點數有任何一個位元不相同，則兩個浮點數必不相等。 因此以上的實做使用了三個變數，分別是 `same` 代表了兩個浮點數是否每一個位元都相同，`notnan` 代表了其中一個數不是 NaN，`iszero` 代表兩個數不是 +0 就是 -0，接著就可以用上面列出的條件來判斷是否相等。 ### greatestBitPos 目標：回傳最高位的 1 的所在位數 ```C= int greatestBitPos(int x) { int shift = !!(x >> 16) << 4; int bit = shift; x = x >> shift; shift = !!(x >> 8) << 3; bit = bit + shift; x = x >> shift; shift = !!(x >> 4) << 2; bit = bit + shift; x = x >> shift; shift = !!(x >> 2) << 1; bit = bit + shift; x = x >> shift; shift = !!(x >> 1); bit = bit + shift; x = x >> shift; return x << bit; } ``` 使用類似於 binary search 遞迴搜尋的概念，首先對於一個 $2n$ 個位元的數字，確認了高位的 $n$ 個位元中是否有 1 後，就可以專注於高位的 $n$ 個位元或低位的 $n$ 個位元，利用相同的方法繼續尋找最高位的 1。實做時則利用了連續兩次的 `!` (logical NOT) 運算，來取得一個非 1 即 0 的數字，代表是否有任何 1 的存在，再將這個得到的 1 或 0 左移 $\log_2n$ 位後就可以得到 $n$ 或 0，代表最高位至少在多少位以上，記下這個目前得知的最高位數，並將原始數字右移剛剛得到 $n$ 或 0 位元後，我們就可以用同樣的方法繼續搜尋低位的 $n$ 位元，而陸續加總每一輪的結果就可以得到所要求的最高位數。 ### isAsciiDigit 目標：判斷 `x` 是否是 ASCII 中的數字 ```C= int isAsciiDigit(int x) { int condition1 = !((x >> 4) ^ 0x3); int condition2 = !((x & 0x8) ^ 0x0); int condition3 = !((x & 0x6) ^ 0x0); return condition1 & (condition2 | condition3); } ``` `x` 若要是 ASCII 中的數字，則必須符合 `0x30 <= x <= 0x39`，實做中則將前述的條件拆成三個可以快速用 bit operation 判斷的條件 ： 1. `x` 是否是一個第五位及第六位皆是 1，其餘所有更高位元皆為 0 的數字，即二進制表示符合 0011XXXX$_2$ (X 代表可 0 可 1) 2. `x` 是否是一個第四位是 0 的數字，即二進制表示符合 XXXX0XXX$_2$ 3. `x` 是否是一個第二位及第三位皆是 0 的數字 (XXXXX00X$_2$) 最後我們只要判斷是否第一個條件成立，並且第二及第三個條件有其中一個符合即可。 ## 分數 ```shell $ make check gcc -O0 -g -Wall -Werror -m32 -lm -o btest bits.c btest.c decl.c tests.c ./btest 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 ```