# 2018q3 Homework5 (bits)
contributed by <`AlecJY`>
## 實驗環境
* 作業系統：openSUSE Leap 15.0
* gcc：7.3.1
* Cppcheck：1.8
* clang-format：5.0.1
## `absVal()`
這題在之前的考試有出現過類似的題目，所以一開始很快地寫出這樣的程式碼
``` C
int absVal(int x)
{
int s = x >> 31;
return (x ^ s) + (~s + 1);
}
```
編譯測試結果沒問題，結果在要commit的時候被cppcheck擋了下來
```
[bits.c:114]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour
```
問題在於對 32-bit signed integer 位移了 32 bits ，所以換個方式思考，將 `x` 轉型成 unsigned integer 再做運算就不會有問題了，所以後來就將程式碼改成底下這樣。
``` C
int absVal(int x)
{
unsigned int *xptr = (unsigned int *) &x;
int sbit = *xptr >> 31;
return (x ^ (~(sbit) + 1)) + sbit;
}
```
和原本最大的差別是原本負數位移 31 bits 會得到 -1 ，現在轉型成無號數之後位移會得到 1 ，所以將原本計算會用到 1 和 -1 的部分互換。
只是這樣會違反題目規定的
> You are expressly forbidden to:
> 6. Use any form of casting.
> 7. Use any data type other than int. This implies that you cannot use arrays, structs, or unions.
參考了一下其他人的作法都是把位移分成兩次執行，所以最後把程式碼改成
``` C
int absVal(int x)
{
int s = x >> 30 >> 1;
return (x ^ s) + (~s + 1);
}
```
總算有通過 cppcheck 的檢查
:::info
翻閱 C99 標準在 6.5.7 第 5 點有底下描述
> The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.
對負數進行位移是根據編譯器的實作所決定的
所以之後去翻閱 GCC 7.3.0 的文件，看到有個選項
```
-Wshift-negative-value
Warn if left shifting a negative value. This warning is enabled by ‘-Wextra’ in
C99 and C++11 modes (and newer).
```
也有解釋為什麼這個 warning 預設是關閉的
```
Shift count operands are probably signed more often than unsigned. Warning about
this would cause far more annoyance than good.
```
還有敘述 GCC 是如何處理有號負數向右位移的
```
Bitwise operators act on the representation of the value including both the sign and
value bits, where the sign bit is considered immediately above the highest-value value
bit. Signed ‘>>’ acts on negative numbers by sign extension
```
:::
## `addOK()`
這題的我的思考方式是這樣
* 兩個正數相加溢出會變成負數
* 兩個負數相加溢出會變成正數或是 0
* 正數和負數相加不會溢位
所以先把 `x` 、 `y` 和他們的和的正負號取出，接下來用 XOR 判斷，如果同時滿足 `x` 、 `y` 正負號相同以及 `x` 、 兩數之和正負號不同就是溢位
## `allEvenBits()` 和 `allOddBits()`
這裡利用位移來把所有的奇數位和偶數位做 AND 運算來算出奇數位或偶數位是否都為 1 ，最後計算完的第 0 bit 就是偶數位的結果，第 1 bit 就是奇數位的結果。
## `anyEvenBit()` 和 `anyOddBit()`
這兩部分跟前面很像，差別只在於只要其中一個 bit 為 1 就好，所以把原本的 AND 運算改成 OR
## `bang()`
這題是在不用 `!` 做到 logical not ，概念上就是有任何 bit 為 1 的話就要回傳 0 ，如果皆為 0 就回傳 1 ，所以用了跟上一題類似的概念，利用位移讓所有位數做 OR ，得到的結果加個 NOT 取最低位數就是需要的結果了
## `bitAnd()`
觀察一下 AND 的真值表
| P | Q | P & Q |
| - | - | ----- |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
以及 OR 的真值表
| P | Q | P \| Q |
| - | - | ------ |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
發現把 AND 真值表的所有值加上 NOT 就變成 OR 的真值表了
## `bitMask()`
這題的概念是先算出要塞幾個 1 進去裡面，之後再把 1 移動到指定的位置，只是現在這種做法會有好幾個undefined behavior。第一個是假如 `diff` 是負數，第四行的 `<< diff` 就會是個 undefined behabior ，再來是對 `~0` 進行位移，因為 `~0` 完之後值會變成 -1 ，對負數向左位移在 C99 標準裡是 undefined behavior ，還有第五行如果 mask 是 0xFFFFFFFF 也會因為對負數位移 0 個位置而產生 undefined behavior 。
``` C=
int bitMask(int highbit, int lowbit)
{
int diff = highbit + ~lowbit + 1;
int mask = ~(~0 << diff << 1);
mask <<= lowbit;
return mask & ~(diff >> 30 >> 1);
}
```
`diff` 是負數這點要解決比較容易，補上底下第四行的程式碼把負數變成無意義的非負數就可以了，向左位移負數的問題則暫時沒想到避免的方法。
``` C=
int bitMask(int highbit, int lowbit)
{
int diff = highbit + ~lowbit + 1;
int udiff = (diff >> 30 >> 1) ^ diff;
int mask = ~(~0 << udiff << 1);
mask <<= lowbit;
return mask & ~(diff >> 30 >> 1);
}
```
## `bitMatch()`
這題是把一樣的bit標出來，也就是 XNOR ，一開始先嘗試用 AND 、 OR 和 NOT 湊出來。
``` C
int bitMatch(int x, int y)
{
return (x & y) | (~x & ~y);
}
```
只是題目不允許使用 OR ，所以再想辦法把 OR 去掉，想法跟 `bitAnd()` 那題差不多
```
int bitMatch(int x, int y)
{
return ~(~(x & y) & ~(~x & ~y));
}
```
## `bitNor()`
這題只是單純的把 OR 去掉，作法跟上一題的後半差不多。
## `bitOr()`
這題跟上面那題一樣也是把 OR 去掉
## `bitParity()`
這題在之前考試有出現過兩次，只是第一次考試有用到 Macro ，第三次考試則是用到了 0x11111111 這個不好湊出來的數，所以用了跟前面 `bang()` 那題一樣的概念，只是差別是把所有 bits 做 XOR，得到的結果就是奇偶較驗的結果。
## `bitReverse()`
這題的第一個想到的想法是利用 divide and conquer 的概念，先 16 bits 一組交換，再 8 bits 一組交換，持續做下去就可以交換完了，只是還沒想到 Mask 要怎麼產生比較好。
## `bitXor()`
`bitMatch()` 那題實際上是在做 XNOR ，所以只要再加一個 NOT 就變成 XOR 了
## `conditional()`
這題允許使用 `!` ，所以先利用 `!` 得到 0 或 1 用來判斷要回傳 y 或是 z，然後如果得到 1 的話就產生 0xFFFFFFFF 的 mask ，如果是 0 則產生值為 0 的 mask，最後將 y 和 z 分別對 NOT mask 以及 mask 做 AND ，這樣就會根據條件讓其中一個的值為零，另一個的值保持不變，最後再用 OR 把他們合併成結果。
``` C
int conditional(int x, int y, int z)
{
int res = !x;
int mask = ~res + 1;
return (y & ~mask) | (z & mask);
}
```
## `copyLSB()`
這題是把每個位元設定成跟最低位元一樣，結果只會有兩種： 0 和 -1 ，先利用 AND 取出最低的位元，然後對取出的位元做互換正負號，就會得到需要的結果。
## `distinctNegation()`
一開始的想法是需要回傳 0 的情況只有 0 和 0x80000000 ，所以湊出下面這個，但是多了一個 operator，而且用到不允許的 `<<`
``` C
int distinctNegation(int x)
{
return !(!x ^ !(x ^ (1 << 31)));
}
```
後來發現自己想太多了，照題意的 x != -x 判斷就可以寫出符合條件的程式碼。先利用二補數的特性算出 -x ，然後再跟 x 做 XOR ，如果結果是 0 就代表完全相等，只是題目有要求不相等需要回傳 1 ，所以再用 `!!` 把回傳值處理成 0 或 1。
``` C
int distinctNegation(int x)
{
return !!(x ^ (~x + 1));
}
```
## `dividePower2()`
這題是將數字除以 2 的 n 次方，這部分在正數沒什麼問題，因為用 `>>` 操作正數在 C99 標準的定義就是處以 2 的 n 次方，但是負數是 implementation-defined ，而這次作業所使用的 GCC 是直接向右移 1 bit 然後在最左方補上 sign bit 。當數字無法整除的時候計算就會有誤差，原本也想說把負數先轉成正數，做完運算再轉回正數，結果也一樣在無法整除時會有誤差，所以後來直接觀察負數除法的行為。以 -241 向右位移 6 以及除以 $2^6$ 為例
```
0b11111111111111111111111100001111 (-241)
0b11111111111111111111111111111101 (-241 / 64)
0b11111111111111111111111111111100 (-241 >> 6)
```
會發現位移 6 的因為餘數問題需要 + 1 才會變成使用除法的答案，多看幾組數字之後會發現有一個簡易的判斷方法，如果我們要除以 $2^n$ ，原來的數字中最低 n bits 中有任何一個 1 就會導致無法整除，因此結果需要 + 1 才會是除法得到的結果，所以用這種想法寫出以下的程式碼
``` C
int dividePower2(int x, int n)
{
int s = x >> 30 >> 1;
int round = !!(x & ~(s << n));
x >>= n;
return x + (round & s);
}
```
步驟就是先取出最左邊的 bit ，如果為正數結果就會是 0 ，如果為負數結果就會是 -1 ，然後利用位移和 NOT 建立 mask ，之後利用 `!!` 將結果轉成 1 或是 0，只是位移負數是未定義行為，但是還暫時想不到其他作法。之後將 `x` 向右位移後加上計算出來是否要加一的值，只是正數沒有加一的問題，所以先將那個值與 `s` 做一次 AND 。
## `evenBits()`
這題要回傳 0x55555555 ，所以就每次 OR 0x55 之後向左位移 8 bits 就可以完成了。
## `ezThreeFourths()`
這題要把數字乘以 3 後除以 4 ，乘以 3 這部分可以把它拆成乘以 2 後加 1 就容易理解多了，只要把數字向左位移 1 後加上數字本身就可以達成乘以 3 的效果，而處以 4 這部分可以利用和 `dividePower2()` 一樣的概念達成。
## `fitsBits()`
這題的想法是先把負數處理成正數會比較好計算，所以先做絕對值，只是例如 -8 可以用 4 bits 表示， 8 則不行，所以做絕對值的時候負數加一的步驟要省略。之後利用位移來檢查是否有超過 n bits 就可以了，只是因為要把 sign bit 考慮進去，所以只要位移 n - 1 bits 就好了。
## `fitsShort()`
這題跟上面那題一樣，只是 n 為定值而已。
## `floatAbsVal()`
這題是浮點數題目，所以少了很多限制，但是老師在作業說明有說到
> 避免用分支 (branch)，設計時間複雜度為 $O(1)$ 的實作
所以意思是 `if` 、 `for` 、 `while` 、 `switch` 、 `?` 、 `&&` 、 `||` 都要避免使用，不然就會造成分支
這題是要對浮點數做絕對值，浮點數代表正負號的 bit 在最高位，只要把它寫成 0 就可以達成目標了，只是題目有提到如果輸入的數字是 NaN 要回傳原來的值，所以還要判斷是不是 NaN ， 在不用到分支的情況寫出了這樣的程式碼，只是遠遠超過題目所限定的 operater 數。
``` C
unsigned floatAbsVal(unsigned uf)
{
unsigned isnan = (uf >> 23 & 0xFF) == 0xFF;
unsigned frac = !!(uf << 9);
isnan = isnan & frac;
isnan = -isnan;
unsigned mask = ~(1 << 31);
return ((uf & mask) & ~isnan) | (uf & isnan);
}
```
Sign in with Wallet
Connect another wallet