# 2018q3 Homework5 (bits)
contributed by < `type59ty` >
##### tags:`hw5`,`bits`
---
## 實驗環境
```c
Linux version 4.15.0-36-generic (buildd@lgw01-amd64-031)
Description: Ubuntu 18.04.1 LTS
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz x 12
GPU : GeForce GTX 1080 Ti x 2
memory: 32G
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 12288K
gcc version: 7.3.0
```
## 預期目標
- 深度學習 [CS:APP](https://hackmd.io/c/S1vGugaDQ) 第 2 章和對應的補充教材
- 跨越理論與實務的鴻溝
- [找出詳解錯誤](https://www.viseator.com/2017/06/18/CS_APP_DataLab/)
## 作業要求
* 自 GitHub 上 fork [datalab](https://github.com/sysprog21/datalab)，依據 [Data Lab: Manipulating Bits](http://csapp.cs.cmu.edu/3e/datalab.pdf)，補完欠缺的程式碼，並且通過自動測試
* 確保儘可能少的指令，可用 `$ gcc -S bits.c` 輸出組合語言並觀察 `bits.s` 的程式碼裡頭的 x86 (IA32) 指令
* 避免用分支 (branch)，設計時間複雜度為 $O(1)$ 的實作
* 選出其中 7 個位元操作的函式，詳細解釋其原理，需要比照 [clz 應用](https://hackmd.io/s/Bk-uxCYxz) 和 [bit-reverse](https://hackmd.io/s/ByzoiggIb) 的分析方式，==舉出真實世界中的應用案例== (最好在 GitHub 找出程式碼)，解說應搭配有效的測試程式碼
* 探討讓 [datalab](https://github.com/sysprog21/datalab) 得以 64-bit friendly 的提案，並舉出實際程式碼修改
## 事前準備
- 詳細閱讀 CMU CS:APP [Data Lab](http://csapp.cs.cmu.edu/3e/datalab.pdf) 要求
- [Bit-wise operations](https://hackmd.io/s/By0MltO_m)
- [bit-field](https://hackmd.io/s/SJ8y82ZYQ)
- [以位元駕馭能量](https://hackmd.io/s/rk2RO0cYX)
- [CS:APP 第 2 章重點提示和練習](https://hackmd.io/s/rJoxSsiuG)
## Coding
- 跟往常一樣，先 fork 到自己的 github 再 clone 下來
- clone 完先 make 一次看看，卻出現錯誤
```c
forest@pop-os:~/datalab$ make btest
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
```
- 查詢後發現需要安裝 gcc-multilib：
```c
forest@pop-os:~/datalab$ sudo apt-get install gcc-multilib
```
- 之後就能正常編譯了
```c
forest@pop-os:~/datalab$ make btest
gcc -O0 -g -Wall -Werror -m32 -lm -o btest bits.c btest.c decl.c tests.c
```
```c
forest@pop-os:~/datalab$ make check
……
...Gives 42[0x2a]. Should be -1[0xffffffff]
ERROR: Test upperBits(0[0x0]) failed...
...Gives 42[0x2a]. Should be 0[0x0]
Total points: 0/228
```
### absVal
**功能**： 絕對值
**想法**： 這題之前考試出過，作業4( assement )裡也詳細探討過了，所以直接附上[連結](https://hackmd.io/s/B1gN1hBoX#%E6%83%B3%E6%B3%95%EF%BC%9A)，差別在於這邊連 `-` 也不能用，所以這邊要對 y 取 2's complement
```c
int absVal(int x)
{
int y = x >> 31;
return (x ^ y) + (~y + 1);
}
```
### addOK
**功能**： 判斷兩數相加是否產生 overflow
**想法**： 兩數 x, y 相加，考慮以下四種狀況
1. 正 + 正
2. 正 + 負
3. 負 + 正
4. 負 + 負
其中 2 跟 3 必不會產生 overflow ， 所以只要判斷 1 跟 4，當相加後的值與 x,y ==異號== 則為 overflow ( i.e 正+正= 負 or 負+負= 正 )
```c
int addOK(int x, int y)
{
int x_s = x >> 31;
int y_s = y >> 31;
int xy_s = (x + y) >> 31;
return (((x_s ^ y_s) & 1) | (~((x_s & y_s) ^ xy_s) & 1));
}
```
### allEvenBits
**功能**： 檢查是否所有偶數位元皆為1
**想法**： 因為只看偶數位元，所以奇數位元都設為0，然後確認是否每個偶數位元都等於1
```c
int allEvenBits(int x)
{
x = x & (x >> 2);
x = x & (x >> 4);
x = x & (x >> 8);
x = x & (x >> 16);
return x & 1;
}
```
### allOddBits
**功能**： 檢查是否所有奇數位元皆為1
**想法**： 跟上一個差不多，只是改成把偶數位元設為0
```c
int allOddBits(int x)
{
x = x & (x >> 2);
x = x & (x >> 4);
x = x & (x >> 8);
x = x & (x >> 16);
x = x >> 1;
return x & 1;
}
```
### anyEvenBit
**功能**： 檢查是否有任何偶數位元為1
**想法**： 一樣先將奇數 bit 設為0，只有偶數 bit 皆為0的狀況，輸出才為0
```c
int anyEvenBit(int x)
{
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
return x & 1;
}
```
### anyOddBit
**功能**： 檢查是否有任何奇數位元為1
**想法**： 觀念同上一個
```c
int anyOddBit(int x)
{
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
x = x >> 1;
return x & 1;
}
```
### bang
**功能**： 不使用 `!` 完成 !x 運算
**想法**： `!` 讓非 0 值都變成 0 ，讓 0 變成 1 ，所以重點是確認這個值是否為 0 ，當一個數反向再 1 ，只有 0 會變回 0
```c
int bang(int x)
{
return (1 & (1 ^ ((x | (~x + 1)) >> 31)));
}
```
### bitAnd
**功能**： 用 `~`和`|`完成 and 運算
**想法**： De Morgan's laws : $x.y$ $=$ $\overline{\overline{x.y}}$ $=$ $\overline{\overline{x}+\overline{y}}$
```c
int bitAnd(int x, int y)
{
return ~((~x) | (~y));
}
```
### bitCount
**功能**： 計算 x 中有幾個 1
**想法**： 運用 divide and conquer 的概念，先將 x 切成 32 塊，相鄰的 bit 兩兩相加，重複這個動作直到所有 bits 都加到一塊，即可得到答案，以 8 bit 為例，我做了一個表格來幫助理解：
假設 `x = abcdefgh` 為一個 8 bit 整數，一開始用 `0x5555` 當 mask 是為了讓相鄰兩個 bit 相加， `x & mask1` 得到 odd bits b,d,f,h ， `(x >> 1) & mask1` 得到 even bits a,c,e,g ，將兩者相加得到 `a+b, c+d, e+f, g+h` ( 圖中省略`+` )，以此類推，最後可以得到 `a+b+c+d+e+f+g+h` ，同理，32 bit 也可以做出來，最後 `& 0x3f` 是因為 ans 最大只有 32
```c
int bitCount(int x)
{
int mask1 = 0x55;
int mask2 = 0x33;
int mask3 = 0x0f;
mask1 |= mask1 << 8;
mask1 |= mask1 << 16;
mask2 |= mask2 << 8;
mask2 |= mask2 << 16;
mask3 |= mask3 << 8;
mask3 |= mask3 << 16;
int ans = (x & mask1) + ((x >> 1) & mask1);
ans = (ans & mask2) + ((ans >> 2) & mask2);
ans = (ans & mask3) + ((ans >> 4) & mask3);
return (ans + (ans >> 8) + (ans >> 16) + (ans >> 24)) & 0x3f;
}
```
### bitMask
**功能**： 介於(包含) highbit 與 lowbit 之間的 bits 設為 1
**想法**： highbit 之下、 lowbit 之上的 bits 設成1，再 and 運算
```c
int bitMask(int highbit, int lowbit)
{
int hi = ~((-1) << highbit << 1);
int lo = ~((1 << lowbit) - 1);
return hi & lo;
}
```
### bitMatch
**功能**： x == y ? 1:0
**想法**： xnor 運算：相同為1，不同為0， De Morgan’s laws
```c
int bitMatch(int x, int y)
{
return ~(~x & y) & ~(x & ~y);
}
```
### bitNor
**功能**： nor 運算
**想法**： De Morgan’s laws
```c
int bitNor(int x, int y)
{
return ~x & ~y;
}
```
### bitOr
**功能**： or 運算
**想法**： De Morgan’s laws
```c
int bitOr(int x, int y)
{
return ~(~x & ~y);
}
```
### bitParity
**功能**： 同位元檢查，奇數個 0(1) 回傳 1，偶數個 0(1) 回傳 0
**想法**： 透過 xor 運算就能得知， e.g
x = 1010 ，則 1 ^ 0 ^ 1 ^ 0 = 0
x = 1011 ，則 1 ^ 0 ^ 1 ^ 1 = 1
所以只要將所有 bits 都 xor 過一次就是答案
```c
int bitParity(int x)
{
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return x & 1;
}
```
### bitReverse
**功能**： reverse the bits
**想法**： 一開始 2bits 之間互換，再來 4bits 之間互換，之後繼續 double 互換區塊的 size ，最後就能得到答案，以 8 bits 為例：
|[a] | [b] |[c]| [d]|[e] |[f]|[g] |[h]|
|-|-|-|-|-|-|-|-|
|[b |a] |[d |c ]|[f| e ]|[h| g]|
|[d |c |b |a ]|[h |g|f |e ]|
|[h |g |f |e |d |c |b |a ]|
```c
int bitReverse(int x)
{
int mask1 = 0x55;
int mask2 = 0x33;
int mask3 = 0x0f;
int mask4 = 0x00ff;
int mask5 = 0xff;
mask1 |= mask1 << 8;
mask1 |= mask1 << 16;
mask2 |= mask2 << 8;
mask2 |= mask2 << 16;
mask3 |= mask3 << 8;
mask3 |= mask3 << 16;
mask4 |= mask4 << 16;
mask5 |= mask5 << 8;
x = ((x >> 1) & mask1) | ((x & mask1) << 1);
x = ((x >> 2) & mask2) | ((x & mask2) << 2);
x = ((x >> 4) & mask3) | ((x & mask3) << 4);
x = ((x >> 8) & mask4) | ((x & mask4) << 8);
x = ((x >> 16) & mask5) | ((x & mask5) << 16);
return x;
}
```
### bitXor
**功能**： xor
**想法**： De Morgan’s laws
$x \oplus y$ $=$ $\overline{x}y + x\overline{y}$ $=$ $\overline{\overline{\overline{x}y} . \overline{x\overline{y}}}$
```c
int bitXor(int x, int y)
{
return ~(~(~x & y) & ~(x & ~y));
}
```
### bitSwap
**功能**： 將指定的 bytes 互換
**想法**： 因為是交換一個 byte ，所以一次位移的量是 8 的倍數，先將要互換的兩個 byte 分別移到最低位元組，將兩數 xor 可以得到一個 mask ，用這個 mask 跟那兩數再作一次 xor 即可得到另外一數， e.g
假設要互換的 byte 為 A、C
則 $xor$ = $A \oplus C$
$xor \oplus A$ = $C$
$xor \oplus C$ = $A$
運用這個原理就能將兩個 bytes 互換，且不影響其他 bytes
```c
int byteSwap(int x, int n, int m)
{
int set1 = (x >> (n << 3)) & 0xff;
int set2 = (x >> (m << 3)) & 0xff;
int xor = (set1 ^ set2);
xor = (xor << (n << 3)) | (xor << (m << 3));
return x ^ xor;
}
```
### conditional
**功能**： x ? y : z
**想法**： 只有當 x = 0 時，x = z，所以只要區分 0 和 非0 的值即可
```c
int conditional(int x, int y, int z)
{
int s = (!!x - 1) & (-1);
return (y & (-1-s)) | (z & (s));
}
```
### countLeadingZero
**功能**： 計算 x 之 leading zero 個數
**想法**：
```c
int countLeadingZero(int x)
{
int mask1 = 0x55;
int mask2 = 0x33;
int mask3 = 0x0f;
mask1 |= mask1 << 8;
mask1 |= mask1 << 16;
mask2 |= mask2 << 8;
mask2 |= mask2 << 16;
mask3 |= mask3 << 8;
mask3 |= mask3 << 16;
x = x | (x >> 16);
x = x | (x >> 8);
x = x | (x >> 4);
x = x | (x >> 2);
x = x | (x >> 1);
// bitCount
int ans = (x & mask1) + ((x >> 1) & mask1);
ans = (ans & mask2) + ((ans >> 2) & mask2);
ans = (ans & mask3) + ((ans >> 4) & mask3);
return 32 - ((ans + (ans >> 8) + (ans >> 16) + (ans >> 24)) & 0x3f);
}
```
### copyLSB
**功能**： 將所有 bits 變成 LSB
**想法**：
```c
int copyLSB(int x)
{
int s = x & 0x1;
return !s - 1;
}
```
### distinctNegation
**功能**： 判斷 x 是否等於 -x
**想法**：
```c
int distinctNegation(int x)
{
x = x << 1;
return !(!x);
}
```
### dividePower2
**功能**： 計算 x / (2^n)
**想法**：
```c
int dividePower2(int x, int n)
{
int s = x >> 30 >> 1;
return (x + (((1 << n) - 1) & s)) >> n;
}
```
### evenBits
**功能**： 所有偶數 bit 設為 1
**想法**：
```c
int evenBits(void)
{
int x = 0x55;
x |= x << 8;
x |= x << 16;
return x;
}
```
### ezThreeFourths
**功能**： x 乘 3/4
**想法**：
```c
int ezThreeFourths(int x)
{
x = x + (x << 1);
return (x + ((x >> 30 >> 1) & 3)) >> 2;
}
```
### fitsBits
**功能**： 判斷 x 能否用 n-bit 2的補數表示
**想法**：
```c
int fitsBits(int x, int n)
{
int mask = 32 + (~n + 1);
return !(x ^ (x << mask >> mask));
}
```
### fitsShort
**功能**： 判斷 x 能否用 16-bit 2的補數表示
**想法**：
```c
int fitsShort(int x)
{
return !(x ^ (x << 16 >> 16));
}
```
### floatAbsVal
**功能**： 取 floating point f 的絕對值
**想法**：
```c
unsigned floatAbsVal(unsigned uf)
{
unsigned ma = uf & 0x007fffff;
unsigned ex = (uf & 0x7f800000);
return (ex == 0x7f800000 && ma) ? uf : (0x7fffffff & uf);
}
```
### floatFloat2Int
**功能**： (int)f
**想法**：
```c
int floatFloat2Int(unsigned uf)
{
unsigned s = (uf & 0x80000000) >> 31;
unsigned ma = (uf & 0x007fffff) | 0x00800000;
int ex = (((uf & 0x7f800000) >> 23) - 127);
unsigned ans;
if (ex < 0)
return 0;
else if (ex > 31)
return 0x80000000u;
if (ex < 23)
ans = ma >> (23 - ex);
else
ans = ma << (ex - 23);
if (s)
return ~ans + 1;
return ans;
}
```
### floatInt2Float
**功能**： (float)x
**想法**：
```c
unsigned floatInt2Float(int x)
{
int s = x&0x80000000;
int exp = -1;
int ma = 0;
if (!x)
return 0;
else if (x==0x80000000)
return 0xcf000000;
if (s) x=~x+1;
//ma = x;
while(x) {
x >>= 2;
exp++;
}
if (exp <= 23) {
ma = x;
exp <<= 23;
}
else {
}
return s | exp | ma;
}
```
### floatIsEqual
**功能**： f==g
**想法**：
```c
int floatIsEqual(unsigned uf, unsigned ug)
{
int mask_us = 0x7fffffff;
int exmask = 0x7f800000;
int isNaN = ((uf & mask_us) > exmask || (ug & mask_us) > exmask);
int zeros = (!((uf & mask_us) || ((ug & mask_us))));
return (!isNaN) && (zeros || (uf == ug));
}
```
### floatIsLess
**功能**： f < g
**想法**：
```c
int floatIsLess(unsigned uf, unsigned ug)
{
int mask_us = 0x7fffffff;
int exmask = 0x7f800000;
int mamask = 0x007fffff;
int uf_s = (uf >> 31) & 1, ug_s = (ug >> 31) & 1;
int uf_ex = (uf >> 23) & 0xff, ug_ex = (ug >> 23) & 0xff;
int uf_ma = (uf & mamask), ug_ma = (ug & mamask);
int isNaN = ((uf & mask_us) > exmask || (ug & mask_us) > exmask);
if (!(uf & mask_us) && !(ug & mask_us))
return 0;
if (isNaN)
return 0;
if (uf_s ^ ug_s)
return uf_s > ug_s;
if (uf_ex ^ ug_ex)
return (uf_ex < ug_ex) ^ uf_s;
if (uf_ma ^ ug_ma)
return (uf_ma < ug_ma) ^ uf_s;
return 0;
}
```
### floatNegate
**功能**： -f
**想法**：
```c
unsigned floatNegate(unsigned uf)
{
if ((uf & 0x7fffffff) > 0x7f800000)
return uf;
return uf ^ 0x80000000;
}
```
### floatPower2
**功能**： 2.0 ^ x
**想法**：
```c
unsigned floatPower2(int x)
{
unsigned INF = 0xff << 23;
int e = 127 + x;
if (x < 0)
return 0;
if (e >= 255)
return INF;
return e << 23;
}
```
### floatScale1d2
**功能**： 0.5 * f
**想法**：
```c
unsigned floatScale1d2(unsigned uf)
{
unsigned s = uf & 0x80000000;
unsigned ex = uf & 0x7f800000;
if (ex >= 0x7f800000)
return uf;
ex >>= 23;
if (ex <= 1) {
if ((uf & 3) == 3)
uf += 2;
return s | ((uf >> 1) & 0x007fffff);
}
return (uf & 0x807fffff) | ((ex - 1) << 23);
}
```
### floatScale2
**功能**： 2 * f
**想法**：
```c
unsigned floatScale2(unsigned uf)
{
unsigned s = uf & 0x80000000;
unsigned ex = uf & 0x7f800000;
if (ex == 0x7f800000)
return uf;
if (ex == 0)
return s | (uf << 1);
ex += (1 << 23);
if (ex == 0x7f800000)
return s | 0x7f800000;
return (uf & 0x807fffff) | ex;
}
```
### floatScale64
**功能**： 64 * f
**想法**：
```c
unsigned floatScale64(unsigned uf)
{
int exp = (uf & 0x7F800000) >> 23;
int sign = uf & 0x80000000;
int cnt = 22;
if (exp == 0) {
if (!(uf & 0x007E0000))
return (uf << 6) | sign;
while (!(uf & (1 << cnt)))
cnt--;
uf <<= (23 - cnt);
return sign | (uf & 0x807FFFFF) | ((cnt - 16) << 23);
}
if (exp == 255)
return uf;
exp += 6;
if (exp >= 255)
return 0x7F800000 | sign;
return (uf & 0x807FFFFF) | (exp << 23);
}
```
### floatUnsigned2Float
**功能**： (float)u
**想法**：
```c
unsigned floatUnsigned2Float(unsigned u)
{
int i = 1;
unsigned temp;
unsigned result;
if (u == 0) {
return 0;
}
while ((u & 0x80000000) != 0x80000000) {
++i;
u <<= 1;
}
result = u << 1;
temp = result;
result >>= 9;
result &= 0x7fffffff;
i = (32 - i) + 127;
result = (result & 0x807FFFFF) | (i << 23);
if ((temp & 0x00000100) == 0x00000100) {
if (temp & 0x000000FF) {
return result + 1;
} else {
if (result & 1) {
return result + 1;
} else {
return result;
}
}
}
return result;
}
```
### getByte
**功能**： 取出 x 的第 n byte
**想法**：
```c
int getByte(int x, int n)
{
x = x >> (n << 3);
return x & 0xff;
}
```
### greatestBitPos
**功能**：
**想法**：
```c
int greatestBitPos(int x)
{
int n = 0;
n += ((!!(x & ((~0) << (n + 16)))) << 4);
n += ((!!(x & ((~0) << (n + 8)))) << 3);
n += ((!!(x & ((~0) << (n + 4)))) << 2);
n += ((!!(x & ((~0) << (n + 2)))) << 1);
n += (!!(x & ((~0) << (n + 1))));
return (1 << n) & x;
}
```
### howManyBits
**功能**： 回傳表示 x 所需的最少 bits 數
**想法**：
```c
int howManyBits(int x)
{
int sign, bit0, bit1, bit2, bit4, bit8, bit16;
sign = x >> 30 >> 1;
x = (sign & ~x) | (~sign & x);
bit16 = !!(x >> 16) << 4;
x = x >> bit16;
bit8 = !!(x >> 8) << 3;
x = x >> bit8;
bit4 = !!(x >> 4) << 2;
x = x >> bit4;
bit2 = !!(x >> 2) << 1;
x = x >> bit2;
bit1 = !!(x >> 1);
x = x >> bit1;
bit0 = x;
return bit16 + bit8 + bit4 + bit2 + bit1 + bit0 + 1;
}
```
### implication
**功能**： x -> y in propositional logic
**想法**： 只有當 x=1,y=0 時才為 false
```c
int implication(int x, int y)
{
return (!x) | y;
}
```
### intLog2
**功能**： floor(log base 2 of x)
**想法**：
```c
int intLog2(int x)
{
int a0 = 0xFF | (0xFF << 8);
int a1 = a0 ^ (a0 << 8);
int a2 = a1 ^ (a1 << 4);
int a3 = a2 ^ (a2 << 2);
int a4 = a3 ^ (a3 << 1);
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x = (x & a4) + ((x >> 1) & a4);
x = (x & a3) + ((x >> 2) & a3);
x = (x & a2) + ((x >> 4) & a2);
x = (x & a1) + ((x >> 8) & a1);
x = (x & a0) + ((x >> 16) & a0);
return x + ~0;
}
```
### isAsciiDigit
**功能**： return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
**想法**：
```c
int isAsciiDigit(int x)
{
return !(((!!((x >> 4) ^ 3)) | (x >> 3 & x >> 1) | (x >> 3 & x >> 2)) & 1);
}
```
### isEqual
**功能**： 判斷 x == y
**想法**：
```c
int isEqual(int x, int y)
{
return !(x ^ y);
}
```
### isGreater
**功能**： x > y
**想法**：
```c
int isGreater(int x, int y)
{
int sign = ((~x & y) >> 31) & 1;
int mark = ~((x ^ y) >> 31);
int NotEqul = !!(x ^ y);
return sign | ((mark) & (~(x + (~y + 1)) >> 31) & NotEqul);
}
```
### isLess
**功能**： x < y
**想法**：
```c
int isLess(int x, int y)
{
int sign = ((x & ~y) >> 31) & 1;
int mark = ~((x ^ y) >> 31);
return sign | (((mark) & (x + (~y + 1)) >> 31) & 1);
}
```
### isLessOrEqual
**功能**： x <= y
**想法**：
```c
int isLessOrEqual(int x, int y)
{
int sign = ((x & ~y) >> 31) & 1;
int mark = ~((x ^ y) >> 31);
int equl = !(x ^ y);
return sign | ((((mark) & (x + (~y + 1)) >> 31) | equl) & 1);
}
```
### isNegative
**功能**： x < 0
**想法**：
```c
int isNegative(int x)
{
int sign = x >> 31;
return !!sign;
}
```
### isNonNegative
**功能**： x >= 0
**想法**：
```c
int isNonNegative(int x)
{
int sign = x >> 31;
return !sign;
}
```
### isNonZero
**功能**： 不使用 ！ 判斷 x 是否為非 0 值
**想法**：
```c
int isNonZero(int x)
{
int ans = (1 & (1 & ((x | (~x + 1)) >> 31)));
return ans;
}
```
### isNotEqual
**功能**： return 0 if x == y, and 1 otherwise
**想法**： XOR
```c
int isNotEqual(int x, int y)
{
return !!(x ^ y);
}
```
### isPallindrome
**功能**： Return 1 if bit pattern in x is equal to its mirror image
**想法**：
```c
int isPallindrome(int x)
{
int x_ = x;
int a0 = 0xFF | (0xFF << 8);
int a1 = a0 ^ (a0 << 8);
int a2 = a1 ^ (a1 << 4);
int a3 = a2 ^ (a2 << 2);
int a4 = a3 ^ (a3 << 1);
x_ = (x_ << 16) | ((x_ >> 16) & a0);
x_ = ((x_ & a1) << 8) | ((x_ >> 8) & a1);
x_ = ((x_ & a2) << 4) | ((x_ >> 4) & a2);
x_ = ((x_ & a3) << 2) | ((x_ >> 2) & a3);
x_ = ((x_ & a4) << 1) | ((x_ >> 1) & a4);
return !(x ^ x_);
}
```
### isPositive
**功能**： x > 0
**想法**：
```c
int isPositive(int x)
{
int sign = x >> 31;
return (!sign & !!x);
}
```
### isPower2
**功能**： 判斷 x 是否為 power of 2
**想法**：
```c
int isPower2(int x)
{
int minus_noe = (~0 ^ (x >> 31));
return !((x & (x + minus_noe)) | !x);
}
```
### isTmax
**功能**： 判斷 x 是否為最大值
**想法**：
```c
int isTmax(int x)
{
x += 1;
return (!!x & !(x ^ (~x + 1)));
}
```
### isTmin
**功能**： 判斷 x 是否為最小值
**想法**：
```c
int isTmin(int x)
{
return (!!x & !(x ^ (~x + 1)));
}
```
### isZero
**功能**： x==0
**想法**：
```c
int isZero(int x)
{
return !x;
}
```
### leastBitPos
**功能**： return a mask that marks the position of the least significant 1 bit. If x == 0, return 0
**想法**：
```c
int leastBitPos(int x)
{
return x & (~x + 1);
}
```
### leftBitCount
**功能**： returns count of number of consective 1's in left-hand (most significant) end of word.
**想法**：
```c
int leftBitCount(int x)
{
int a0 = 0xFF | (0xFF << 8);
int a1 = a0 ^ (a0 << 8);
int a2 = a1 ^ (a1 << 4);
int a3 = a2 ^ (a2 << 2);
int a4 = a3 ^ (a3 << 1);
x = ~x;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x = ~x;
x = (x & a4) + ((x >> 1) & a4);
x = (x & a3) + ((x >> 2) & a3);
x = (x & a2) + ((x >> 4) & a2);
x = (x & a1) + ((x >> 8) & a1);
x = (x & a0) + ((x >> 16) & a0);
return x;
}
```
### logicalNeg
**功能**： implement the ! operator
**想法**：
```c
int logicalNeg(int x)
{
int ans = (1 & (1 ^ ((x | (~x + 1)) >> 31)));
return ans;
}
```
### logicalShift
**功能**： shift x to the right by n, using a logical shift
**想法**：
```c
int logicalShift(int x, int n)
{
return (x >> n) & ~(((1 << 30 << 1) >> n) << 1);
}
```
### maximumOfTwo
**功能**： compute the maximum of two integers without branching
**想法**：
```c
int maximumOfTwo(int x, int y)
{
int delta = x - y;
int neg = delta >> 31;
int max = (~neg & x) | (neg & y);
int alien = (x ^ y) >> 31;
int x_pos = ~(x >> 31);
return (~alien & max) | (alien & x_pos & x) | (alien & ~x_pos & y);
}
```
### minusOne
**功能**： return -1
**想法**：
```c
int minusOne(void)
{
return ~0;
}
```
### multFiveEighths
**功能**： multiplies by 5/8 rounding toward 0
**想法**：
```c
int multFiveEighths(int x)
{
x = x + (x << 2);
return (x + ((x >> 30 >> 1) & 7)) >> 3;
}
```
### negate
**功能**： return -x
**想法**：
```c
int negate(int x)
{
return ~x + 1;
}
```
### oddBits
**功能**： return word with all odd-numbered bits set to 1
**想法**：
```c
int oddBits(void)
{
int ans = 0xaaaa;
ans |= ans << 16;
return ans;
}
```
### remainderPower2
**功能**：
**想法**：
```c
int remainderPower2(int x, int n)
{
int sign = x >> 31;
int pos = x + (~((x >> n) << n) + 1);
int neg;
x = ~x + 1;
neg = x + (~((x >> n) << n) + 1);
neg = ~neg + 1;
return (~sign & pos) | (sign & neg);
}
```
### replaceByte
**功能**： Replace byte n in x with c
**想法**：
```c
int replaceByte(int x, int n, int c)
{
int mask = 0xFF << (n << 3);
return (mask & (c << (n << 3))) | (~mask & x);
}
```
### rotateLeft
**功能**： Rotate x to the left by n
**想法**：
```c
```
### rotateRight
**功能**： Rotate x to the right by n
**想法**：
```c
```
### satAdd
**功能**： adds two numbers but when positive overflow occurs, returns maximum possible value, and when negative overflow occurs, it returns minimum positive value.
**想法**：
```c
```
### satMul2
**功能**： multiplies by 2, saturating to Tmin or Tmax if overflow
**想法**：
```c
```
### satMul3
**功能**： multiplies by 3, saturating to Tmin or Tmax if overflow
**想法**：
```c
```
### sign
**功能**： return 1 if positive, 0 if zero, and -1 if negative
**想法**：
```c
int sign(int x)
{
return (x >> 31) | (!!x);
}
```
### signMag2TwosComp
**功能**： Convert from sign-magnitude to two's complement where the MSB is the sign bit
**想法**：
```c
int signMag2TwosComp(int x)
{
int sign = x >> 31;
int mag = x & ~(1 << 31);
return (sign & (~mag + 1)) | (~sign & mag);
}
```
### specialBits
**功能**： return bit pattern 0xffca3fff
**想法**：
```c
int specialBits(void)
{
return ~(0xd7 << 14);
}
```
### subtractionOK
**功能**：Determine if can compute x-y without overflow
**想法**：
```c
int subtractionOK(int x, int y)
{
int s_xy = !!((x >> 31) ^ (y >> 31));
int s_y = !(((x - y) >> 31) ^ (y >> 31));
return !(s_xy & s_y);
}
```
### thirdBits
**功能**： return word with every third bit (starting from the LSB)
**想法**：
```c
int thirdBits(void)
{
int x = 0x49;
x |= (x << 9);
x |= (x << 18);
return x;
}
```
### tmax
**功能**： return maximum two's complement integer
**想法**：
```c
int tmax(void)
{
return ~(1 << 31);
}
```
### tmin
**功能**： return minimum two's complement integer
**想法**：
```c
int tmin(void)
{
return 1 << 31;
}
```
### trueFiveEighths
**功能**： multiplies by 5/8 rounding toward 0, avoiding errors due to overflow
**想法**：
```c
int trueFiveEighths(int x)
{
int eights = x >> 3;
int rem = x & 7;
return eights + (eights << 2) + ((rem + (rem << 2) + (x >> 30 >> 1 & 7)) >> 3);
}
```
### trueThreeFourths
**功能**： multiplies by 3/4 rounding toward 0, avoiding errors due to overflow
**想法**：
```c
int trueThreeFourths(int x)
{
int const four = x >> 2;
int const rem = x & 3;
return four + (four << 1) + ((rem + (rem << 1) + (x >> 31 & 3)) >> 2);
}
```
### twosComp2SignMag
**功能**： Convert from two's complement to sign-magnitude
**想法**：
```c
int twosComp2SignMag(int x)
{
int sign = x >> 31;
int mag = (sign & (~x + 1)) | (~sign & x);
return (sign & (1 << 31)) | mag;
}
```
### upperBits
**功能**： pads n upper bits with 1's
**想法**：
```c
int upperBits(int n)
{
int not = !n;
int zero = ~not + 1;
return ~zero & ((1 << 31) >> (n + (~0)));
}
```
:::info
目前進度: 215/228
:::
Sign in with Wallet
Connect another wallet