# 2018q3 Homework5 (bits)
contributed by <[pjchiou](https://github.com/pjchiou)>
---
因為 cppcheck 一直不讓我 commit ，出現以下訊息。
```
[bits.c:114]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour
[bits.c:128]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour
[tests.c:92]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour
[tests.c:110]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour
[tests.c:112]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour
[tests.c:132]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour
[tests.c:141]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour
[tests.c:407]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour
[tests.c:436]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour
[tests.c:551]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour
[tests.c:737]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour
```
所以我先暫時偷改了 ./scripts/pre-commit.hook 內的最後面
```python=
# static analysis
$CPPCHECK $CPPCHECK_OPTS >/dev/null
if [ $? -ne 0 ]; then
RETURN=0
echo "" >&2
echo "Fail to pass static analysis." >&2
echo
fi
```
#4 return 值的部分，從 1 改為 0 。
---
## outline
- 注意事項
- 整數部分
- 浮點數部分
- 整數第二部分
- 深入探討
---
## 注意事項
整個程式分為數個牽設到 bit operation 的實作，每一個題目都有運算子使用個數的限制( `=` 不算 )，測試的方法在 `README.md` 內有。過程中有幾個限制，整數的規定與浮點數不同。
### 整數規定
- 只能用 0~255 的整數。(不能用 `-1`)
- 不能用全域變數。
- 運算子只能用 `~`, `!`, `&`, `|`, `^`, `+`, `<<`, `>>` 。(不能用 `-` !?)
- 禁用 if, do, while, for, switch。
- 禁用 macro。
- 不能自定 function ， 也不能 call function。
- 不能 casting。
- 假設
* 2 補數系統，32 bit 整數。
* `>>` right shift arithmetically ，也就是最左邊 bit 會補 sign bit ，而不是補 0 。
* `>>` 的量在 0~31 之間。
### 浮點數規定
- 可以用流程控制， if, do, while, for, switch。
- 整數範圍沒有限制。
- 運算子沒有限制。
- 禁用 macro。
- 不能自定 function ， 也不能 call function。
- 不能 casting。
- ==不能用 float==。
==最後提醒自己挑戰不要看答案，先自己想。==
---
## 整數部分
### absVal (op:6/10)
#### 求絕對值。
重點在三個關係式
- x^(-1) = ~x
- x^0 = x
- -x = ~x+1
```clike
int absVal(int x)
{
return (x ^ (x >> 31)) + (~(x >> 31) + 1);
}
```
### addOK (op:12/20)
#### 判斷是否會 overflow/underflow ，1 是會；0 不會。
令 z = x+y，判斷 x 與 y 同號，但 x 與 z 異號的情況。
- 若 x 與 y 異號，則不可能 overflow/underflow。
- (x>>31) ^ (y>>31) 為 0 表示 x 與 y 同號、非 0 為異號。(非 0 不代表為 1 )
- 若我們令
* (x>>31) ^ (y>>31) -> (a)式
* (x>>31) ^ (z>>31) -> (b)式
||a=0|a!=0|
|:-:|:-:|:-:|
|**b=0**|沒事|不可能|
|**b!0**|找出這種|不可能|
```clike
int addOK(int x, int y)
{
int z = x + y;
return !(!(x >> 31 ^ y >> 31) & !!(x >> 31 ^ z >> 31));
}
```
### allEvenBits (op:9/12)
#### 所有偶數位元是否都是 1。
對折、對折、再對折...直到剩下兩個 bits 。
```clike
int allEvenBits(int x)
{
x &= (x >> 16);
x &= (x >> 8);
x &= (x >> 4);
x &= (x >> 2);
return (x & 0x1);
}
```
### allOddBits (op:10/12)
#### 所有奇數位元是否都是 1。
跟 allEvenBits 一樣想法。
```clike
int allOddBits(int x)
{
x &= (x >> 16);
x &= (x >> 8);
x &= (x >> 4);
x &= (x >> 2);
return (x & 0x2)>>1;
}
```
### anyEvenBit (op:9/12)
#### 偶數位元是否有 1。
```clike=1
int anyEvenBit(int x)
{
x |= (x >> 16);
x |= (x >> 8);
x |= (x >> 4);
x |= (x >> 2);
return (x & 0x1);
}
```
### anyOddBit (op:10/12)
#### 奇數位元是否有 1。
```clike=1
int anyOddBit(int x)
{
x |= (x >> 16);
x |= (x >> 8);
x |= (x >> 4);
x |= (x >> 2);
return ((x & 0x2) >> 1);
}
```
### Bang (op:12/12)
#### 計算 `!x` 但不能用 `!` 。
沒什麼特別的，跟上面一樣，把全部的 bit 都集中到最右一位。
```clike=1
int bang(int x)
{
x |= (x >> 16);
x |= (x >> 8);
x |= (x >> 4);
x |= (x >> 2);
x |= (x >> 1);
return (~x & 0x1);
}
```
:::warning
作業開頭有寫說運算子的數目限制非常寬鬆，用到滿應該是非常爛的寫法，有時間再回頭想想。
:::
### bitAnd (op:4/8)
#### 只用 `~` 與 `|` 實作 logical and。
一張圖解釋
- 紫色為 X ，綠色為 Y
- 紫色以外是 ~X
- 綠色以外是 ~Y
- ~X 與 ~Y 聯集就是只差中間交集那塊
```clike
int bitAnd(int x, int y)
{
return ~(~x | ~y);
}
```
### bitCount
還在想
### bitMask
還在想
### bitMatch (op:8/14)
就是 XOR 運算再取其補數。
- `~(x & y)` 等同不是兩邊都是 1 的部分
- `~(~x & ~y)` 等同不是兩邊都是 0 的部分
```clike
int bitMatch(int x, int y)
{
return ~(~(x & y) & ~(~x & ~y));
}
```
### bitNor (op:3/8)
兩者都沒有的位元，非常直覺。
```clike
int bitNor(int x, int y)
{
return (~x & ~y);
}
```
### bitOr (op:4/8)
`bitNor` 反過來就好。
```clike
int bitOr(int x, int y)
{
return ~(~x & ~y);
}
```
### bitParity (op:11/20)
重點在下面的關係，跟 XOR 的行為一樣。
||odd|even|
|:-:|:-:|:-:|
|odd|even|odd|
|even|odd|even|
然後不斷兩兩消除。
$$
b_0 \oplus b_1 \oplus b_2 ... \oplus b_{31} \\
= (b_0 \oplus b_1) \oplus (b_2 \oplus b_3) ... \oplus (b_{30} \oplus b_{31}) \\
$$
:::info
這樣可以說 XOR 運算有結合律嗎?
:::
```clike
int bitParity(int x)
{
x ^= x >> 1;
x ^= x >> 2;
x ^= x >> 4; // shift the bit to the rightest bit of each byte
x ^= x >> 8; // shift to even bytes.
x ^= x >> 16;
return (x & 0x1);
}
```
### bitReverse (op:53/45)
好不容易想到，但超用運算子。
想法是先每個 byte 各自反轉，再逐個 byte 反過來塞到另一個整數內。
```graphviz
digraph byte{
node[shape=record]
splines=false
by [label="<0>0|<1>1|<2>0|<3>1|<4>1|<5>1|<6>0|<7>0"]
re [label="<0>0|<1>0|<2>1|<3>1|<4>1|<5>0|<6>1|<7>0"]
by:1 -> re:6
by:2 -> re:5
by:5 -> re:2
by:6 -> re:1
}
```
仔細觀察，發現只有在兩者不同時，才需要互換。而且互換一定是 0 變 1 或著 1 變 0(也就是 toggle )。依照這個發現，我們改以下列方式來處理 byte 內的反轉。
```graphviz
digraph byte{
node[shape=record]
by [label="<0>0|<1>1|<2>0|<3>1|<4>1|<5>1|<6>0|<7>0"]
filter [label="<0>0|<1>1|<2>1|<3>0|<4>0|<5>1|<6>1|<7>0"]
re [label="<0>0|<1>0|<2>1|<3>1|<4>1|<5>0|<6>1|<7>0"]
by -> filter [label="XOR",color="white"]
filter -> re
}
```
先創造一個 filter ，這個 filter 會告訴我們每一個 bit 是否要 toggle ，因此程式的流程如下。
- #5~#27 創造這個 filter 。
- #29 由本來的數對這個 filter 做 XOR 運算，會得到每個 byte 順序不變，但 byte 內的 bit 已反轉。
- #30~#39 逐個 byte 反過來塞到一個新的整數內。
```clike=1
int bitReverse(int x)
{
int filter07, filter16, filter25, filter34, y, tempfilter;
tempfilter = 0x1;
tempfilter |= tempfilter << 8;
tempfilter |= tempfilter << 16;
filter07 = (x ^ (x >> 7)) & tempfilter;
filter07 |= filter07 << 7;
tempfilter = 0x2;
tempfilter |= tempfilter << 8;
tempfilter |= tempfilter << 16;
filter16 = (x ^ (x >> 5)) & tempfilter;
filter16 |= filter16 << 5;
tempfilter = 0x4;
tempfilter |= tempfilter << 8;
tempfilter |= tempfilter << 16;
filter25 = (x ^ (x >> 3)) & tempfilter;
filter25 |= filter25 << 3;
tempfilter = 0x8;
tempfilter |= tempfilter << 8;
tempfilter |= tempfilter << 16;
filter34 = (x ^ (x >> 1)) & tempfilter;
filter34 |= filter34 << 1;
x ^= (filter07 | filter16 | filter25 | filter34);
y = x & 0xff;
y <<= 8;
x >>= 8;
y |= x & 0xff;
y <<= 8;
x >>= 8;
y |= x & 0xff;
y <<= 8;
x >>= 8;
y |= x & 0xff;
return y;
}
```
### bitXor (op:7/14)
與 `bitMatch` 類似。
```clike
int bitXor(int x, int y)
{
return ~(x & y) & ~(~x & ~y);
}
```
### byteSwap (op:28/25)
想了整整一天，然後還超用 operator 。
- #5~#12 ，首先我要保證 `n<=m` ，令 `diff=m-n` ，若為負數表示要交換。
- #14~#16 這裡，把要交換的兩個 byte 清成 `00000000` 。
- #18~#20 將原來的 x 向左/向右移動 `diff` bytes 後，補回 `y` 。
```clike=1
int byteSwap(int x, int n, int m)
{
int diff, swap, filterN, filterM, y;
m <<= 3;
n <<= 3;
diff = m + ~n + 1;
swap = diff >> 31;
m ^= (n & swap);
n ^= (m & swap);
m ^= (n & swap);
filterN = (0xff << n);
filterM = (0xff << m);
y = x & ~filterN & ~filterM;
diff = (diff ^ swap) + ~swap + 1;
y |= ((x >> diff) & filterN);
y |= ((x << diff) & filterM);
return y;
}
```
### conditional (op:9/16)
- 令 `diff = z-y`
- 令 `con = !x` ，為的是使其只有可能是 `0` 或 `1` ，進而利用 `~x+1` 來產生 `0x00000000` 或 `0xffffffff` 。再用 diff 做 bitwise AND 運算就能控制是否加上兩值的差。
```clike=1
int conditional(int x, int y, int z)
{
int diff = z + ~y + 1, con = !x;
diff = diff & (((~con) + 1) >> 31);
return y + diff;
}
```
### countLeadingZero
還在想
### copyLSB (op:3/5)
很簡單，取其最右位元，若是 1 轉為 -1；否則轉為 0 。
```clike
int copyLSB(int x)
{
return (~(x & 0x1)) + 1;
}
```
### distinctNegation (op:5/5)
若 `x==-x` ，表示 x^(-x) 會等於 `0`。(每個位元都一樣)
```clike
int distinctNegation(int x)
{
return !!(x ^ (~x + 1));
}
```
### dividePower2 (op:10/15)
本來以為這不就 `x>>n` ?看來是我太天真了...負的會有問題。後來仔細想想，**正數除法**與**負數除法**方向不同。
先從正數開始看，比較單純。以 8 bit 整數 (-128~127) 做為例子。
以下是 13/4 與 -13/4 的結果。
- 正數的部分是直接右移兩個 bit ，讓最右兩位元直接不見，沒有問題。如果先減去餘數再算的話，結果一樣。而餘數就是 x & ($2^2-1$) 。
- 而負數的部分，反而是要加一個數，使得 0~n-1 bits 都為 0，再做右移運算。==這個數是多少不重要，反正會讓第 n 個 bit 變成 1 。==
```graphviz
digraph posi{
node[shape=record]
13 [label="13",shape=plaintext]
3 [label="3",shape=plaintext]
-13 [label="-13",shape=plaintext]
-3 [label="-3",shape=plaintext]
thirteen [label="<ptr>0|0|0|0|1|1|0|1"]
three [label="<ptr>0|0|0|0|0|0|1|1"]
negthirteen [label="<ptr>1|1|1|1|0|0|1|1"]
negthree [label="<ptr>1|1|1|1|1|1|0|1"]
13 -> thirteen:ptr:w
-13 -> negthirteen:ptr:w
3 -> three:ptr:w
-3 -> negthree:ptr:w
}
```
還不知道如何用更好的模型去解釋這件事，目前都只是歸納、觀察的結果。
```clike=1
int dividePower2(int x, int n)
{
int Neg = x >> 31, filter = (0x1 << n) + (~0), Mod;
Mod = filter & x;
x >>= n;
x += ((!!Mod) & Neg);
return x;
}
```
### evenBits (op:4/8)
很直覺，把設好一個 byte 再擴展到 32 bits.
```clike
int evenBits(void)
{
int filter = 0x55;
filter |= filter << 8;
filter |= filter << 16;
return filter;
}
```
### ezThreeFourths (op:9/12)
有了 `dividePower2` 就很簡單了，注意順序。
- #5~#6 先乘以 3 然候看有沒有 overflow/underflow。
- 再跟 `dividePower2` 的做法一樣。
```clike=1
int ezThreeFourths(int x)
{
int Neg, filter = 0x3, Mod;
x += (x << 1);
Neg = x >> 31;
Mod = filter & x;
x >>= 2;
x += ((!!Mod) & Neg);
return x;
}
```
### fitsBits (op:6/15)
#### 判斷 n 位元，是否可以表示 x 。
想了一晚，後來發現很簡單。
- 若 `x` 為正，右移 `n-1` bit 必為 `0`。
- 反之，右移 `n-1` bit 必為 `-1` 。
```clike=1
int fitsBits(int x, int n)
{
int Neg = x >> 31;
n += (~0);
x >>= n;
return !(x ^ Neg);
}
```
### fitsShort (op:4/8)
#### `x` 是否可用 16 bit 表示
直接拿 `fitsBits` 改就好。
```clike
int fitsShort(int x)
{
int Neg = x >> 31;
x >>= 15;
return !(x ^ Neg);
}
```
---
## 浮點數部分
### floatAbsVal (op:7/10)
#### 求絕對值，但如果是 `NaN` 直接回傳 `uf`
直接把 sign bit 改為 `0`，然後判斷是否為 `NaN`。`NaN` 的條件為
- Exponent == `0xff`
- Fraction != `0`
```clike
unsigned floatAbsVal(unsigned uf)
{
int Exp, Man;
Exp = (uf >> 23) & 0xff;
Man = uf << 9;
if (Exp == 0xff && Man)
return (uf);
uf <<= 1;
uf >>= 1;
return uf;
}
```
### floatFloat2Int (op:21/30)
#### 浮點數轉 32 bit 有號整數，若超過可表示範圍則回傳 `0x80000000`。
先拆成三部分，各自處理
- Sign
- Exponent：這部分本來就要先減去 `127` 才是真正的值，但我們再減去 `23` ，直接假設 fraction 的部分已經先左移 `23` 個 bit 了。
- Fraction：這個部分是只有小數點，預設是要加上 `1` 才是真正的值。先把 `1` 加回去，方便等下做位移。
先接著判斷這個值是否小於 `1` 或大/小於 32 bit 有號整數的最大/最小值。如果在範圍內，直接做 shift operation ，然後看其 `sign` 決定是否變號。這裡有一個 trick 是在這個整數為負最小值的時候($-2^{31}$)，左移會讓正數 overflow 之後乘 `-1` ，會再 underflow 一次，又變回我們期望的值。
```clike=1
int floatFloat2Int(unsigned uf)
{
int Sign, Exp, Man;
Sign = (uf >> 31) & 0x1;
Exp = ((uf >> 23) & 0xff) - (127 + 23);
Man = ((uf << 9) >> 9) | 0x00800000;
if (Exp < -23)
return (0);
if ((Sign && Exp > 8) || (!Sign && Exp > 7))
return (0x80000000);
if (Exp >= 0)
Man <<= Exp;
else
Man >>= (-Exp);
if (Sign)
Man *= -1;
return Man;
}
```
### floatInt2Float (op:44/30)
#### 32 bit 整數轉單精度浮點數
想了快兩天，才發現自己忽略了==精度==與==捨入==的問題，難怪一直出錯。現階段還超用了很多運算子，再努力修改。
- 精度的部分，在單精度的浮點數下，fraction 的部分是 23 個 bit 。乍看之下好像很多，但卻無法容納完整的 32 bit 整數，我們用一個非常簡單的程式，就可以觀察的這個現象。
```clike
for (int i = 0x1 << 24; i < (0x1 << 24) + 10; i++) {
float f = i;
printf("%f\tinteger=%d\thex=%x\n", f, i, i);
}
```
輸出如下
:::success
16777216.000000 integer=16777216 hex=1000000
16777216.000000 integer=16777217 hex=1000001
16777218.000000 integer=16777218 hex=1000002
16777220.000000 integer=16777219 hex=1000003
16777220.000000 integer=16777220 hex=1000004
16777220.000000 integer=16777221 hex=1000005
16777222.000000 integer=16777222 hex=1000006
16777224.000000 integer=16777223 hex=1000007
16777224.000000 integer=16777224 hex=1000008
16777224.000000 integer=16777225 hex=1000009
:::
當需要的位數超過 24 個 bit 的時候，連整數都沒辦法正確表示了。(因為浮點數預設整數部分為 1 ，所以如果這個整數需要超過 `23+1` 位才能表示時就會不精準。)
這個例子中的整數要 25 bit 才能表示，也就是最低位正好無法顯示，這時候就需要捨入，從輸出看得出來，捨入的規則不是單純的捨棄最低位，否則應該每個數字都會出現兩次，顯然 `16777218.000000` 只有出現一次。
:::warning
我以前都直接用 double ，fraction 的部分有 52 個 bit ，不會連 32 bit 的整數都沒辦法正確表示，老實說看到這個結果我真的驚呆了...
:::
- 捨入的規則只有一句話，==捨入到最近的那個有效數字，一樣近的時候捨入至最低有效位為 `0`。== 如果我們以 8 bit 要捨入剩 6 bit 為例，如下。
```graphviz
digraph{
node[shape=record]
lowest [label="最低有效位",shape=plaintext]
byte [label="0|1|1|0|1|<ptr> 0|1|1"]
byteup [label="0|1|1|0|1|<ptr> 1|0|0"]
bytedown [label="0|1|1|0|1|<ptr> 0|0|0"]
lowest -> byte:ptr
byte:ptr -> byteup:ptr [label="向上捨入"]
byte:ptr -> bytedown:ptr [label="向下捨入"]
}
```
這個例子之中，會向上捨入，因為向上捨入的**距離**較短，只差 `1` ，而向下捨入差 `3`。
```graphviz
digraph{
node[shape=record]
lowest [label="最低有效位",shape=plaintext]
byte [label="0|1|1|0|1|<ptr> 0|1|0"]
byteup [label="0|1|1|0|1|<ptr> 1|0|0"]
bytedown [label="0|1|1|0|1|<ptr> 0|0|0"]
lowest -> byte:ptr
byte:ptr -> byteup:ptr [label="向上捨入"]
byte:ptr -> bytedown:ptr [label="向下捨入"]
}
```
第二個例子中，距離向上與向下捨入都是 `2`，這時候就會選擇使最低有效位為 `0` 的方向捨入，因此會向下捨入。
完整程式碼如下
```clike=1
unsigned floatInt2Float(int x)
{
int Sign, Exp = 31, Man = (0x1 << 31), Rem, pos = 8;
unsigned filter = 0xffffff00;
if (!x)
return (0);
Sign = x & 0x80000000;
if (Sign)
x *= -1;
while (!(x & Man)) {
pos--;
Man >>= 1;
filter >>= 1;
}
Rem = x & ~(filter | Man);
if (pos > 0) {
if (Rem > 0 && (0x1 << pos) - Rem < Rem)
x += (1 << pos);
if ((0x1 << pos) - Rem == Rem && ((x >> pos) & 0x1) == 1)
x += (1 << pos);
}
Man = 0x1 << 31;
while (!(x & Man)) {
Exp--;
Man >>= 1;
}
if (Exp > 23)
Man = x >> (Exp - 23);
else
Man = x << (23 - Exp);
Man &= 0x007fffff;
Exp += 127;
Exp <<= 23;
return Sign | Exp | Man;
}
```
### floatIsEqual (op:16/25)
#### 判斷兩浮點數是否相等
- `+0` 與 `-0` 是相等
- 若其中一個是 `NaN` 則回傳 `0`
```clike=1
int floatIsEqual(unsigned uf, unsigned ug)
{
int Exp, frac;
if (!((uf << 1) | (ug << 1)))
return (1);
Exp = (uf >> 23) & 0xff;
frac = uf & 0x007fffff;
if (Exp == 0xff && frac)
return (0);
Exp = (ug >> 23) & 0xff;
frac = ug & 0x007fffff;
if (Exp == 0xff && frac)
return (0);
return (!(uf ^ ug));
}
```
### floatIsLess (op:27/30)
#### 判斷浮點數 `uf` 是否 < 浮點數 `ug`
- 若 sign 不同可以直接知道結果。
- 若 sign 同，但 exponent 不同，因為浮點數預設整數位為 `1` ，所以直接比較也可以知道結果，但要注意根據 sign 的不同，有不一樣的結果。
- 若連 exponent 也相同，就直接比較 fraction ，一樣注意 sign 不同有不同結果。
```clike=1
int floatIsLess(unsigned uf, unsigned ug)
{
int signf, signg, expf, expg, fracf, fracg;
if (!((uf << 1) | (ug << 1)))
return (0);
signf = (uf >> 31) & 0x1;
signg = (ug >> 31) & 0x1;
expf = (uf >> 23) & 0xff;
expg = (ug >> 23) & 0xff;
fracf = uf & 0x007fffff;
fracg = ug & 0x007fffff;
if ((expf == 0xff && fracf) || (expg == 0xff && fracg))
return (0);
if (signf > signg)
return (1);
if (signf < signg)
return (0);
if (expf > expg)
return (signf);
if (expf < expg)
return (!signf);
if (fracf < fracg)
return (!signf);
if (fracf > fracg)
return (signf);
return (0);
}
```
### floatNegate (op:6/10)
#### 改變正負號
判斷是否為 `NaN` ，如果不是直接 toggle `sign` 。
```clike=1
unsigned floatNegate(unsigned uf)
{
int exp, frac;
exp = (uf >> 23) & 0xff;
frac = uf & 0x007fffff;
if (exp == 0xff && frac)
return (uf);
return uf ^ 0x80000000;
}
```
### floatPower2 (op:4/30)
#### 回傳 $2^x$
奇怪這麼簡單怎給那麼多運算子...
直接照定義來做，只要改 exponent 部分就好，注意 non-normalized 與 special 的部分即可。
```clike=1
unsigned floatPower2(int x)
{
x += 127;
if (x >= 0xff)
return (0x7f800000);
if (x <= 0)
return (0);
return x << 23;
}
```
### floatScale1d2 (op:19/30)
#### 回傳 `0.5*f`
浮點數在 Normalized 與 Non-normalized 的時候，在 fraction 的部分對應到的 mantissa 是不一樣的。
- Normalized 的浮點數，mantissa 的部分是 fraction 再加上 `1` ，預設整數位已經是 `1` 了。若除以 `2` 後的值還在 normalized 的範圍內的時候，只要把 exponent 的部分減 `1` 即可。
- Non-normalized 的浮點數，mantissa 的部分不需要加上 `1` ， fraction 直接代表真正的 mantissa 。若除以 `2` 之前與之後，都在 non-normalized 的範圍內的時候，直接把 fraction 的部分做位元右移運算，並注意捨入即可。
- 如果除以 `2` 之前是 normalized 但除之後是 non-normalized ，這時候要注意把 `0x00400000` 這個 bit 加上去，因為兩者在 fraction 對應到的 mantissa 不一樣。
```clike=1
unsigned floatScale1d2(unsigned uf)
{
int sign, exp, frac, rem;
sign = uf & 0x80000000;
exp = (uf >> 23) & 0xff;
frac = uf & 0x007fffff;
if (!(uf << 1))
return (uf);
if (exp == 0xff)
return (uf);
if (exp > 1)
exp--;
else {
rem = frac & 0x1;
frac >>= 1;
frac += (frac & rem);
if (exp == 1) {
exp--;
frac |= 0x00400000;
}
}
return sign | (exp << 23) | frac;
}
```
### floatScale2 (op:18/30)
#### 計算 `2*f`
比較單純，不會有捨入的問題。
- Normalized 的情況下只要 exp+1 就好。
- Non-normalized 看 fraction 最高有效位是 1 的話再把 `exp`+1，其餘只要做位元左移運算就好。
```clike=1
unsigned floatScale2(unsigned uf)
{
int sign, exp, frac;
sign = uf & 0x80000000;
exp = (uf >> 23) & 0xff;
frac = uf & 0x007fffff;
if (!(uf << 1))
return (uf);
if (exp == 0xff)
return (uf);
if (exp > 0)
exp++;
else {
if (((frac >> 22) & 0x1) == 0x1) {
exp++;
}
frac <<= 1;
frac &= 0x007fffff;
}
return sign | (exp << 23) | frac;
}
```
### floatScale64 (op:24/35)
#### 計算 `64*f`
- 與 floatScale2 不同的是要注意到會產生 `Inf` 或 `-Inf` 的狀況，除此之外加個迴圈就好。
```clike=1
unsigned floatScale64(unsigned uf)
{
int sign, exp, frac;
unsigned count = 0x1 << 5;
sign = uf & 0x80000000;
exp = (uf >> 23) & 0xff;
frac = uf & 0x007fffff;
if (!(uf << 1))
return (uf);
if (exp == 0xff && frac)
return (uf);
if (exp >= (0xff - 6))
return (0x7f800000 | sign);
while (count) {
if (exp > 0)
exp++;
else {
if (((frac >> 22) & 0x1) == 0x1) {
exp++;
}
frac <<= 1;
frac &= 0x007fffff;
}
count >>= 1;
}
return sign | (exp << 23) | frac;
}
```
### floatUnsigned2Float (op:42/30)
#### 無號整數轉成浮點數
直接拿前面的 `floatInt2Float` 改就好，把判斷正負的部分直接砍掉就可以了。
```clike=1
unsigned floatUnsigned2Float(unsigned u)
{
int Exp = 31, Man = (0x1 << 31), Rem, pos = 8;
unsigned filter = 0xffffff00;
if (!u)
return (0);
while (!(u & Man)) {
pos--;
Man >>= 1;
filter >>= 1;
}
Rem = u & ~(filter | Man);
if (pos > 0) {
if (Rem > 0 && (0x1 << pos) - Rem < Rem)
u += (1 << pos);
if ((0x1 << pos) - Rem == Rem && ((u >> pos) & 0x1) == 1)
u += (1 << pos);
}
Man = 0x1 << 31;
while (!(u & Man)) {
Exp--;
Man >>= 1;
}
if (Exp > 23)
Man = u >> (Exp - 23);
else
Man = u << (23 - Exp);
Man &= 0x007fffff;
Exp += 127;
Exp <<= 23;
return Exp | Man;
}
```
## 整數第二部分
### getByte (op:3/6)
#### 取出第 n 個 byte 的內容
```clike
int getByte(int x, int n)
{
return (x >> (n << 3)) & 0xff;
}
```
### greatestBitPos (op:15/70)
#### 找出最左邊的 `1`
想了很久，後來看了 `ofAlpaca` 同學的共筆，才知道怎麼做。還以為題目給 70 個運算子會很複雜，結果很單純。
```clike
int greatestBitPos(int x)
{
int y, filter = ~(0x1 << 31);
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
y = (x >> 1) & filter;
return x ^ y;
}
```
### implicatoin (op:2/5)
#### 若 x 成立 y 必成立； x 不成立，y 有可能成立。
有一個簡單的例子，假設 x 代表下雨， y 代表天空有雲。
- 若下雨，天空必有雲。
- 若沒下雨，天空還是可能有雲。
||沒雨|有雨|
|:-:|:-:|:-:|
|沒雲|O|X|
|有雲|O|O|
很明顯這是 OR 運算。在沒雨 (`x==0`) 的時候一定是 true ，有雨的時候看有沒有雲 (`y==1`) 來決定。
```clike
int implication(int x, int y)
{
return (!x) | y;
}
```
### isAsciiDigit (op:14/15)
#### 判斷是否為 0x30 <= x <= 0x39
兩個條件
- 是否只用到最低 6 bit
- 設其上下界， x 分別減`上/下`界必為`負/正`數。
```clike
int isAsciiDigit(int x)
{
int low = 0x30, high = 0x3a, legal;
legal = !((~(0x3f)) & x);
x = ((x + (~low + 1)) >> 31) ^ ((x + (~high + 1)) >> 31);
x &= 0x1;
return (x & legal);
}
```
### isEqual (op:2/5)
#### 判斷兩數是否相等
若相等做 XOR 運算必為 0 。
```clike
int isEqual(int x, int y)
{
return !(x ^ y);
}
```
`isNotEqual` 與此類似，不再贅述。
### isGreater (op:18/24)
#### 回傳是否 `x>y`
- 先判斷是否異號，，在 x>0 且 y<0 的情況下一定成立； x<0 且 y>0 時一定不成立。
- 同號時
- `!!dis` : 距離是否不為 0
- `~diff` : 異號
- `(dis>>31)+1` : 距離為正
```clike=1
int isGreater(int x, int y)
{
int dis = x + ~y + 1, negx = x >> 31, negy = y >> 31, diff;
diff = negx ^ negy;
dis = (!!dis) & (~diff) & ((dis >> 31) + 1) & 0x1;
diff = (diff & ~negx) & 0x1;
return dis | diff;
}
```
`isLess` 直接把 `x` 與 `y` 反過來就好。
`isLessOrEqual` 再把 `isLess` 中判斷距離不為 0 的部分拿掉就好。
### isNegative (op:3/6)
#### 是否為負數
直接看最左位元就好。
```clike
int isNegative(int x)
{
return !!(x >> 31);
}
```
`isNonNegative` 一樣，不再贅述。
`isPositive` 也類似，多判斷是否為 0 而已。
### isNonZero (op:4/10)
#### 是否不為 0
只有 0 乘 -1 還是自己。
```clike
int isNonZero(int x)
{
return !!(~x + 1);
}
```
`isZero` 與此類似，不再贅述。
### isTmax (op:5/10)
#### 是否為整數最大值。
直接變出整數最大，用一樣的直做 XOR 為 0 的特性去檢驗即可。
```clike=1
int isTmax(int x)
{
int y = 0x1 << 30;
y <<= 1;
y -= 1;
return !(x ^ y);
}
```
`isTmin` 類似，不再贅述。
### leastBitPos (op:4/6)
#### 找出最右位的 1
假設某一個整數的二進位表示為 `...1000` ，此數 -1 後會變成 `...0111` ，在最右邊的 1 左邊的部分，完全不會變。
因此 `x^(x-1)` ，會變成 `00..001111` ，最右邊的 1 以左全是 0 。再把這個當作 filter 與原有的 `x` 做 AND 就可以得到答案。
```clike
int leastBitPos(int x)
{
int filter = x ^ (x + ~0);
return (x & filter);
}
```
### logicalNeg (op:8/12)
#### 不用 `!` 實作 `!`
把 x 轉成負的，然後取最左一位。只有 0 還是會取到 0 。
```clike
int logicalNeg(int x)
{
int neg = x >> 31;
x = (x ^ (~neg)) + (neg + 1);
return (~(x >> 31)) & 0x1;
}
```
Sign in with Wallet
Connect another wallet