# 2018q3 Homework5 (bits)

contributed by < `flawless0714` >

## 實驗環境

OS: Lubuntu 18.04.1 LTS (Bionic Beaver)
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.030
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
Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp flush_l1d

## 開發紀錄
- absVal()

    int absVal(int x)
    {
        int y = (x >> 15);
        y >>= 16;
        return ((x ^ y) + (~y + 1));
    }

剛開始想半天想不到如何做出沒有 branch 的二補數運算，結果在找資料時才發現自己對有號整數的理解有問題，在翻閱 C 語言規格書(Bitwise shift operators, p.96)後發現 C 語言對負整數的右移行為的定義為 implementation-defined ，而 gcc 則定義負整數的右移為帶著負號做位移(ex: 0x80 >> 3 會得到 0xF0)，另外有資料提到若編譯器有註明某行為為 platform-dependent ，則需查看編譯器的 doc 去尋找對應的 implementation 。在理解 gcc 對負整數的位移行為後不久就做出要求之功能，進函數後先取得 `x >> 31` 的結果，假如是負數則會得到0xffffffff，反之則為0，最後再對負整數取二補數(反相(`x ^ y`)後加一(`~y + 1`))，其中不難發現到假如 arg 為正整數則可以保持原樣輸出，我只能說多虧 gcc 有這樣的 implementation ，不然我現在還是一頭霧水..。實在是又上了一課，以前只對無號整數做位移，一直以為負整數也是一樣概念...。

- addOK()

    int addOK(int x, int y)
    {
        unsigned xM = x, yM = y, oF = x + y;

        xM >>= 31;
        yM >>= 31;
        oF >>= 31;

        return !(((!xM) && (!yM) && (oF)) || ((xM) && (yM) && (!oF)));
    }

本題使用真值表將會造成溢位之排列組合找出,再將化簡後之布林式實做出來,真值表如下:
| xM | yM | oF | ==res== |
|:--:|:--:|:--:|:--:|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |

- allEvenBits()

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

本題將輸入先與 0x55555555 做 bitwise AND 運算以得到僅剩下偶數位元之輸入，再將此結果與 0x55555555 做 bitwise XOR 運算，如此一來假如全部偶數位元都為 1 的話，我們會得到 0，再將此結果做 logical inverse 以回傳題目要求之輸出。

- allOddBits()

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

本題概念與上題雷同。

- anyEvenBit()

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

本題先將輸入過濾到剩下偶數位元，之後再將結果反相兩次以得到非0即1的輸出。

- anyOddBit()

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

本題概念與上題雷同。

## 筆記
- branch
程式執行過程中需要跳躍的地方即為 branch。

- conditional branch
for loop, while loop, `if`, `?:` (ternary operator) ...
- unconditional branch
`continue`, `break`, infinite loop ...
## 問題
- cppcheck
==Shifting signed 32-bit value by 31 bits is undefined behaviour== ,這 warning 我有個無法理解的點，將一 32-bit 資料右移31個 bits 只把 MSB 移到 LSB的位置，為什麼這樣會有 UB ，還是說我露考慮了甚麼地方?