# 2018q3 Homework5 (bits)
contributed by < [`ofAlpaca`](https://github.com/ofAlpaca) >
###### tags: `CSIE5006` `HW`
## 實驗環境
```
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel(R) Xeon(R) CPU E3-1231 v3 @ 3.40GHz
Stepping: 3
CPU MHz: 3548.766
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 6799.62
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 8192K
NUMA node0 CPU(s): 0-7
```
---
## 無法 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 btest.c:17:0:
/usr/include/stdio.h:27:10: fatal error: bits/libc-header-start.h: 沒有此一檔案或目錄
#include <bits/libc-header-start.h>
^~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.
In file included from decl.c:1:0:
/usr/include/stdio.h:27:10: fatal error: bits/libc-header-start.h: 沒有此一檔案或目錄
#include <bits/libc-header-start.h>
^~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.
In file included from /usr/lib/gcc/x86_64-linux-gnu/7/include-fixed/limits.h:194:0,
from /usr/lib/gcc/x86_64-linux-gnu/7/include-fixed/syslimits.h:7,
from /usr/lib/gcc/x86_64-linux-gnu/7/include-fixed/limits.h:34,
from tests.c:3:
/usr/include/limits.h:26:10: fatal error: bits/libc-header-start.h: 沒有此一檔案或目錄
#include <bits/libc-header-start.h>
^~~~~~~~~~~~~~~~~~~~~~~~~~
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 後就可以 make 。
---
## bits.c - integer
### absVal
* (5+1)/10 operation
* 想法 :
* 改良自小考，因為無法使用 `-` 所以改成作兩次 `!` 來得到 `1` ，若 `y` 為 0 則不影響。
* 但是使用 shift left 31 會在 commit 時讓 cppcheck 跳出 Undefined behavior 的 error ，這裡有兩個解決方法，一個是改成 `x >> 30 >> 1` 或是轉型為 unsigned ，但是根據 [DataLab](https://github.com/sysprog21/datalab/blob/master/bits.c#L47) 的要求，是不能使用任何 casting 的，故改採前者解決。在此假設 implicit conversion 也不允許。
* git commit 時會產生 `(error) Shifting signed 32-bit value by 31 bits is undefined behaviour` 的錯誤訊息 :
```clike=
int absVal(int x)
{
int y = x >> 31;
return (x^y) + !!y;
}
```
* 修改後 : (多增加一個 operation:cry:)
```clike=
int absVal(int x)
{
int y = x >> 30 >> 1;
return (x^y) + !!y;
}
```
### addOK
* (6+1)/20 operation
* 想法:
* Overflow 只會發生於**負加負**或是**正加正**，正加負不可能溢位，所以主要檢查負加負之後是否為負，正加正之後是否為正，若不是則溢位。
* `x^z` 與 `y^z` 用於判斷 `x` 和 `y` 是否與相加結果 `z` 的 sign bit 一樣，一樣則為 0 ，否則為 1 。
* 若兩者與 `z` 的 sign bit 都不一樣，那 `&` 的結果會是 1 ，表示溢位。
* 若兩者與 `z` 的 sign bit 都一樣或只有一個不一樣，那 `&` 的結果會是 0 ，表示正常。
* 最後 shift right 31 取 sign bit 並使用 logical NOT ( **!** ) 得到 0 或 1 。
以下只看 sign bit :
| & | y^z : 0 | y^z : 1 |
| -------- | -------- | -------- |
| x^z : 0 | 0 | 0 |
| x^z : 1 | 0 | 1 |
* git commit 時會產生 `(error) Shifting signed 32-bit value by 31 bits is undefined behaviour` 的錯誤訊息 :
```clike=
int addOK(int x, int y)
{
int z = x + y;
return !(((x ^ z) & (y ^ z)) >> 31) ;
}
```
* 修改後 : (多增加一個 operation:cry:)
```clike=
int addOK(int x, int y)
{
int z = x + y;
return !(((x ^ z) & (y ^ z)) >> 30 >> 1) ;
}
```
### allEvenBits
* 9/12 operation
* 想法 :
* 使用 `&` 可以確保所有偶位元都為 1 。
* 只要不作 `x &= x >> 1` ，那奇偶位元的結果就不會合在一起。
* 最後再取 LSB 即可。
```clike=
int allEvenBits(int x)
{
x &= x >> 16;
x &= x >> 8;
x &= x >> 4;
x &= x >> 2;
return x & 0x1;
}
```
### allOddBits
* 10/12 operation
* 想法 :
* 道理與 `allEvenBits` 相同，只是多了 shift right 1 。
```clike=
int allOddBits(int x)
{
x &= x >> 16;
x &= x >> 8;
x &= x >> 4;
x &= x >> 2;
return (x >> 1) & 0x1;
}
```
### anyEvenBits
* 9/12 operation
```clike=
int anyEvenBit(int x)
{
x |= x >> 16;
x |= x >> 8;
x |= x >> 4;
x |= x >> 2;
return x & 0x1;
}
```
### anyOddBits
* 10/12 operation
```clike=
int anyOddBit(int x)
{
x |= x >> 16;
x |= x >> 8;
x |= x >> 4;
x |= x >> 2;
return (x >> 1) & 0x1;
}
```
### bang
* (5+1)/12 operation
* 想法 :
* 除了 0 以外，其他數值的二補數都是正負號相反的，因此當某數值與其二補數作 `OR` 後的 sign bit 必定會是 1 。
* 若 sign bit 為 1 ， shift right 31 後會是 -1 ，故再加 1 使其結果為 0 ; 若 sign bit 為 0 ， shift right 31 後會是 0 ，再加 1 使其結果為 1 。
* git commit 時會產生 `(error) Shifting signed 32-bit value by 31 bits is undefined behaviour` 的錯誤訊息 :
```clike=
int bang(int x)
{
return ((x | (~x + 1)) >> 31) + 1;
}
```
* 修改後 : (多增加一個 operation:cry:)
```clike=
int bang(int x)
{
return ((x | (~x + 1)) >> 30 >> 1) + 1;
}
```
### bitAnd
* 4/8 operation
* 想法 :
* 使用 [De Morgan's laws](https://en.wikipedia.org/wiki/De_Morgan%27s_laws) : `x & y = ~~(x & y) = ~(~x | ~y)` 。
```clike=
int bitAnd(int x, int y)
{
return ~(~x | ~y);
}
```
### bitCount
* 33/40 operation
* 想法 :
* 將所有 bit 相加後就可計算總共有幾個 1-bit ，但是如果一次一次位移來相加，絕對會超過 40 operation ，所以改用類似 SIMD 的方式去相加。
* 把相鄰的 bit 相加後，將原本所在的那兩個 bit 的位置當成是暫存，儲存相加後的結果。 2-bits 足夠表示 bit 與 bit 相加的結果，不用擔心溢位。
* 接下來都如法炮製，相鄰 2-bits 相加，並把結果儲存到這 4-bits 的位置。
* 一直做到剩下兩個 16-bits 為止，再把兩者相加就是總 bit 數了。
```
x -> 00 01 00 11 00 00 01 10 00 01 11 10 11 10 10 01
-----------------------------------------------
2-bits tmp -> 00|01|00|10|00|00|01|01|00|01|10|01|10|01|01|01
-----------------------------------------------
4-bits tmp -> 00 01|00 10|00 00|00 10|00 01|00 11|00 11|00 10
-----------------------------------------------
8-bits tmp -> 00 00 00 11|00 00 00 10|00 00 01 00|00 00 01 01
-----------------------------------------------
16-bits tmp -> 00 00 00 00 00 00 01 01|00 00 00 00 00 00 10 01
```
```clike=
int bitCount(int x)
{
int mask_01 = 0x55;
int mask_0011 = 0x33;
int mask_00001111 = 0x0F;
int mask_FF = 0xFF;
// mask 0x55555555
mask_01 = mask_01|mask_01 << 8;
mask_01 = mask_01|mask_01 << 16;
// mask 0x33333333
mask_0011 = mask_0011|mask_0011 << 8;
mask_0011 = mask_0011|mask_0011 << 16;
// mask 0x0F0F0F0F
mask_00001111 = mask_00001111|mask_00001111 << 8;
mask_00001111 = mask_00001111|mask_00001111 << 16;
// mask 0x00FF00FF
mask_FF = mask_FF|mask_FF << 16;
x = (x & mask_01) + ((x >> 1) & mask_01);
x = (x & mask_0011) + ((x >> 2) & mask_0011);
x = (x & mask_00001111) + ((x >> 4) & mask_00001111);
x = (x & mask_FF) + ((x >> 8) & mask_FF);
return (x + (x >> 16)) & 0xFF;
}
```
### bitMask
* 7/16 operation
* 想法 :
* highbit 是從 LSB 開始數到第 highbit 的位置。
* lowbit 是從 LSB 開始數第 lowbit 的位置。
* 圖解如下 :
```
bitMask(highbit = 5, lowbit = 3) :
mask = 0x38 = 0 0 1 1 1 0 0 0
[7][6][5][4][3][2][1][0]
```
* 將 0xFFFFFFFF 作 shift left ( highbit + 1) 後取一補數，可得到 highbit 的 mask 。
* 將 0xFFFFFFFF 作 shift left lowbit 即可得到 lowbit 的 mask 。
* 最後將兩者作 `&` 即可找到對應的 mask 。
* 圖解如下 : (以 8-bits 為例，highbit = 5, lowbit = 3)
```
0xFF -> shiftleft (5+1) -> 1100 0000 -> ones' complement -> 0011 1111
0xFF -> shiftleft 3 -> 1111 1000
---------------------------------------------------------------------
0011 1111
& 1111 1000
-------------
0011 1000 = 0x38
```
* 一開始的版本 :
```clike=
int bitMask(int highbit, int lowbit)
{
int full_one = ~0x00; // get 0xFFFFFFFF
int high_mask = full_one << (highbit + 1);
int low_mask = full_one << lowbit;
return ~high_mask & low_mask;
}
```
然而，**以上的程式碼是有問題的**，當 highbit = 31 ， lowbit = 0 時，照理來說答案應該要是 0xFFFFFFFF ，但結果卻是 0x00 。原因是 ==Undefined behavior== ，根據 C99 的描述，如果 shift left 後的值是無法表示的，則為 UB ，以上程式碼會讓 `full_one` 作 shift left 32 時產生 UB 因而造成非預期結果。
> [C99 6.5.7] The result of E1 << E2 is E1 left-shifted E2 bit positions; acated bits are filled with zeros. If E1 has an unsigned type, the alue of the result is E1 × 2^E2^ , reduced modulo one more than the aximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 × 2^E2^ is representable in the result type, then that is the resulting value; otherwise, **the behavior is undefined**.
* 換個寫法就不會造成 UB 了 :
```clike=
int bitMask(int highbit, int lowbit)
{
int full_one = ~0x00; // get 0xFFFFFFFF
int high_mask = (full_one << highbit) << 1 ;
int low_mask = full_one << lowbit;
return ~high_mask & low_mask;
}
```
### bitMatch
* 7/14 operation
* 想法 :
* 受限於題目只能用 `~` 和 `&` ，所以要想辦法取代 `^` 。
* 可以使用下圖寫出等價於 `XOR` 的電路 :
* `~(~(~a & b) & ~(a & ~b))` 由於此函式要的結果與 `XOR` 相反，所以去掉一個 `~` 。
```clike=
int bitMatch(int x, int y)
{
return ~(~x & y) & ~(x & ~y);
}
```
### bitNor 、 bitOr
* bitNot : 3/8 operation
* bitOr : 4/8 operation
* 想法 :
* 一樣使用 De Morgan’s laws 就好
```clike=
int bitNor(int x, int y)
{
return ~x & ~y;
}
int bitOr(int x, int y)
{
return ~(~x & ~y);
}
```
### bitParity
* 11/20 operation
* 想法 :
* 透過一連串的 shift right 與 `XOR` 計算 1 有偶數還是奇數個。
* 下圖以 8-bits 來舉例 :
```
0111 0011
XOR 0000 0111 (>> 4)
---------------------
0111 0100 --> 0111 0100
XOR 0001 0001 (>> 2)
----------------------
0110 0101 --> 0110 0101
XOR 0011 0010 (>> 1)
----------------------
0101 0111 --> LSB 為 1
```
```clike=
int bitParity(int x)
{
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return x & 0x1;
}
```
### bitReverse
* 40/45 operation
* 想法 :
* 要將數值的 bit 位元排列逆轉過來，其實有個簡單的方法，那就是兩兩互相交換。
* 說的準確點是先相鄰 bit 互換，再相鄰 2-bits 互換，再相鄰 4-bits 互換，持續換到 16-bits ，這樣換完排列順序就會逆轉。
```clike=
int bitReverse(int x)
{
int mask_01 = 0x55;
int mask_0011 = 0x33;
int mask_00001111 = 0x0F;
int mask_FF = 0xFF;
int mask_FFFF = mask_FF | mask_FF << 8;
// mask 0x55555555
mask_01 = mask_01 | mask_01 << 8;
mask_01 = mask_01 | mask_01 << 16;
// mask 0x33333333
mask_0011 = mask_0011 | mask_0011 << 8;
mask_0011 = mask_0011 | mask_0011 << 16;
// mask 0x0F0F0F0F
mask_00001111 = mask_00001111 | mask_00001111 << 8;
mask_00001111 = mask_00001111 | mask_00001111 << 16;
// mask 0x00FF00FF
mask_FF = mask_FF | mask_FF << 16;
x = ((x & mask_01) << 1) | ((x >> 1) & mask_01);
x = ((x & mask_0011) << 2) | ((x >> 2) & mask_0011);
x = ((x & mask_00001111) << 4) | ((x >> 4) & mask_00001111);
x = ((x & mask_FF) << 8) | ((x >> 8) & mask_FF);
x = ((x & mask_FFFF) << 16) | ((x >> 16) & mask_FFFF);
return x;
}
```
### bitXor
* 8/14 operation
* 想法 :
* 根據邏輯閘的電路來寫就可以了
```clike=
int bitXor(int x, int y)
{
return ~(~(~x & y) & ~(x & ~y));
}
```
### bitSwap
* 14/25 operation
* 想法 :
* 先靠 shift left 3 來取得指定的 byte 是從哪個 bit 開始
* 使用 shift right 後再取出該 byte 的數值
* 使用 `XOR` 將原本該 byte 位置的數值覆蓋為 0
* 再用 `OR` 將新的 byte 貼上
```clike=
int byteSwap(int x, int n, int m)
{
int n_shift = n << 3;
int m_shift = m << 3;
int n_byte = (x >> n_shift) & 0xff;
int m_byte = (x >> m_shift) & 0xff;
x ^= m_byte << m_shift;
x |= n_byte << m_shift;
x ^= n_byte << n_shift;
x |= m_byte << n_shift;
return x;
}
```
### conditional
* 8/16 operation
```clike=
int conditional(int x, int y, int z)
{
x = !!x;
x = ~x + 1; // get all 0 or 1
return (x & y) | (~x & z);
}
```
### countLeadingZero
* 44/50 operation
* 想法 :
* 將所有的 1-bit 向右填滿，再取其一補數，便可以得到從左邊數來最多的 0 的 mask 。
* 以下示範 : (以 8-bits 為例)
```
0001 1010
OR 0000 0001 (>> 4)
-------------------
0001 1011 -> 0001 1011
OR 0000 1101 (>> 2)
-------------------
0001 1111 -> 0001 1111
OR 0000 1111 (>> 1)
-------------------
0001 1111 ->(~)-> 1110 0000
```
* 最後再做 `bitCount` 即可求出答案。
```clike=
int countLeadingZero(int x)
{
x |= x >> 16;
x |= x >> 8;
x |= x >> 4;
x |= x >> 2;
x |= x >> 1;
x = ~x;
// do bitCount
int mask_01 = 0x55;
int mask_0011 = 0x33;
int mask_00001111 = 0x0F;
int mask_FF = 0xFF;
// mask 0x55555555
mask_01 = mask_01 | mask_01 << 8;
mask_01 = mask_01 | mask_01 << 16;
// mask 0x33333333
mask_0011 = mask_0011 | mask_0011 << 8;
mask_0011 = mask_0011 | mask_0011 << 16;
// mask 0x0F0F0F0F
mask_00001111 = mask_00001111 | mask_00001111 << 8;
mask_00001111 = mask_00001111 | mask_00001111 << 16;
// mask 0x00FF00FF
mask_FF = mask_FF | mask_FF << 16;
x = (x & mask_01) + ((x >> 1) & mask_01);
x = (x & mask_0011) + ((x >> 2) & mask_0011);
x = (x & mask_00001111) + ((x >> 4) & mask_00001111);
x = (x & mask_FF) + ((x >> 8) & mask_FF);
return (x + (x >> 16)) & 0xFF;
}
```
### copyLSB
* 3/5 operation
* 想法 :
* 先 mask 出 LSB 後取其二補數。
* 若 LSB 為 1 ，二補數為 0xFFFFFFFF (-1) ; 若 LSB 為 0 ，二補數仍為 0 。
```clike=
int copyLSB(int x)
{
x = x & 0x1;
return ~x + 1;
}
```
### distinctNegation
* 5/5 operation
* 想法 :
* 比較某數值與其二補數是否相同，若兩者 `XOR` 後結果為 0 則表示該數值的正數與負數完全一樣，若為非 0 則表示兩者不同。
```clike=
int distinctNegation(int x)
{
return !!(x ^ (~x + 1));
}
```
### dividePower2
* (9+1)/15 operation
* 想法 :
* 正數除 2^n^ 會向下取整數，等同於向零取整數；雖然負數也會向下取整數，但卻不是向零取整數，故結果須再加 1 。
* 首先判斷是否需要加 1 ，如果負數作 shift right 後有 bit 遺失，則表示需要 +1 。
* 下方可以看到 -6 除以 2^2^ 後應該要是 -1 ，但結果卻是 -2 ，其原因是在位移的過程中遺失了位元 :
```
1010 -> (>> 2) -> 1110
-6 -2
```
* 所以只要判斷**是否遺失位元**與**是否為負數**即可，若都是則加 1 來向零取整數。
```clike=
int dividePower2(int x, int n)
{
int missing_bit = !!(x ^ ((x >> n) << n));
int neg = x >> 31;
return (x >> n) + (missing_bit & neg);
}
```
* 因為 `neg = x >> 31` 會造成 cppcheck error ，故應修改為 `neg = x >> 30 >> 1` 。
### evenBits
* 4/8 operation
* 想法 :
* 規定最多只能使用 8-bits ，所以只要把 8-bits 的 `0101 0101` 複製成 32-bits 即可。
```clike=
int evenBits(void)
{
int x = 0x55;
x |= x << 8;
x |= x << 16;
return x;
}
```
### ezThreeFourths
* (11+1)/12 operation
* 想法 :
* 先將數值乘上 3 ，再除以 4 即可。
* 由於也需要向零取整數，所以延續 `dividePower2` 的部份程式碼。
```clike=
int ezThreeFourths(int x)
{
x = (x << 1) + x; // 2x + x = 3x
// do dividePower2
int missing_bit = !!(x ^ ((x >> 2) << 2));
int neg = x >> 31;
return (x >> 2) + (missing_bit & neg);
}
```
* 因為 `neg = x >> 31` 會造成 cppcheck error ，故應修改為 `neg = x >> 30 >> 1` 。
### fitsBits
* 7/15 operation
* 想法 :
* 如果說 n-bits 就足夠表示該數值，那麼左位移掉多餘的 bits 照理來說應該也不影響數值才對。
* 所以先左位移掉多餘的 bits 後再右位移回來，比較和原本的有沒有差異。
```clike=
int fitsBits(int x, int n)
{
int shift = 32 + (~n + 1); // same as 32 - n
int y = x << shift >> shift;
return !(x ^ y);
}
```
### fitShort
* 4/8 operation
```clike=
int fitsShort(int x)
{
int y = x << 16 >> 16;
return !(x ^ y);
}
```
---
## bits.c - floating point
### floatAbsVal
* 9/10 operation
* 想法 :
* 只需要修改 floating point 上的 sign bit 就好，最快的方法就是先 shift left 1 再 shift right 1 回來，由於是型別是 unsigend 所以右位移回來並不會有 sign extension 。
* 需要注意的是當值為 NaN 時，就改回傳參數。
* 判斷方法就是將 exp 與 frac 的部份取出並檢查是否為 NaN ，如果 exp 為 0xff 且 frac 不為 0 ，則表示是 NaN ，回傳參數。
```clike=
unsigned floatAbsVal(unsigned uf)
{
unsigned _exp = (uf >> 23) & 0xff;
unsigned _frac = uf << 9 >> 9;
if (!(_exp ^ 0xff) && _frac)
return uf;
return uf << 1 >> 1;
}
```
### floatFloat2Int
* 17/30 operation
* 想法 :
* 因為是要從 floating point 轉成 integer ，所以第一步要做的就是拆解出 `sign` 、 `exp` 、 `frac` 這三個部分。
* 接下來計算 Exponent `E` ，若為負值，表示 `frac` 部分是小數，轉成正數一定會被捨去，故可以直接回傳 0 ， denormalized 的 case 也包含在此。
* 下一個 `else if` 是要處理 special case 的，照理來說應該填 `else if (E == 128)` ，也就是當 `exp` 都為 1 時的情況，那為什麼改成 `E > 23` 呢? 由於 `frac` 只有 23 位，當 `E` 大於 23 時， right-shifted 會把所有位元都移除，也就是只剩下 1 。
* 最後再根據 `sign` 是否為 1 決定是否取其二補數。
```clike=
int floatFloat2Int(unsigned uf)
{
// s | exp | frac
// 1-bit| 8-bits | 23-bits
unsigned _sign = ~(uf >> 31) + 1;
unsigned _exp = (uf >> 23) & 0xff;
unsigned _frac = uf & 0x7fffff;
unsigned bias = 127;
int E = _exp - bias;
if (E < 0) // exp too small, truncated
return 0;
else if ( E > 23 ) // exp is full set, only Nan and infinity
// why not 128 ? because 23 is the most bit it can shift.
// Further left-shift will become 1.
return 0x80000000u;
_frac |= 0x800000;
_frac = _frac >> (23 - E);
return ((_frac ^ _sign) + (_sign & 1));
}
```
### floatInt2Float
* 29/30 operation
* 想法 :
* 第一步是先判斷正負並取其 `sign` ，如果是負數還需要轉成正數再做處理，因為表示法不再是二補數了。
* 接下來一直做 left-shifted 直到 Most Significant 1-bit ，記錄其位置， 31 減去該位置後可以得到 Exponent ，並計算 `exp` ，位移後在那個 Most Significant 1-bit 之後的部分即是 `frac` 。
* 接著再將 `sign` 、 `exp` 、 `frac` 使用 `OR` 作融合即可得到結果。
* 但還需注意的是**捨入**，如果被捨棄的部分是超過 0.5 的話須進位，如果剛好 0.5 則需要檢查進位後是否為偶數，是則進位，否則捨棄。
```clike=
unsigned floatInt2Float(int x)
{
unsigned _sign = 0, _exp = 0, _frac = 0, result = 0 ;
unsigned MSB = 1 << 31;
unsigned bias = 127;
int i = 0;
if (x >> 31) {
_sign = 1;
x = ~x + 1;
}
if (x != 0) {
while (!(x & MSB)) {
x = x << 1;
i = i + 1;
}
x = x << 1;
i = 31 - i;
}else
return 0;
_exp = bias + i; // E = exp - bias
_frac = x;
result = _sign << 31;
result |= _exp << 23 ;
result |= _frac >> 9;
// check for rounding
if ((_frac >> 8) & 1) {
// truncated bits are more than 1/2
if (_frac & 0xff) // has 1/2 and the further bits are not zero
return result + 1;
else { // has 1/2 but the further bits are all zero
// then, decided by the LSB
if (result & 1) // LSB is 1, then add 1
return result + 1;
else // LSB is 0, then don't add 1
return result;
}
}
// truncated bits are less than 1/2
return result;
}
```
### floatIsEqual
 為什麼會 timeout
### floatIsLess
 為什麼會 timeout
---
## bits.c - Arithmetic
### getByte
* 3/6 operation
* 想法 :
* 將 `n` 乘上 8 可以得到要取得位元組的起始位置。
* 把 `x` 右位移後即可得到該位元組。
```clike=
int getByte(int x, int n)
{
int shift = n << 3;
return (x >> shift) & 0xff;
}
```
### greatestBitPos
* (15+1) / 70 operaiton
* 想法 :
* 使用 shift 和 `OR` 將 Most Significant 1-bit 右手邊的位元全填成 1 。
* 由於 MS 1-bit 的左手邊位元全會是 0 ，故可作 right-shift 1 ，並與原本的數值做 `XOR` 來得到 MS 1-bit 的 mask。作 `& ~(1 << 31)` 只是為了要避免 sign extension 產生額外的 1 。
```
0110 000 => use shift and OR => 0111 1111 => right-shift 1 => 0011 1111
0111 1111 (x)
^ 0011 1111 (x >> 1)
------------
0100 0000 <- MS 1 bit mask
```
```clike=
int greatestBitPos(int x)
{
x |= x >> 16;
x |= x >> 8;
x |= x >> 4;
x |= x >> 2;
x |= x >> 1;
int y = (x >> 1) & ~(1 << 30 << 1);
return x ^ y;
}
```
### howManyBits
* 46/90 operation
* 想法 :
* 對於正數，只要找到 MS 1-bit 就知道他需要幾位才夠表示，但是負數卻不行。
* `1111 1000` 的最少表示位元數是 4 ，前面的 4 個 1 都是可以忽略的，重點是在 `1000` ，對於負數，只要找到其從 MSB 開始的連續 1 之最右手邊的位置即是以二補數表示所需最少位元數。
* 要找到該位置，先取其一補數得到 `0000 0111` ，再找到其 MS 1-bit 的左 1 bit 即是。
```clike=
int howManyBits(int x)
{
int sign = x >> 31; // pos: 0, neg: 0xffffffff
int num ;
x = x ^ sign; // if it's neg, then get ones' complement.
x |= x >> 16;
x |= x >> 8;
x |= x >> 4;
x |= x >> 2;
x |= x >> 1;
// do bitCount
int mask_01 = 0x55;
int mask_0011 = 0x33;
int mask_00001111 = 0x0F;
int mask_FF = 0xFF;
// mask 0x55555555
mask_01 = mask_01 | mask_01 << 8;
mask_01 = mask_01 | mask_01 << 16;
// mask 0x33333333
mask_0011 = mask_0011 | mask_0011 << 8;
mask_0011 = mask_0011 | mask_0011 << 16;
// mask 0x0F0F0F0F
mask_00001111 = mask_00001111 | mask_00001111 << 8;
mask_00001111 = mask_00001111 | mask_00001111 << 16;
// mask 0x00FF00FF
mask_FF = mask_FF | mask_FF << 16;
x = (x & mask_01) + ((x >> 1) & mask_01);
x = (x & mask_0011) + ((x >> 2) & mask_0011);
x = (x & mask_00001111) + ((x >> 4) & mask_00001111);
x = (x & mask_FF) + ((x >> 8) & mask_FF);
num = (x + (x >> 16)) & 0xFF;
return num + 1;
}
```
### implication
* 2/5 operation
* 想法 :
* $p \to q \equiv \neg p \lor q$
* 真值表 :
| $p$ | $q$ | $\neg p$ | $\neg p \lor q$ |
| -------- | -------- | -------- | ---|
| 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 |
```clike=
int implication(int x, int y)
{
return (!x) | y;
}
```
### isAsciiDigit
* 9/15 operation
* 想法 :
* 只要 x 的數值是在 0x30 ~ 0x39 之間即是 Ascii code 的 0 ~ 9 。
* 也就是說 `x - 0x30` 與 `0x39 - x` 都必須要大於等於 0 。
```clike=
int isAsciiDigit(int x)
{
int upper = 0x39 + (~x + 1);
int lower = x + (~0x30 + 1);
return !((lower | upper) >> 31);
}
```
### isEqual
* 2/5 operation
```clike=
int isEqual(int x, int y)
{
return !(x ^ y);
}
```
### isGreater 、 isLess
* 14/24 operation
* 想法 : (兩題思路一樣，不再贅述，以 `isGreater` 作解釋)
* 將 `x > y` 看成 `0 > y - x` 來判斷。
* 要區分為有 Overflow 的 case 和沒有 Overflow 的 case 。
* 如果 `x` 、 `y` 正負號相同，則表示沒有 Overflow ，就計算 `y - x` 是否大於 0 。
* 如果 `x` 、 `y` 正負號相異，則表示可能有 Overflow ，就根據 `y` 的正負號去判斷是否大於 0 。
* 使用 `condition` 的技巧去選擇該怎麼判斷。
```clike=
int isGreater(int x, int y)
{
int same_sign = ((x ^ y) >> 31) & 1;
int y_sign = (y >> 31) & 1;
int gt = ((y + (~x + 1)) >> 31) & 1;
return (y_sign & same_sign) | (gt & !same_sign);
}
int isLess(int x, int y)
{
int same_sign = ((x ^ y) >> 31) & 1;
int x_sign = (x >> 31) & 1;
int lt = ((x + (~y + 1)) >> 31) & 1;
return (x_sign & same_sign) | (lt & !same_sign);
}
```
### isLessOrEqual
* (14+3)/24 operation
* 想法 :
* 因為可能會 Overflow ，所以要分成**有溢位**和**沒溢位**來處理。
* 將 `x <= y` 解讀為 `0 <= y - x` ，只有當 `x` 、 `y` 是異號時才有可能 Overflow 。
* 當如果 `x` 、 `y` 為異號，則 `y - x` 結果之正負號一定會等於 `y` 的正負號，除非 Overflow 。
* 這裡處理 Overflow 的方法為當 `x` 、 `y` 是異號時，也就是可能發生溢位的情況下，不去計算其結果，根據 `y` 的正負號來決定。
```clike=
int isLessOrEqual(int x, int y)
{
int x_sign = !(x >> 30 >> 1);
int y_sign = !(y >> 30 >> 1);
int same_sign = x_sign ^ y_sign;
int z = !((y + (~x + 1)) >> 30 >> 1); // z >= 0 : 0, z < 0 : 1
return (z & (!same_sign)) | (y_sign & same_sign);
}
```
### isNonZero
* 5/10 operation
* 想法 :
* 0 的特色是其二補數一模一樣，但不幸的是 Tmin 也有同樣的特性，不過幸好 0 沒有 Tmin 的 sign bit ， 所以還是可以靠這個來分辨。
```clike=
int isNonZero(int x)
{
return ((x | (~x + 1)) >> 31) & 1;
}
```
### isPallindrome
* 43/45 operation
* 想法 :
* 做前面提到的 `bitReverse` 後比較看看和原本的一不一樣即可。
```clike=
int isPallindrome(int x)
{
int mask_01 = 0x55;
int mask_0011 = 0x33;
int mask_00001111 = 0x0F;
int mask_FF = 0xFF;
int mask_FFFF = mask_FF | mask_FF << 8;
int y = x; // original value
// mask 0x55555555
mask_01 = mask_01 | mask_01 << 8;
mask_01 = mask_01 | mask_01 << 16;
// mask 0x33333333
mask_0011 = mask_0011 | mask_0011 << 8;
mask_0011 = mask_0011 | mask_0011 << 16;
// mask 0x0F0F0F0F
mask_00001111 = mask_00001111 | mask_00001111 << 8;
mask_00001111 = mask_00001111 | mask_00001111 << 16;
// mask 0x00FF00FF
mask_FF = mask_FF | mask_FF << 16;
x = ((x & mask_01) << 1) | ((x >> 1) & mask_01);
x = ((x & mask_0011) << 2) | ((x >> 2) & mask_0011);
x = ((x & mask_00001111) << 4) | ((x >> 4) & mask_00001111);
x = ((x & mask_FF) << 8) | ((x >> 8) & mask_FF);
x = ((x & mask_FFFF) << 16) | ((x >> 16) & mask_FFFF);
return !(x ^ y);
}
```
Sign in with Wallet
Connect another wallet