# 2018q3 Homework5 (bits)
###### tags: `C語言`
contributed by < `asd757817` >
**環境:**
|作業系統|kernel|gcc version|
|-|-|-|
|Ubuntu 16.04 x64|4.15.0-38-generic|gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.10)|
**作業要求：**
1. 只能使用： ! ˜ & ˆ | + << >> 等運算子實作函式
2. 盡可能精簡使用的運算子
3. 不能呼叫其他函式
---
## absVal： 回傳絕對值
以 32-bit 為例，input 為 N:
* 判斷 N 的正負號，做 `>>`
- if N > 0, (N >> 31) = 0 (0x0)
- if N < 0, (N >> 31) = -1 (0xffffffff)
* `N ^ (N >> 31)`:
- if N > 0, = N
- if N < 0, = ~N
* `abs(N) =`
- if N > 0, = N
- if N < 0, = ~N + 1
```C
int absVal(int x)
{
int y = x >> 31;
return ( x ^ y ) - y ;
}
```
## addOK： 檢查兩數相加是否會發生 overflow
* 32-bit 有號整數最大值為 0x7fffffff；最小值為 0x80000000。
* overflow 只出現在兩個情況:
1. 正 + 正 = 負
2. 負 + 負 = 正
Z = X + Y； 0 為正； 1 為負，truth table:
```
Z
X Y | 0 | 1
----------------
0 0 | 1 | 0
1 1 | 0 | 1
1 0 | 1 | 1
0 1 | 1 | 1
```
* 當 X、Y 同時與 Z 異號時表示 overflow，回傳 0，反之回傳 1。
=> [(sign_X ^ sign_Z) & (sign_Y ^ sign_Z)]
上述表示式為 1 時表示 overflow，0 則反之，因此需要再做一次 `!` 運算。
```C
int addOK(int x, int y)
{
int z = x+y;
return !(((z^x)&(z^y))>>31);
}
```
### allEvenBits： 檢查偶數位的位置數值是不是全是 1，是的話回傳 1
32 bits： 31, 30, ..... , 1, 0 ，若 0、2、4、......、30 都是 1 時回傳 1。
判斷方式： 將所有偶數位的數值做 & 運算，結果為 1 表示所有偶數位數值都是 1。
透過右移對不同的位置做運算
原 x 內各 bit 為：
| 31 | 30 |... |1 |0 |
| -------- | -------- | -------- | -------- | -------- |
| b31 | b30 | ... |b1 | b0 |
bn： 表示第 n 位的數值
執行 ```x &= x>>16``` 後，x 內第 0 ~ 15 bit 的情況：
| 15 | 14 |... |1 |0 |
| -------- | -------- | -------- | -------- | -------- |
| b15 & b31 | b14 & b30 | ... | b1 & b17 | b0 & b16 |
再執行 ```x &= x>>8``` 後，x 內第 0 ~ 7 bit 的情況：
| 7 | ... |1 |0 |
| -------- | -------- | -------- | -------- |
| b7 & b23 & b15 & b31 | ... | b1 & b17 & b9 & b25 | b0 & b16 & b8 & b24 |
以此類推直到第 0 位置出現 b0 & b2 & b4 & ... & b30，此時就可以把第 0 位置的數值做為回傳值回傳。
```C
int allEvenBits(int x)
{
x &= x>>16;
x &= x>>8;
x &= x>>4;
x &= x>>2;
return x&1;
}
```
### allOddBits： 檢查奇數位的位置數值是不是全是 1，是的話回傳 1
作法同 allEvenBits，allEvenBits 在 return 前 x 第 0、1 bit 的內容為：
| 1 | 0 |
| -------- | -------- |
| b1 & b3 &.....& b31 | b0 & b2 &......& b30|
因此 allEvenBits 是 ```return x & 1 ``` ，奇數位的檢查則是回傳第 1 bit 的數值即可，
```return (x>>1) & 1``` 將原本 x 右移一位在 & 1 取得數值。
```C
int allOddBits(int x)
{
x &= x>>16;
x &= x>>8;
x &= x>>4;
x &= x>>2;
return (x >> 1) & 1;
}
```
### anyEvenBit： 檢查偶數位的位置是否有 1，有一個是 1 就回傳 1
判斷方法類似於 allEvenBit，但因為只要有一個是 1 就回傳 1，因此把原本函式的 & 改成 |
```C
int anyEvenBit(int x)
{
x |= x >> 16;
x |= x >> 8;
x |= x >> 4;
x |= x >> 2;
return x & 1;
}
```
### anyOddBit： 檢查奇數位的位置是否有 1，有一個是 1 就回傳 1
判斷方法類似於 allOddBit，但因為只要有一個是 1 就回傳 1，因此把原本函式的 & 改成 |
```C
int anyOddBit(int x)
{
x |= x >> 16;
x |= x >> 8;
x |= x >> 4;
x |= x >> 2;
return (x >> 1) & 1;
}
```
### bang： x 為 0 回傳 1；反之回傳 0
1. 利用 anyOddBit 檢查 32 個 bit 是否有 1
```C
x |= x >> 16;
x |= x >> 8;
x |= x >> 4;
x |= x >> 2;
x |= x >> 1;
return ~(x&1);
/*
若 32 個 bits 中含有 1，執行 x |= x >> 1 後，x = -1 ;
若不含 1 則 x = 0 ;
以 ! 運算使 -1→0、0→1
*/
```
2. 利用二補數：任何非 0 的數與其二補數做 OR 得到的數值都是 -1；0 與其二補數做 OR 還是 0
```C
int bang(int x)
{
return (((~x+1)|x)>>31) + 1;
}
```
### bitAnd： 以 |、~ 實做 &
X & Y 的 Truth table：
```
Y
| 0 1
----------------
X 0 | 0 0
1 | 0 1
```
X OR Y 的 Truth table：
```
Y
| 0 1
----------------
X 0 | 0 1
1 | 1 1
```
AND 運算中，只有 X=1 且 Y=1 時，數值為 1 ； OR 運算中，只有 X=0 且 Y=0 時，數值為 0
將 OR 運算的輸出做 ~ 運算得到：只有 X、Y 都是 0 時輸出為 1；輸入的 X、Y 都必須先經過一次 ~ 運算，使得只有 X、Y 都等於 1 時輸出才會得到 1。
```C
int bitAnd(int x, int y)
{
return ~(~x|~y);
}
```
### bitCount： 計算 32 個 bit 中有幾個是 1
```C
int bitCount(int x)
{
int mask_1 = 0x55555555;
x = (x & mask_1) + ((x>>1) & mask_1);
int mask_2 = 0x33333333;
x = (x & mask_2) + ((x>>2)&mask_2);
int mask_3 = 0x0f0f0f0f;
x = (x & mask_3) + ((x>>4)&mask_3);
int mask_4 = 0x00ff00ff;
x = (x & mask_4) + ((x>>8)&mask_4);
int mask_5 = 0xffff;
x = (x & mask_5) + ((x>>16) & mask_5);
return x;
}
```
### bitMask： 傳入 highbit、lowbit，將兩者範圍內的 bit 設為 1 回傳數值，當 lowbit > highbit 時回傳 0
想法：
```
# 以 (highbit, lowbit) = (16 , 8) 為例，目標是產生下列數值：
00000000 00000000 11111111 00000000
# 可以透過 AND 下列兩數產生
11111111 11111111 11111111 00000000
00000000 00000000 11111111 11111111
# 將 32 bit 都設為 1
11111111 11111111 11111111 11111111
# 左移 8 bit
11111111 11111111 11111111 00000000
# 希望透過右移 16 bit 產生
00000000 00000000 11111111 11111111
```
希望產生上的結果必須將使用 unsigned 型態來實作，使用 gcc 編譯，右移時是補 sign bit，但我們希望左移、右移都是補 0，因此使用 unsigned 。
```C
int bitMask(int highbit, int lowbit)
{
unsigned x = ~0U;
return x & (x >> (31 +(~highbit + 1))) & (x << lowbit);
}
```
### bitMatch： 找出傳入的兩個數 bit 相同的位置
```C
int bitMatch(int x, int y)
{
return ~(x & ~y) & ~( ~x & y );
}
```
### bitNor： 找出傳入的兩個數 bit 都是 0 的位置
```C
int bitNor(int x, int y)
{
return ~x & ~y;
}
```
### bitOr: 找出傳入的兩個數 bit 至少有一個為 1 的位置
```C
int bitOr(int x, int y)
{
return ~(~x & ~y);
}
```
### bitParity： 計算 parity，32 個 bit 中含有奇數個 1 回傳 1，否則回傳 0
```C
int bitParity(int x)
{
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
return (x^(x>>1)) & 1;
}
```
### bitReverse： 將 bit 反轉 (e.g.,0x80000000 → 0x00000001)
```C
int bitReverse(int x)
{
unsigned y = x;
y = ((y & 0xffff0000) >> 16) | ((y & 0x0000ffff) << 16);
y = ((y & 0xff00ff00) >> 8 ) | ((y & 0x00ff00ff) << 8 );
y = ((y & 0xf0f0f0f0) >> 4 ) | ((y & 0x0f0f0f0f) << 4 );
y = ((y & 0xcccccccc) >> 2 ) | ((y & 0x33333333) << 2 );
y = ((y & 0xaaaaaaaa) >> 1 ) | ((y & 0x55555555) << 1 );
return y;
}
```
### bitXor: 將傳入的兩數做 XOR
```C
int bitXor(int x, int y)
{
return ~(~(x & ~y) & ~(~x & y));
}
```
### byteSwap： 將指定的 byte 位置數值交換
```C
int byteSwap(int x, int n, int m)
{
unsigned y = x;
unsigned a = (y & (0xff << ( n << 3 ))) >> ( n << 3 ) << ( m << 3 );
unsigned b = (y & (0xff << ( m << 3 ))) >> ( m << 3 ) << ( n << 3 );
unsigned mask = ~((0xff << (n << 3)) | (0xff << (m << 3)));
return (y & mask)|a|b;
}
```
### getByte： 回傳指定 byte 的數值
```C
int getByte(int x, int n)
{
unsigned y = x;
return (y & (0xff << (n << 3))) >> (n << 3);
}
```
### conditional： 當 x != 0 時回傳 y，否則回傳 z
```C
int conditional(int x, int y, int z)
{
return ((0xffffffff + !x)&y) | ((~!x + 1)&z);
}
```
### copyLSB： 將所有 bit 設為傳入數值的 least significant bit
```C
int copyLSB(int x)
{
return !(x & 1) + 0xffffffff;
}
```
### distinctNegation： 若 x != -x 回傳 1 否則回傳 0
實際上只有 0x0 跟 0x80000000 會回傳 0，其他都會回傳 1。
```C
int distinctNegation(int x)
{
return !!(x ^ (~x + 1));
}
```
### dividePower2： 計算 $x / 2^n$
```C
int dividePower2(int x, int n)
{
unsigned mask = ~(0xffffffff << n);
return (x >> n) + ((x >> 31)&(!!(x & mask)));
}
```
### evenBits： 將偶數位的 bit 都設為 1
```C
int evenBits(void)
{
return 0x55555555;
}
```
### ezThreeFourths：將傳入的數乘以四分之三(無條件捨去)，計算結果應與 x\*3/4 一致
```C
int ezThreeFourths(int x)
{
x = x + x + x;
return (x >> 2) + ((x >> 31)&(!!(x & 0x3)));
}
```
### fitsBits： 傳入 x,n 判斷 x 是否能以 n bit 的有號數系統表示，可以回傳 1 反之回傳 0
想法：
- 以 數字 5 為例，最少要 4 bit 才能表示，4 bit 可表示的範圍: -8 ~ 7
```
# 32 bit 中 5 的表示如下
xxxxxxxx xxxxxxxx xxxxxxxx xxxx0101
# xxxx..... 表示 5 可以安全左移(不發生 overflow)的空間
```
- n >= 4，表示可以安全左移的空間(32 - n)應小於 n 可安全左移的空間，藉由將 x 左移 32 - n 位，檢查是否有發生 overflow 即可判斷 n 是否 >= 4。
- overflow 判斷方式： 左移後在右移判斷數值是否相等
```
# 以 x = 2 , n = 2 檢驗
00000000 00000000 00000000 00000010
# 左移 32 - n = 30 bits
10000000 00000000 00000000 00000000
# 再右移 30 bits
11111111 11111111 11111111 11111111
# 數值改變，表示有發生 overflow，因此可以 n bit 表示 x
```
```C
int fitsBits(int x, int n)
{
int shift_bit = 32 + ~n + 1;
return !(x ^ ((x << shift_bit) >> shift_bit));
}
```
### fitsShort： 檢查 x 是否可以用 16 bits 的二補數系統表示，若可以表示回傳 1，反之回傳 0
```
int fitsShort(int x)
{
return !(x^((x << 16)>>16));
}
```
Sign in with Wallet
Connect another wallet