# 2018q3 Homework5 (bits)
contributed by < `plusline` >
### 環境設定
```
plusline@plusline-System-Product-Name:~/plusline/datalab$ make
gcc -O0 -g -Wall -Werror -m32 -lm -o btest bits.c btest.c decl.c tests.c
/usr/lib/gcc/i686-linux-gnu/7/../../../../i686-linux-gnu/bin/ld: /usr/lib/gcc/i686-linux-gnu/7/liblto_plugin.so: error loading plugin: /usr/lib/gcc/i686-linux-gnu/7/liblto_plugin.so: wrong ELF class: ELFCLASS32
collect2: error: ld returned 1 exit status
Makefile:13: recipe for target 'btest' failed
make: *** [btest] Error 1
```
正在尋找原因...似乎是與 64-bit 和 32-bit 有關，已經安裝
```
$ sudo apt update
$ sudo apt install libc6-dev:i386 gcc:i386
```
仍然出現問題
solution:[HowTo Compile a 32-bit Application Using gcc On the 64-bit Linux Version](https://www.cyberciti.biz/tips/compile-32bit-application-using-gcc-64-bit-linux.html)
測試
```
plusline@plusline-System-Product-Name:~/plusline/datalab$ make
```
```
Total points: 0/228
```
:::info
注意上面的訊息提到不相容的 LTO gcc plugin，可找手冊來關閉 plugin，再來測試
:notes: jserv
:::
:::info
根據上面的作法已經解決問題了，但還是想問老師說的手冊是什麼？是指 man gcc 嗎？
by plusline
:::
> man 就是 manual 的簡稱，手冊是也 :notes: jserv
> 可是有一萬五千多行... by plusline
### 修改 bits.c
#### absVal
```c
int absVal(int x)
{
int y = x >> 31;
return (y ^ x) - y;
}
```
不能用`-`所以改成
```c
int absVal(int x)
{
int y = x >> 31;
return (y ^ x) + (~y+1);
}
```
如果沒有先拿出來考過真很難想到不用 if 怎麼寫。
拿到四分，不過無法 commit 上去， error 的提示讓人覺得很奇怪，不是只要 shift 小於等於31就有定義嗎？
```
plusline@plusline-System-Product-Name:~/plusline/datalab$ git commit -a -m 'Complete absVal'
[bits.c:114]: (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
Fail to pass static analysis.
```
> 注意有號數的使用，應善用 `<stdint.h>`
> [name="jserv"]
:::info
分成兩次 shift 就能取消 error ，剩下的錯誤都發生在 test.c 我應該去改嗎？
:::
> 改吧，順便提交 pull request
> [name="jserv"]
#### addOK
正數加上正數應該產生正數，負數加上負數應該產生負數。本來想和硬體一樣用最後兩個位元做互斥或，只是不知道怎得到進位。。
```c
int addOK(int x, int y)
{
int sum = x + y;
int same = (~(x ^ y)) & (sum ^ x);
return ((~same) >> (32 - 1)) & 1;
}
```
#### allEvenBits
把長條的 bits 想像成棉被，對折對折再對折。
```c
int allEvenBits(int x)
{
x=x&(x>>2);
x=x&(x>>4);
x=x&(x>>8);
x=x&(x>>16);
x=x&1;
return x;
}
```
#### allOddBits
作法和 allEvenBits 差不多，只是最後要看的是最小第二位。
```c
int allOddBits(int x)
{
x = x & (x >> 2);
x = x & (x >> 4);
x = x & (x >> 8);
x = x & (x >> 16);
x = x >> 1;
x = x & 1;
return x;
}
```
#### anyEvenBit
```c
int anyEvenBit(int x)
{
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
x = x & 1;
return x;
}
```
#### anyOddBit
```c
int anyOddBit(int x)
{
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
x = x >> 1;
x = x & 1;
return x;
}
```
#### bang
```c
int bang(int x)
{
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
x = ~x & 1;
return x;
}
```
#### bitAnd
用笛摩根定理
```c
int bitAnd(int x, int y)
{
return ~((~x) | (~y));
}
```
#### bitCount
版本一
很明顯超過40個運算子，正在思考如何簡化。
目前的方式是畫真值表，再做成半加器的形式。
```c
//*****
int bitCount(int x)
{
int A=x;
int B=x>>1;
int S=A^B;//count even number
int C=A&B;//count even number and shift left one bit
//*****
A=S;
B=S>>2;
int S1_1=A^B;
int C1_1=A&B;//shift one
A=C;
B=C>>2;
int S1_2=A^B;//shift one
int C1_2=A&B;//shift two
//*****
A=S1_1;
B=S1_1>>4;
int S2_1=A^B;//zero
int C2_1=A&B;//one
A=C1_1;
B=C1_1>>4;
int S2_2=A^B;//one
int C2_2=A&B;//two
A=S1_2;
B=S1_2>>4;
int S2_3=A^B;//one
int C2_3=A&B;//two
A=C1_2;
B=C1_2>>4;
int S2_4=A^B;//two
int C2_4=A&B;//three
//*****
int h=1+(1<<8)+(1<<16)+(1<<24);
int a1=S2_1&h;
int a2=C2_1&h;
int a3=S2_2&h;
int a4=C2_2&h;
int a5=S2_3&h;
int a6=C2_3&h;
int a7=S2_4&h;
int a8=C2_4&h;
int sum=a1+(a2<<1)+(a3<<1)+(a4<<2)+(a5<<1)+(a6<<2)+(a7<<2)+(a8<<3);
int ans=sum+(sum>>8);
ans=ans+(ans>>16);
ans=ans&((1<<6)+(~1+1));
return ans;
}
```
版本二
已經少用很多運算子了，但還是多了9個，相較上一版本，少做一層半加的動作。
```c
int bitCount(int x)
{
int A = x;
int B = x >> 1;
int S = A ^ B; // count even number
int C = A & B; // count even number and shift left one bit
//*****
A = S;
B = S >> 2;
int S1_1 = A ^ B;
int C1_1 = A & B; // shift one
A = C;
B = C >> 2;
int S1_2 = A ^ B; // shift one
int C1_2 = A & B; // shift two
//*****
int h = 15 + (15 << 8) + (15 << 16) + (15 << 24);
int hh=1+(1<<4)+(1<<8)+(1<<12)+(1<<16)+(1<<20)+(1<<24)+(1<<28);
int aa1=S1_1&hh;
int aa2=C1_1&hh;
int aa3=S1_2&hh;
int aa4=C1_2&hh;
int Sum=aa1+(aa2<<1)+(aa3<<1)+(aa4<<2);
Sum=Sum+(Sum>>4);
Sum=Sum&h;
Sum=Sum+(Sum>>8);
Sum = Sum + (Sum >> 16);
Sum = Sum & ((1 << 6) + (~1 + 1));
return Sum;
}
```
版本三
成功將運算子壓到39個，相較上一版本，化簡 mask 。
```c
int bitCount(int x)
{
int A = x;
int B = x >> 1;
int S = A ^ B; // count even number
int C = A & B; // count even number and shift left one bit
//*****
A = S;
B = S >> 2;
int S1_1 = A ^ B;
int C1_1 = A & B; // shift one
A = C;
B = C >> 2;
int S1_2 = A ^ B; // shift one
int C1_2 = A & B; // shift two
//*****
int d=15+(15<<16);
int dd=d+(d<<8);
int k=1+(1<<16);
int kk=k+(k<<8);
int kkk=kk+(kk<<4);
int aa1 = S1_1 & kkk;
int aa2 = C1_1 & kkk;
int aa3 = S1_2 & kkk;
int aa4 = C1_2 & kkk;
int Sum = aa1 + (aa2 << 1) + (aa3 << 1) + (aa4 << 2);
Sum = Sum + (Sum >> 4);
Sum = Sum & dd;
Sum = Sum + (Sum >> 8);
Sum = Sum + (Sum >> 16);
Sum = Sum & ((31<<1)+1);
return Sum;
}
```
#### bitMask
分別將低於 highbit 的位元設為1，低於 lowbit 設為1，再取交集。
```c
int bitMask(int highbit, int lowbit)
{
int h = (~1 + 1) << 1;
h = h << highbit;
h = ~h;
int l = 1 << (lowbit);
l = l + (~1 + 1);
int mask = h & ~l;
return mask;
}
```
#### bitMatch
提示讀半天，原來是要做 equal 或是 NXOR 。
```c
int bitMatch(int x, int y)
{
return (x&y)|(~x&~y);
}
```
#### bitNor
用笛摩根定理
```c
int bitNor(int x, int y)
{
return (~x)&(~y);
}
```
#### bitOr
上一題加 not 。
```c
int bitOr(int x, int y)
{
return ~((~x)&(~y));
}
```
#### bitParity
第一個禮拜的題目，相信大家都把答案背下來了 XD 。
```c
int bitParity(int x)
{
int sum=x^(x>>1);
sum=sum^(sum>>2);
sum=sum^(sum>>4);
sum=sum^(sum>>8);
sum=sum^(sum>>16);
sum=sum&1;
return sum;
}
```
#### bitReverse
相鄰交換，隔一個，隔兩個，隔四個，隔八個，隔十六個交換，順序沒差。
```c
int bitReverse(int x)
{
int h1 = (1 << 16) + (~1 + 1); // 0x0000ffff
int h2 = (h1 >> 8); // 0x00ff00ff
h2 = h2 + (h2 << 16);
int h3 = (h2 >> 4) & h2; // 0x0f0f0f0f
h3 = h3 + (h3 << 8);
int h4 = (h3 >> 2) & h3; // 0x33333333
h4 = h4 + (h4 << 4);
int h5 = (h4 >> 1) & h4; // 0x55555555
h5 = h5 + (h5 << 2);
x = ((x >> 1) & h5) | ((x & h5) << 1);
x = ((x >> 2) & h4) | ((x & h4) << 2);
x = ((x >> 4) & h3) | ((x & h3) << 4);
x = ((x >> 8) & h2) | ((x & h2) << 8);
x = ((x >> 16) & h1) | ((x & h1) << 16);
return x;
}
```
#### bitXor
畫真值表
| ｘ | ｙ | return |
| -------- | -------- | -------- |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
```c
int bitXor(int x, int y)
{
return (~x & y) | (x & ~y);
}
```
#### byteSwap
取出要交換的部份，直接交換。
```c
int byteSwap(int x, int n, int m)
{
int mask = 15;
mask = mask + (mask << 4);
int shift_n = n << 3;
int shift_m = m << 3;
int mask_n = mask << shift_n;
int mask_m = mask << shift_m;
int get_n = mask_n & x;
int get_m = mask_m & x;
int change_n = ((get_n >> shift_n) & mask) << shift_m;
int change_m = ((get_m >> shift_m) & mask) << shift_n;
int ans = (x & ~mask_n & ~mask_m) | change_n | change_m;
return ans;
}
```
#### conditional
用 shannon expansion 。
```c
int conditional(int x, int y, int z)
{
int i = x | (x << 1);
i = i | (i << 2);
i = i | (i << 4);
i = i | (i << 8);
i = i | (i << 16);
i = i >> 30 >> 1;
return (i & y) | (~i & z);
}
```
#### countLeadingZero
把所有一右邊的位元全部補成一，再數有幾個零。
```c
int countLeadingZero(int x)
{
int i = x;
i = i | (i >> 16);
i = i | (i >> 8);
i = i | (i >> 4);
i = i | (i >> 2);
i = i | (i >> 1);
i = ~i;
//加上bitCount
}
```
#### copyLSB
將最小位移到符號位，在利用 sign extension 將所有位補成符號位的數
```c
int copyLSB(int x)
{
return x << 30 << 1 >> 30 >> 1;
}
```
#### distinctNegation
考慮0和0x80000000就可以了。
```
int distinctNegation(int x)
{
int k = x << 1;
return !!(k);
}
```
#### dividePower2
這題要 round to zero 負數要加， CSAPP 只有在浮點數稍微提一下，公式是喂狗來的， `bias=(1<<n)-1`，是目前看到唯一可以移除掉分之的作法。想破頭居然才兩分。
```c
int dividePower2(int x, int n)
{
int y = x >> 30 >> 1;
return (x + (((1 << n) + (~1 + 1)) & y)) >> n;
}
```
##### evenBits
```c
int evenBits(void)
{
int i=5;
i=i|(i<<16);
i=i|(i<<8);
i=i|(i<<4);
return i;
}
```
#### ezThreeFourths
注意正負的判斷是判斷做完乘法後，已經溢位的數，如果溢位成負數就用負數做。
```c
int ezThreeFourths(int x)
{
int i=x+(x<<1);
int y=i>>30>>1;
i=(i+(3&y))>>2;
return i;
}
```
#### fitsBits
利用 sign extension 。
```c
int fitsBits(int x, int n)
{
int i = x << (32 - n);
i = i >> (32 - n);
i = i ^ x;
return !i;
}
```
#### fitsShort
減號可以刪掉，不過為了對應上一題，就寫這樣了。
```c
int fitsShort(int x)
{
int n = 16;
int i = x << (32 - n);
i = i >> (32 - n);
i = i ^ x;
return !i;
}
```
#### floatAbsVal
注意NaN的格式 `x11111111XXXXXXXXXXXXXXXXXXXXXXX`，但 X 不能全為0。
```c
unsigned floatAbsVal(unsigned uf)
{
int temp = uf << 1;
temp = temp >> 24;
temp = ~temp;
int cond = uf << 9;
if ((!temp) && (cond))
return uf;
unsigned i = 1 << 30 << 1;
i = ~i;
i = uf & i;
return i;
}
```
要進入浮點數的題目了........
Total points: 61/228 估計接近一百題
Sign in with Wallet
Connect another wallet