# 2018q3 Homework5 (bits)

## absVal
參考之前考試題目，由於有限制 operator `-` 。那其實我們原本在考試時候是用 `-y` ，換個想法就是把一個數取負號，不就可以利用二補數的概念 先取 ==1 補數再 +1== ，就可以拿到自己相反的數。

int absVal(int x)
{
    int y = x >> 31; // get signed bit
    return (y ^ x)+(~y + 1); 
}

## addOK
我們需要關心的是`正數+正數` `負數+負數` 造成 signed bit 變號, 所以我都取`signed bit`來做檢查，最後的 return 是用 Karnaugh Map 寫出來的。`正數+負數` `正數+負數` 可以放心的加就算 overflow 最後出來也是正確的。

int addOK(int x, int y)
{
    int ans_sig =  !!((x+y) >> 31);
    int x_sig = !!(x >> 31);
    int y_sig = !!(y >> 31);
    return ( (!x_sig & !ans_sig) | (y_sig & ans_sig) | (x_sig & !y_sig));
}

## allEvenBits
想法就是跟`1010 1010 1010 1010 1010 1010 1010 1010 ` 結合一下，最後只要是 -1 ，就代表偶數位都是`1`

int allEvenBits(int x)
{   
    return !((x | 0xAAAAAAAA )+1);
}

## allOddBits

int allOddBits(int x)
{
    return !((x | 0x55555555 )+1);
}

>下面分數怪怪der，到底有沒有得分
>[name=jn]
>[color=blue]

mec@mec-MS-7A63:~/JN_work/embededHW/datalab$ ./btest 
Score	Rating	Errors	Function
 4	4	0	absVal
 3	3	0	addOK
 2	2	0	allEvenBits
 2	2	0	allOddBits
ERROR: Test anyEvenBit(-2147483648[0x80000000]) failed...
...Gives 42[0x2a]. Should be 0[0x0]
ERROR: Test anyOddBit(-2147483648[0x80000000]) failed...
...Gives 42[0x2a]. Should be 1[0x1]

mec@mec-MS-7A63:~/JN_work/embededHW/datalab$ ./btest -f alloddBits
Score	Rating	Errors	Function
Total points: 0/0

## anyEvenBit
* 與 `0101 0101 0101 0101 0101 0101 0101 0101` 結合，利用`xor`有變化就知道有偶數 bit

int anyEvenBit(int x)
{
    return !!(x & 0x55555555);
}

## anyOddBit
* 同樣概念

int anyOddBit(int x)
{
    return !!(x & 0xAAAAAAAA);
}

## bang

int bang(int x)
{  
    int or_sum = x | (~x+1);
    return  0x1 ^ (0x1 & (or_sum >> 31));
}

* 參考這裡的[作法](https://www.viseator.com/2017/06/18/CS_APP_DataLab/)，就是利用與自己的相反數做 `or` 就可以透過最高位元知道這個數是不是`0`，後續就是做一些簡單取值的動做。

## h2 bitAnd

int bitAnd(int x, int y)
{
    return ~(~x | ~ y);
}

* 利用 `or` 特性一定要都是 `0` 才會是 `0`

## distinctNegation

int distinctNegation(int x)
{    
    int x_ops = ~x+1;
    x = x_ops | x;
    x = x << 1 ;          
    return !!x;
}

* 我觀察三種狀況，假設只有 3 bits ，觀察當自己與自己的相反數做 `or` ，會有什麼結果。
* 011 | 101
* 000 | 000
* 100 | 100

## getByte

由輸入來決定要 shift 幾個 bits

int getByte(int x, int n) 
{
    return    (x >> (n<<3)) & 0xff;
}

## implication ->

A為真，則B也為真；如果A為假，則對B沒有任何影響

+|0|1|
0|1|1|
1|0|1|

int implication(int x, int y)
{
    return (!x )| y;
}

## isEqual

畫出 truth table ，即可了解用 XOR 配合驚探號

int isEqual(int x, int y)
{
    return !(~(~x & ~y) & (~(x & y)));
}

## isGreater
畫出 truth table 即可了解。找出 x_sig, y_sig 與 sub_sig 找出之間的關係。因為是要 `>0` 不是 `>=0` , 所以再做相反數時候不用 `+1`

int isGreater(int x, int y)
{   int sub_sign = !!((x+(~y))>>31);
    int x_sign = !!(x>>31);
    int y_sign = !!(y>>31);
    return ((!x_sign)&(!sub_sign)) | ((!x_sign)&y_sign) | (x_sign&y_sign&(!sub_sign));
}

## isLess

把上面那題的 x 與 y 互換。

int isLess(int x, int y)
{
    int sub_sign = !!((~x+(y))>>31);
    int x_sign = !!(x>>31);
    int y_sign = !!(y>>31);
    return ((!y_sign)&(!sub_sign)) | ((!y_sign)&x_sign) | (y_sign&x_sign&(!sub_sign));
}

## isLessOrEqual
把上面那題的 `1` 加回去，奇怪的是單獨測試這個 function 盡然是 error function ，但是全部測試會過 operator 數目沒有超過(22個)，也沒使用違規 operator

int isLessOrEqual(int x, int y)
{
    int sub_sign = !!(((~x+1)+y)>>31);
    int x_sign = !!(x>>31);
    int y_sign = !!(y>>31);
    return ((!y_sign)&(!sub_sign)) | ((!y_sign)&x_sign) | (y_sign&x_sign&(!sub_sign));
    return 42;
}

## isNonZero
這個四分太好賺了吧～～～～LOL~~~

/*
 * isNonZero - Check whether x is nonzero using
 *              the legal operators except !
 *   Examples: isNonZero(3) = 1, isNonZero(0) = 0
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 4
 */
int isNonZero(int x)
{
    return !!x;
}

## isTmax
兩個條件
* 是不是正數
* 是不是0x7fffffff

int isTmax(int x)
{
    
    return (!(x+0x80000001))&(!(x>>31));
}

## isTmin
同上概念

int isTmin(int x)
{
    return (!(x+0x80000000))&(x>>31);
}

## isZero

int isZero(int x)
{
    return !x;
}

## greatestBitPos
* [參考](https://stackoverflow.com/questions/21413565/create-a-mask-that-marks-the-most-significant-set-bit-using-only-bitwise-operat)

int greatestBitPos(int x)
{
    unsigned int m;
    m = x;
    m = m | m >> 1;
    m = m | m >> 2;
    m = m | m >> 4;
    m = m | m >> 8;
    m = m | m >> 16;
    m = m & ((~m >> 1)^0x80000000);
    return m;
}