# 2018q3 Homework5 (bits)
###### tags: `sysprog2018`
Contributed by <[`aben20807`](https://github.com/aben20807)>
## 環境設定
+ 安裝問題
```bash
$ uname -a
Linux ben-UX410UQK 4.15.0-23-generic #25-Ubuntu SMP Wed May 23 18:02:16 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ sudo apt install libc6-dev:i386 gcc:i386
Reading package lists... Done
Building dependency tree
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:
The following packages have unmet dependencies:
gcc:i386 : Depends: cpp:i386 (>= 4:7.3.0-3ubuntu2.1) but it is not going to be installed
Depends: gcc-7:i386 (>= 7.3.0-27~) but it is not going to be installed
E: Unable to correct problems, you have held broken packages.
```
+ 解決：把相依性檔案一併安裝
```bash
$ sudo apt install libc6-dev:i386 gcc:i386 cpp:i386 gcc-7:i386 binutils:i386
```
+ 無法 `make`
```bash
$ make check
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
```
+ 發現 `g++` 消失，所以再裝一次
```bash
$ sudo apt install g++
```
+ 安裝後就可以了 (雖然說可以，不過好像流程是錯的，近期裝的 gcc 4.9 也消失)
```bash
Total points: 0/228
```
+ 事情還沒結束，今天(10/26)上課考試前開機發現變成命令模式了@@
+ 以 `$ startx` 進入 GUI 介面後想說考完試再來處理
+ 課後利用以下指令修復，開機後能正常進入 GUI 介面 [[Ref]](https://askubuntu.com/a/1066064)
```bash
$ sudo apt update && sudo apt upgrade --fix-missing
$ sudo apt install --reinstall ubuntu-session gdm3
```
## 開發記錄
### 觀察每個 bits 的函數 (week3 / review)
```c
void print_bits(size_t const size, void const *const ptr)
{
unsigned char *b = (unsigned char*) ptr;
for (int i = size - 1; i >= 0; i--){
for (int j = 7; j >= 0; j--){
printf("%u", (b[i] >> j) & 1);
}
}
puts("");
}
// Usage:
// int x = ~0 & (0x28 << 14);
// print_bits(sizeof(x), &x); // 00000000000010100000000000000000
```
### 不能 commit
+ cppcheck 會把 32 位有號數最大可以 shift 的寬度限定為 31
```bash
$ git commit
[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
```
+ 解決：把需要 shift 31 bits 的變數使用 `unsigned` cast，常數則加上後綴 `U`，就不需要分兩次 shift 了，(已送 [PR](https://github.com/sysprog21/datalab/pull/2))
+ 關於一些 UB 的例子請參考 http://blog.robertelder.org/signed-or-unsigned/
```c
- int bit = (x >> i) & 0x1;
+ int bit = ((unsigned) x >> i) & 0x1;
- int mask = 1 << i;
+ int mask = 1U << i;
```
### specialBits
+ 因為有人先問我這題所以我就先做了
+ 利用一開始預先做一補數就可以少一個運算子
+ 中間有一個 byte 是 `0x28` 先做一補數得 `0xd7`
+ 移到適當位置再做一次一補數即可
```c
int specialBits(void)
{
// 0xffca3fff = 0b11111111110010100011111111111111
// 0xd7 << 14 = 0b00000000001101011100000000000000
return ~(0xd7 << 14);
}
```
### absVal
+ 兩種情況：
+ $x \lt 0$：`x >> 31` 為 `0x111...1`，跟 `x` 作 XOR 會得到 `x` 的一補數，而 `~0x111...1 + 1` 為 `1`，所以就回傳 `x` 的二補數
+ $x \ge 0$：`x >> 31` 為 `0`，跟 `x` 作 XOR 不變，而 `~0 + 1` 為 `0`，所以就回傳 `x` 的值
```c
int absVal(int x)
{
return (x ^ (x >> 31)) + ((x >> 31) & 1);
}
```
+ 但是這樣跟 `tests.c` 一樣不能 commit，而且這裡無法使用 unsigned 解決
+ 我去查規格書時並沒有提及有號整數右移會有什麼 UB 發生，只有對負數右移時是 implementation-defined §6.5.7/5，可能就是因為這個所以 cppcheck 會發出警告，但卻不是所有負數的右移都警告，這點我覺得相當奇怪
+ 題目假定我們的機器是 `Performs right shifts arithmetically.` 但這是 C 語言規格書中不被保證的 (見上一點)
+ 題目禁止事項中有提到 `6. Use any form of casting.`, `7. Use any data type other than int.`，暫時沒有不用 `unsigned` 又能夠直接右移 31 bits 的方式，所以我就擅自使用 `unsigned` 及假定把 `int` 的值給 `unsigned` 的變數不算 cast 了，算 **implicit conversion**
> if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.
> --- C99 6.3.1.3/2
+ ==注意，以下對整數操作的函式中可能有使用 `unsigned` 這並不合原始規定==
+ 可以使用分段 shift 來替換 `(x >> 30) >> 1`，但我就使用無號整數來維持可讀性，以下為互相轉換的例子 (只要是 `int` shift 31 bits 就無法通過 cppcheck)
```c
void func(int x)
{
// int y = x >> 31; // (x >> 30) >> 1
// 使用 unsigned 得到 y (sign extension) 的方法
unsigned sig = x;
sig = sig >> 31;
int y = ~0 + !sig;
}
```
```c
void func(int x)
{
unsigned sig = x;
sig = sig >> 31;
// 使用 int 得到 sig 的方法
// int sig = (x >> 31) & 0x1;
}
```
+ 用 `unsigned` 做 sign extension
```c
int sign_ext(int x, int n)
{
// return x >> n;
unsigned u = x;
unsigned sign_mask = ~((~0u) >> n) & (~0u + !(u >> 31));
return (u >> n) | sign_mask;
}
```
+ 以下就是能夠通過 cppcheck 的方法 (第一題就花了我頗久@@)
```c
int absVal(int x)
{
unsigned sig = x;
sig = sig >> 31;
return (x ^ (~0 + !sig)) + sig;
}
```
### addOK
+ 同樣利用把 `int` 的值給 `unsigned` 變數後透過右移得到 sign bit
+ 加法溢位有兩種可能：正 + 正 = 負，負 + 負 = 正，所以透過 `x`, `y` 及 `x + y` 的 sign bit 去判斷是否溢位
```c
int addOK(int x, int y)
{
unsigned x_sig = x;
x_sig = x_sig >> 31;
unsigned y_sig = y;
y_sig = y_sig >> 31;
unsigned z_sig = x + y;
z_sig = z_sig >> 31;
return !((x_sig & y_sig & !z_sig) | (!x_sig & !y_sig & z_sig));
}
```
### allEvenBits
### allOddBits
### anyEvenBit
### anyOddBit
+ 這4個蠻像的就一起寫
+ 都是利用右移把 bit 的資訊壓縮
```c
int allEvenBits(int x)
{
x = x & (x >> 16);
x = x & (x >> 8);
x = x & (x >> 4);
x = x & (x >> 2);
return x & 0x1;
}
int allOddBits(int x)
{
x = x >> 1;
x = x & (x >> 16);
x = x & (x >> 8);
x = x & (x >> 4);
x = x & (x >> 2);
return x & 0x1;
}
int anyEvenBit(int x)
{
x = x | (x >> 16);
x = x | (x >> 8);
x = x | (x >> 4);
x = x | (x >> 2);
return x & 0x1;
}
int anyOddBit(int x)
{
x = x >> 1;
x = x | (x >> 16);
x = x | (x >> 8);
x = x | (x >> 4);
x = x | (x >> 2);
return x & 0x1;
}
```
+ 經過 `evenBits()` 後發現可以使用 mask 來實作
```c
int allEvenBits(int x)
{
int mask = 0x55 | (0x55 << 8);
mask = mask | (mask << 16);
return !((x & mask) ^ mask);
// 與 mask 做 AND 後再和 mask 做 XOR 確認是否等於
}
int allOddBits(int x)
{
int mask = 0xaa | (0xaa << 8);
mask = mask | (mask << 16);
return !((x & mask) ^ mask);
}
int anyEvenBit(int x)
{
int mask = 0x55 | (0x55 << 8);
mask = mask | (mask << 16);
return !!(x & mask);
// 與 mask 做 AND 後若不為 0 代表存在任一 even bit 為 1
}
int anyOddBit(int x)
{
int mask = 0xaa | (0xaa << 8);
mask = mask | (mask << 16);
return !!(x & mask);
}
```
### bang
+ 觀察後發現，只有對 `0` 取二補數後其 sign bit 都是 `0` (TMin 及其二補數的 sign bit 都是 `1`)
+ 因為不能用 `!` 所以再用一次 `~` 讓 sign bit 的 `0`, `1` 對調，如此就只有 `0` 使得兩個數的 sign bit 經過 and 後為 `1`
```c
int bang(int x)
{
unsigned u1 = ~x;
unsigned u2 = ~(~x + 1);
return ((u1 >> 31) & (u2 >> 31));
}
```
### bitAnd
+ 利用笛摩根定律 (De Morgan's laws) $\neg (\neg p \vee \neg q) \equiv (p \wedge q)$
```c
int bitAnd(int x, int y)
{
return ~(~x | ~y);
}
```
### bitMask
```c
int bitMask(int highbit, int lowbit)
{
// 0b000...000111111 h_mask for highbit
// 0b111...111111000 l_mask for lowbit
// &) 0b000...000111000 bitMask(5, 3)
int h_mask = ~((~0 << highbit) << 1);
int l_mask = ~0 << lowbit;
return h_mask & l_mask;
}
```
### bitMatch
+ 剛看解釋還有些不懂，其實是做 XNOR，也就是 bit 相同設 `1`，不同設 `0`
+ 可以先做 XOR 再做 NOT 不過 XOR 不能用
+ 邏輯上用 `(x & y) | (~x & ~y)` 不過也不能用 OR，所以再度請出笛摩根
```c
int bitMatch(int x, int y)
{
// ~(x ^ y)
// (x & y) | (~x & ~y)
return ~(~(x & y) & ~(~x & ~y));
}
```
### bitXor
+ 與 bitMatch 差一個 `~`
```c
int bitXor(int x, int y)
{
// ~((x & y) | (~x & ~y))
return ~(x & y) & ~(~x & ~y);
}
```
### bitNor
```c
int bitNor(int x, int y)
{
return ~x & ~y;
}
```
### bitOr
+ 與 bitNor 差一個 `~`
```c
int bitOr(int x, int y)
{
return ~(~x & ~y);
}
```
### bitParity
+ 已經看過頗多次，不能建立表格
```c
int bitParity(int x)
{
x = x ^ (x >> 16);
x = x ^ (x >> 8);
x = x ^ (x >> 4);
x = x ^ (x >> 2);
x = x ^ (x >> 1);
return x & 0x1;
}
```
### byteSwap
+ 每個 byte 有 8 bits，所以 `n`, `m` 要先乘以 `8`，利用左移 `3` 來達到
+ 分別產生 n, m 的 mask
+ 接著利用 mask 取出對應位置的 byte 後再移到 swap 後的位置
+ e.g. `0x12345678` 的 `1`, `3` byte 要互換
+ `0x00005600` 右移 1 byte 再左移 3 byte 得 `0x56000000`
+ `0x12000000` 右移 3 byte 再左移 1 byte 得 `0x00001200`
+ 最後清空 `x` 原本的第 n, m byte 再利用 OR 把對應的 bits 附上 e.g.
+ `0x1234"56"78` -> `0x1234"00"78` -> `0x1234"12"78`
+ `0x"12"341278` -> `0x"00"341278` -> `0x"56"341278`
```c
int byteSwap(int x, int n, int m)
{
n = n << 3;
m = m << 3;
int n_mask = (0xff << n);
int m_mask = (0xff << m);
int n_byte = (((x & n_mask) >> n) & 0xff) << m;
int m_byte = (((x & m_mask) >> m) & 0xff) << n;
x = (x & ~n_mask) | m_byte;
x = (x & ~m_mask) | n_byte;
return x;
}
```
### conditional
+ 原本想到是先把所有 bits 壓縮到最右邊就可以知道是 `0` 還是非 `0`，所以寫出以下版本，共用了 19 個運算子，超出要求
```c
int conditional(int x, int y, int z)
{
x = x | (x >> 16);
x = x | (x >> 8);
x = x | (x >> 4);
x = x | (x >> 2);
x = x | (x >> 1);
x = x & 0x1;
return ((~0 + !x) & y) + ((~0 + x) & z);
}
```
+ 突然可以用 `!` 來檢測是否為 `0`，瞬間精簡許多
```c
int conditional(int x, int y, int z)
{
int true_mask = ~0 + !x;
return (true_mask & y) + ((~true_mask) & z);
}
```
### countLeadingZero
+ 已經先用 binary search 產生 branch free 的 clz 了，運算子數超量所以優化中
+ 大致流程：
+ 把 `x` 所有 bits 反向，數前綴有幾個 `1`
+ 利用與 mask 做 `&` 後再 `^` 判斷是否等於 mask，若等於就代表需要更長的 mask
+ 判斷前方的 `1` 長度是否大於 16，是則增加 mask 長度為 16 + 8，否則減少 16 - 8，依此類推
+ 最後加上 `!~x` 是因為當 `x` 為 `0 (0b000...0`) 時 的時候是有 32 個
```c
int countLeadingZero(int x)
{
x = ~x;
int lsh = 16;
int mask = ~0 << lsh;
int f1 = !((x & mask) ^ mask);
lsh = lsh + ((8 ^ (~0 + !f1)) + f1);
mask = ~0 << lsh;
int f2 = !((x & mask) ^ mask);
lsh = lsh + ((4 ^ (~0 + !f2)) + f2);
mask = ~0 << lsh;
int f3 = !((x & mask) ^ mask);
lsh = lsh + ((2 ^ (~0 + !f3)) + f3);
mask = ~0 << lsh;
int f4 = !((x & mask) ^ mask);
lsh = lsh + ((1 ^ (~0 + !f4)) + f4);
mask = ~0 << lsh;
int f5 = !((x & mask) ^ mask);
// return 31 - lsh + f5 + !~x;
return 32 + (~lsh) + f5 + !~x;
}
```
+ siahuat0727 建議可以不用先做 `~`，`0` 與 mask 的 `1` 做 `&` 會為 `0`
+ 改完變成 49 個，剛好在 50 以內
```c
int countLeadingZero(int x)
{
int mask_len = 16;
int mask = ~0 << mask_len;
int f1 = !(x & mask);
mask_len = mask_len + ((8 ^ (~0 + !f1)) + f1);
mask = ~0 << mask_len;
int f2 = !(x & mask);
mask_len = mask_len + ((4 ^ (~0 + !f2)) + f2);
mask = ~0 << mask_len;
int f3 = !(x & mask);
mask_len = mask_len + ((2 ^ (~0 + !f3)) + f3);
mask = ~0 << mask_len;
int f4 = !(x & mask);
mask_len = mask_len + ((1 ^ (~0 + !f4)) + f4);
mask = ~0 << mask_len;
int f5 = !(x & mask);
return 32 + (~mask_len) + f5 + !x;
}
```
+ 因為 `~0` 太常用了所以宣告一個變數來減少運算子使用：41 個
```c
int countLeadingZero(int x)
{
int allf = ~0;
int mask_len = 16;
int mask = allf << mask_len;
int f1 = !(x & mask);
mask_len = mask_len + ((8 ^ (allf + !f1)) + f1);
mask = allf << mask_len;
int f2 = !(x & mask);
mask_len = mask_len + ((4 ^ (allf + !f2)) + f2);
mask = allf << mask_len;
int f3 = !(x & mask);
mask_len = mask_len + ((2 ^ (allf + !f3)) + f3);
mask = allf << mask_len;
int f4 = !(x & mask);
mask_len = mask_len + ((1 ^ (allf + !f4)) + f4);
mask = allf << mask_len;
int f5 = !(x & mask);
return 32 + (~mask_len) + f5 + !x;
}
```
### copyLSB
+ 最右 bit 為 `1` 則把 `0xffffffff + 0 = -1` 回傳
+ 最右 bit 為 `0` 則把 `0xffffffff + 1 = 0` 回傳
```c
int copyLSB(int x)
{
return ~0 + !(x & 0x1);
}
```
### distinctNegation
+ 跟二補數做 XOR 若相同則結果為 `0`, 其他則透過兩次 NOT 將值變成 `1`
+ 又發現所求 `x != -x` 可以變成 `x + x != 0`
```c
int distinctNegation(int x)
{
// !!(x ^ (~x + 1))
return !!(x + x);
}
```
### dividePower2
> Compute x/(2^n), for 0 <= n <= 30. Round toward zero.
+ 重點是後面那句"向 0 捨入"
+ 以題目為例說明
+ `dividePower2(15, 1) = 7`，${15 \over 2^1} = 7.5$，7.5 向 0 捨入為 `7`
+ `dividePower2(-33, 4) = -2`，${-33 \over 2^4} = -2.0625$，-2.0625 向 0 捨入為 `-2`
+ 對正數直接右移的話就可以直接為答案，但是負數的結果並非向 0 捨入，`-33 >> 4` 結果為 `-3`
+ 根據 CSAPP P72~P74 的討論，負數必須加上一個偏移量，其最後給出一個公式：
$\underset{round\ toward\ zero}{x \over 2^k} =
\begin{cases}
x >> k &\text x \ge 0 \\
x + ((1 << k) - 1) >> k &\text x \lt 0
\end{cases}$
```c
(x < 0 ? (x + (1 << k) - 1 : x) >> k
```
+ 想說改成沒有其他運算子的版本如下，但是不行！原因是最後 `>> n` 需要 sign extension 的幫助，而我因為使用 `unsigned` 所以整個運算都是使用無號，因此最後的右移一定是補 `0`
```c
int dividePower2(int x, int n)
{
unsigned sig = x;
sig = sig >> 31;
return (x + (sig << n) - sig) >> n;
}
```
+ 既然已經知道是最後一個 shift 的問題就透過先把值存在 `x` 裡再右移吧，雖然遇到負數也是 implementation-defined 不過並不是直接寫 31 所以可以通過 cppcheck
```c
int dividePower2(int x, int n)
{
unsigned sig = x;
sig = sig >> 31;
x = x + (sig << n) - sig;
return x >> n;
}
```
### evenBits
+ 似曾相識，跟 `allEvevBits()` 很像，但可用的運算子數更少
+ 發現可用 `0x55 (0b01010101)` 做 mask
+ 這樣那系列的也可以用更少的運算子數了
```c
int evenBits(void)
{
int x = 0x55 | (0x55 << 8);
return x | (x << 16);
}
```
### fitsBits
+ `x` 可否用 `n` bits 的二補數系統存放
+ 發現只有兩種情況可行：
+ 右移 `n - 1` bits 後剩下的全為 `0` (正數)：`0b000...0[0xxx]`
+ 右移 `n - 1` bits 後剩下的全為 `1` (負數)：`0b111...1[1xxx]`
```c
int fitsBits(int x, int n)
{
x = x >> (n + ~0);
// return !(x ^ 0) | !(x ^ ~0);
return !(x) | !(x + 1);
}
```
### fitsShort
+ `fitsBits()` 的簡化版
```c
int fitsShort(int x)
{
x = x >> 15;
return !x | !(x + 1);
}
```
### getByte
+ `byteSwap()` 的退化版
```c
int getByte(int x, int n)
{
return (x >> (n << 3)) & 0xff;
}
```
### implication
+ 四種情況：
+ T -> T: T
+ T -> F: F
+ F -> T: T
+ F -> F: T
+ $X \rightarrow Y \equiv \neg X \vee Y$
```c
int implication(int x, int y)
{
return (!x) | y;
}
```
### isAsciiDigit
+ 判斷 `x - 0x30` 和 `0x39 - x` 是否都大於等於 `0`
+ 要檢查 sign bit 所以又請出 `unsigned`
```c
int isAsciiDigit(int x)
{
unsigned ge0 = x;
ge0 = !((ge0 + ~0x30 + 1) >> 31);
unsigned le9 = x;
le9 = !((~le9 + 1 + 0x39) >> 31);
return ge0 & le9;
}
```
### isEqual
+ 前面有使用過，同樣的數做 XNOR 會得 1
```c
int isEqual(int x, int y)
{
return !(x ^ y);
}
```
### isGreater
+ 原本以為可以用 `isAsciiDigit()` 的技巧，結果不行，因為會 overflow
+ `!!(x ^ y)` 是要避免 x, y 相等
```c
int isGreater(int x, int y)
{
unsigned sig = x + ~y + 1;
return !!(x ^ y) & !(sig >> 31);
}
```
+ 修改成如下
+ `x` $\ge$ 0 且 `y` $\lt$ 0 時必大於
+ `x`, `y` 同號 (`x`, `y` sign bit 相同) 時，`x - y` $\gt$ 0 (`x - y - 1` 的 sign bit 為 0) 時大於
```c
int isGreater(int x, int y)
{
unsigned sig_x = x;
sig_x = sig_x >> 31;
unsigned sig_y = y;
sig_y = sig_y >> 31;
int xpyn = (!sig_x) & sig_y;
unsigned sig_z = x + ~y; // x - y - 1
sig_z = sig_z >> 31;
return (xpyn | ((!(sig_x ^ sig_y)) & (!sig_z)));
}
```
### isLess
+ 把 `isGreater()` 的 `x`, `y` 互換即可
```c
int isLess(int x, int y)
{
unsigned sig_x = x;
sig_x = sig_x >> 31;
unsigned sig_y = y;
sig_y = sig_y >> 31;
int xnyp = (!sig_y) & sig_x;
unsigned sig_z = y + ~x; // y - x - 1
sig_z = sig_z >> 31;
return (xnyp | ((!(sig_y ^ sig_x)) & (!sig_z)));
}
```
### isLessOrEqual
+ 在 `isLess()` 的回傳值再和 `(!(x ^ y))` 做 OR 讓相等時回傳 1
```c
int isLessOrEqual(int x, int y)
{
unsigned sig_x = x;
sig_x = sig_x >> 31;
unsigned sig_y = y;
sig_y = sig_y >> 31;
int xnyp = (!sig_y) & sig_x;
unsigned sig_z = y + ~x; // y - x - 1
sig_z = sig_z >> 31;
return (!(x ^ y)) | (xnyp | ((!(sig_y ^ sig_x)) & (!sig_z)));
}
```
### isNegative
+ 取 sign bit
```c
int isNegative(int x)
{
unsigned sig = x;
sig = sig >> 31;
return sig;
}
```
### isNonNegative
+ `isNegative()` 加 NOT
```c
int isNonNegative(int x)
{
unsigned sig = x;
sig = sig >> 31;
return !sig;
}
```
### isNonZero
+ 與 `bang()` 差一個 NOT，不能用 `!`，所以使用 De Morgan's laws
```c
int isNonZero(int x)
{
unsigned u1 = x;
unsigned u2 = ~x + 1;
return ((u1 >> 31) | (u2 >> 31));
}
```
### isNotEqual
+ 與 `isEqual()` 差一個 NOT
```c
int isNotEqual(int x, int y)
{
return !!(x ^ y);
}
```
### isPositive
+ 利用 `!!x` 來去掉 `x` 為 0 的情況
```c
int isPositive(int x)
{
unsigned sig = x;
sig = sig >> 31;
return (!!x) & (!sig);
}
```
### isTmax
```c
int isTmax(int x)
{
unsigned tmax = 0x1;
tmax = ~(tmax << 31);
return !(x ^ tmax);
}
```
+ 發現不能用 shift
+ `Tmax + 1` 後做一補數會是自己 `~(0b0111...11 + 0b000...01)` 為 `0b0111...1`
+ 但要注意同樣加 1 並 `~` 後會是自己的還有 `-1(0b111...1)`，所以把 `-1` 排除掉
```c
int isTmax(int x)
{
return !(x ^ ~(x + 0x1)) & !!~x;
}
```
### isTmin
```c
int isTmin(int x)
{
unsigned tmin = 0x1;
tmin = tmin << 31;
return !(x ^ tmin);
}
```
+ 同樣不能 shift
+ `Tmin - 1` 後做一補數會是自己 `~(0b1000...00 - 0b000...01)` 為 `0b1000...0`
+ 但要注意同樣減 1 後 `~` 為自己的還有 `0(0b000...0)`，所以排除 `0`
```c
int isTmin(int x)
{
return !(x ^ ~(x + ~0)) & !!x;
}
```
### isZero
+ 這應該不需要解釋
```c
int isZero(int x)
{
return !x;
}
```
### leastBitPos
+ `x - 1` 會把右邊的 `0` 都變成 `1` 直到遇到一個 `1` 並且把它變成 `0`
+ `0b1010...01[100000] - 1 = 0b1010...01[011111]`
+ `~(x - 1)` 就會得到右邊 `10...0` 與原本的 `x` 相同，其他位與 `x` 相反，此時再透過 `&` 取得所求
+ `~0b1010...01[011111] = 0b0101...01[100000]`
```c
int leastBitPos(int x)
{
return x & (~(x + ~0));
}
```
### leftBitCount
+ 與 `countLeadingZero()` 差在一個數 `1` 一個數 `0`
+ 所以在一開始先 `x = ~x;`，這樣就把題目轉成 `countLeadingZero()`
```c
int leftBitCount(int x)
{
x = ~x;
int allf = ~0;
int mask_len = 16;
int mask = allf << mask_len;
int f1 = !(x & mask);
mask_len = mask_len + ((8 ^ (allf + !f1)) + f1);
mask = allf << mask_len;
int f2 = !(x & mask);
mask_len = mask_len + ((4 ^ (allf + !f2)) + f2);
mask = allf << mask_len;
int f3 = !(x & mask);
mask_len = mask_len + ((2 ^ (allf + !f3)) + f3);
mask = allf << mask_len;
int f4 = !(x & mask);
mask_len = mask_len + ((1 ^ (allf + !f4)) + f4);
mask = allf << mask_len;
int f5 = !(x & mask);
return 32 + (~mask_len) + f5 + !x;
}
```
### logicalNeg
+ 跟 `bang()` 一模一樣的功能
```c
int logicalNeg(int x)
{
unsigned u1 = ~x;
unsigned u2 = ~(~x + 1);
return ((u1 >> 31) & (u2 >> 31));
}
```
### logicalShift
+ 先產生高位 n 個 `0` 的 mask
```c
int logicalShift(int x, int n)
{
int mask = ~(~0 << (32 + ~n) << 1);
return (x >> n) & mask;
}
```
### maximumOfTwo
+ 參考 `isGreater()`
```c
int maximumOfTwo(int x, int y)
{
unsigned sig_x = x;
sig_x = sig_x >> 31;
unsigned sig_y = y;
sig_y = sig_y >> 31;
int xpyn = (!sig_x) & sig_y;
unsigned sig_z = x + ~y; // x - y - 1
sig_z = sig_z >> 31;
int xgty_mask = ~0 + !(xpyn | ((!(sig_x ^ sig_y)) & (!sig_z)));
return (xgty_mask & x) + (~xgty_mask & y);
}
```
### minimumOfTwo
+ 參考 `isLess()`
```c
int minimumOfTwo(int x, int y)
{
unsigned sig_x = x;
sig_x = sig_x >> 31;
unsigned sig_y = y;
sig_y = sig_y >> 31;
int xnyp = (!sig_y) & sig_x;
unsigned sig_z = y + ~x; // y - x - 1
sig_z = sig_z >> 31;
int xlty_mask = ~0 + !(xnyp | ((!(sig_x ^ sig_y)) & (!sig_z)));
return (xlty_mask & x) + (~xlty_mask & y);
}
```
### minusOne
```c
int minusOne(void)
{
return ~0;
}
```
### negate
+ 二補數技巧
```c
int negate(int x)
{
return ~x + 1;
}
```
### oddBits
```c
int oddBits(void)
{
int x = 0xaa | 0xaa << 8;
return x | x << 16;
}
```
### replaceByte
+ `byteSwap()` 簡化版
```c
int replaceByte(int x, int n, int c)
{
n = n << 3;
c = c << n;
return (x & ~(0xff << n)) | c;
}
```
### sign
+ 觀察負數、0、正數：
||`!!x`|`sing bit`|回傳|
|:-:|:-:|:-:|:-:|
|正數|1|0|`1`|
|0|0|0|`0`|
|負數|1|1|`-1`|
+ 找到符合所求的公式：`!!x - 2 * sign bit`
```c
int sign(int x)
{
unsigned sig = x;
sig = sig >> 31;
return !!x + ~(sig << 1) + 1;
}
```
### signMag2TwosComp
+ 此處左移 31 有使用 `1u`，因為使用 `1` cppcheck 會報錯
```c
int signMag2TwosComp(int x)
{
unsigned sig = x;
sig = sig >> 31;
int mask = ~(1u << 31);
return ((x & mask) ^ (~0 + !sig)) + sig;
}
```
### subtractionOK
+ 參考 `addOK()`
+ 減法溢位有兩種可能：正 - 負 = 負，負 - 正 = 正，所以透過 x, y 及 x - y 的 sign bit 去判斷是否溢位
```c
int subtractionOK(int x, int y)
{
unsigned x_sig = x;
x_sig = x_sig >> 31;
unsigned y_sig = y;
y_sig = y_sig >> 31;
unsigned z_sig = x + ~y + 1;
z_sig = z_sig >> 31;
return !((x_sig & !y_sig & !z_sig) | ((!x_sig) & y_sig & z_sig));
}
```
### thirdBits
```c
int thirdBits(void)
{
int x = (0x92 << 8) | 0x49;
return x << 15 | x;
}
```
### tmax
```c
int tmax(void)
{
return ~(1u << 31);
}
```
### tmin
```c
int tmin(void)
{
return 1u << 31;
}
```
### twosComp2SignMag
+ 除了最左位的 sign bit，其他的根據 sign bit 決定是否做二補數，`1` 負數要做，`0` 正數不用，最後在最左方加上 sign bit
+ 但又發現一開始不需要排除最左位，因為正數不會做二補數，所以 sign bit 不變；負數做二補數後 sign bit 變成 `0`，這時候再補回 `1` 就好
+ 在過程中發現有**一個值沒有檢查**，就是 `-0(0b1000...0)`，正確值應該要是 `0`，可是回傳值是 `-2147483648`
```c
int twosComp2SignMag(int x)
{
unsigned sig = x;
sig = sig >> 31;
int sig_mask = sig << 31;
// return (((x & ~sig_mask) ^ (~0 + !sig)) + sig) | sig_mask;
return ((x ^ (~0 + !sig)) + sig) | sig_mask;
}
```
+ 要包含 `-0(0b1000...0)` 就需要先排除，並確認 magnitude 的值
```c
int twosComp2SignMag(int x)
{
unsigned sig = x;
sig = sig >> 31;
int sig_mask = sig << 31;
int magnitude = x & ~sig_mask;
return ((magnitude ^ (~0 + !sig)) + sig) | (sig_mask << !magnitude);
}
```
+ 後來想想，發現只有 `-0` 會讓一開始的 sign bit 為 1，二補數後也為 1，所以使用 `^` 解決即可
```c
int twosComp2SignMag(int x)
{
unsigned sig = x;
sig = sig >> 31;
int sig_mask = sig << 31;
return ((x ^ (~0 + !sig)) + sig) ^ sig_mask;
}
```
### upperBits
+ 這題是我在寫 datalab 一直有需求的功能，就是產生 n 個 1 右邊皆為 0 (相反也一樣，用 `~` 即可)
+ 在 `logicalShift()` 中有使用 `~0 << (32 + ~n) << 1` 產生 `0b111...1000...0` 但 n 最大就只能到 31，而這題需要支援 0~32，只用 `~0 << (33 + ~n)` 會在 n 為 32 時發生 UB，以我的情況來說就是大於等於 32 的就直接不 shift，所以當輸入的 `n` 為 0 時 `~0 << (33 + ~n)` 就等於 `~0`，因此利用這點，加上一個 `!n` 讓 n 為 0 時自動加 1，這樣可以通過測試，但是利用 UB 非常不好
```c
int upperBits(int n)
{
return (~0 << (33 + ~n)) + !n;
}
```
+ 改良如下，使用一個 mask，當 n 為 0 時會使得 mask 為全 0，其他情況會全 1，這樣當左方發生 UB 時會強制被全 0 的 mask 清空
```c
int upperBits(int n)
{
int is_zero_mask = ~0 + !n;
return (~0 << (33 + ~n)) & is_zero_mask;
}
```
## 開發環境
```
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
Stepping: 9
CPU MHz: 700.082
CPU max MHz: 3500.0000
CPU min MHz: 400.0000
BogoMIPS: 5808.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 4096K
NUMA node0 CPU(s): 0-3
```
Sign in with Wallet
Connect another wallet