# 2018q3 Homework5 ([bits](https://hackmd.io/s/r14wRqUjQ))
contributed by < [wingard](https://github.com/wingard) >

###### tags: `HW5`

## 作業要求

* 自 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 的提案，並舉出實際程式碼修改

---
## 環境設定

測試環境

$ cat /etc/lsb-release 
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=18.04
DISTRIB_CODENAME=bionic
DISTRIB_DESCRIPTION="Ubuntu 18.04.1 LTS"

依照作業的指示，會無法安裝套件

$ sudo apt install libc6-dev:i386 gcc:i386
[sudo] password for kevin: 
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.

改為安裝 `gcc-multilib`

$sudo apt install gcc-multilib

## bits.c - integer

### absval

* 如果是正數的話，回傳原始的值，否則回傳 1 補數加 1

x >> 31; //get all 1 or all 0
return (y ^ x) + (~y + 1);

### addok

### allEvenBits/anyEvenBit/allOddBits/anyOddBit

* 每次折半比較，最後再 mask ，差別在:
* Even Bit: 最後的 Mask = 0x1
* Odd Bit: 最後的 Mask = 0x2
* all: 每次折半比較的 operator 是 `&=`
* any: 每次折半比較的 operator 是 `|=`

* 另外根據 [c operator precedence](https://en.cppreference.com/w/c/language/operator_precedence)，會先執行 `>>` 再執行 `&=` `|=`

int allEvenBits(int x)
{
    x &= x>>16;
    x &= x>>8;
    x &= x>>4;
    x &= x>>2;
    
    return x&0x1;
}

int allOddBits(int x)
{
    x &= x>>16;
    x &= x>>8;
    x &= x>>4;
    x &= x>>2;
    
    return x&0x2;
}

int anyEvenBit(int x)
{
    x |= x>>16;
    x |= x>>8;
    x |= x>>4;
    x |= x>>2;
    
    return x&0x1;
}

int anyOddBit(int x)
{
    x |= x>>16;
    x |= x>>8;
    x |= x>>4;
    x |= x>>2;
    
    return x&0x2;
}

### bang

* `!` 意義是0變成1，非0變成0
*

### bitAnd

### bitCount

### Conditional

* 參考了[ofAlpaca 的實作](https://hackmd.io/s/By9Rt6x37#conditional)，這是我目前看過最神奇的一段code了...
* 先透過`!!x`將 x 轉化成 0 或 1
* 取 `x` 的二補數，此時 x 必為全 0 或全 1

/*
 * conditional - same as x ? y : z
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z)
{
    x = !!x; //reduce x to 0 or 1

    x = ~x + 1; // x will be all 0 or all 1
                // ~x will be all 1 or all 0
    return (x & y) | (~x & z);
}

## bits.c - floating point