# 2018q3 Homework3 (review)

<contributed by < `ChingChieh` >
###### tags: `2018q3`
## 第一周測驗二
### 題目
考慮到以下判斷 parity bit 的程式碼

#include <stdio.h>

/* Generate look-up table while pre-processing */
#define P2(n) n, n ^ 1, n ^ 1, n
#define P4(n) P2(n), P2(n ^ 1), P2(n ^ 1), P2(n)
#define P6(n) P4(n), P4(n ^ 1), P4(n ^ 1), P4(n)
#define LOOK_UP P6(0), P6(1), P6(1), P6(0)

/* LOOK_UP is the macro expansion to generate table */ 
unsigned int table[256] = { LOOK_UP };

int parity(int num) {
    /* Number is considered to be of 32 bits */
    int max = 16;

    // Dividing the number into 8-bit 
    // chunks while performing XOR 
    while (max >= 8) {
        num = num ^ (num >> max);
        max /= N;
    }
    // Masking the number with 0xff (11111111) 
    // to produce valid 8-bit result 
    return table[num & 0xff];
}

int main() {
    unsigned int num = 1742346774;
    /* Result is 1 for odd parity, 0 for even parity */
    int result = parity(num);
    printf("%s parity\n", parity(num) ? "odd" : "even");

    return 0;
}

N = ?
### 解釋原理
第十行先建一個長度為256且type為unsigned int的table，裏面存了從0到255分別的parity bit，是為了等等查表用。

再看第24行發現我們需要的結果只在最後 8 bit，剛好有256種可能。

第一次while迴圈時先讓 32 bits數子中 [31:16]bits 和 [15:0]bits 做 XOR，如此一來可以讓成對的1變成0，此時 [15:0]bits 和全部32 bits 的 parity 是一樣的。

接下來因為知道最後我們需要8bits所以這裡就會先猜 N=2 ，然後重複做上面的動作，最後把我們要的結果存在[7:0]bits 此時這8bits 所代表的 parity 會和全部 32bits 一樣。

第4到7行用 macro 的方法來產生 code，這邊這樣寫剛好可以產生出0-255對應的parity
## 第三週測驗三
### 題目
考慮以下程式碼，在 little-endian 硬體上，會返回 `1`，反之，在 big-endian 硬體上會返回 `0`:

int main() {
    union { int a; char b;
    } c = { .a = K1 };
    return c.b == K2;
}

補完上述程式碼。
因為要在 little endian 的硬體上 return 1，所以 a 的 [7:0]bits 要和 b 一樣，所以1和254有可能是答案

當 int a=1 時       
address      : 高        低
big endian   : 01 00 00 00     return 0 == 1
little endian: 00 00 00 01     return 1 == 1


當 int a=254 時
address      : 高        低
big endian   : FE 00 00 00      
little endian: 00 00 00 FE
因為char其實是有號的，所以在little endian的硬體上比較c.b == 254時
其實是-2 == 254所以會 return 0

## 第三週測驗三
### 題目
以下程式碼計算 parity bit:

#include <stdint.h>
int parity(uint32_t x)
    x ^= x >> 1;
    x ^= x >> 2;
    x = (x & 0x11111111U) * 0x11111111U;
    return (x >> P) & 1;
}

P = ?

### 解釋原理
要計算 1 的數量在全部 32 bits 中是奇數個還是偶數個最簡單的方法就是每個 bit 做 XOR 如果結果是 1 就代表有基數個 1。

* 第3,4行
我們先簡化問題用 8 bit 的 ABCDEFGH 來表示 x 的 8 個 bit,
字母相接代表他們做 XOR 。

x:              A    B    C    D    E    F    G    H
x >> 1:         0    A    B    C    D    E    F    G
x ^= x >> 1:    A   AB   BC   CD   DE   EF   FG   GH
x >> 2:         0    0    A   AB   BC   CD   DE   EF
x ^= x >> 2:    A   AB  ABC ABCD BCDE CDEF DEFG EFGH
                              ＾                   ＾

ㄔ
可以觀察到最後的結果第 0 和 4 bit 包含全部我們需要的資訊，也就是說這兩行把全部需要的資訊每隔四的 bit 存
* 第5,6行
把`x = (x & 0x11111111U) * 0x11111111U`拆開來看

x = x & 0x11111111U 

因為所需要的資訊已經每4個bit存好了，所以就把其他bit的值都設為 0 確保等等做乘法可以得到我們要的結果

x = x * 0x11111111U

假設 x = 0000 0001 0001 0000 0001 0001 0001 0000

    0000 0001 0001 0000 0001 0001 0001 0000
  x 0001 0001 0001 0001 0001 0001 0001 0001
  ------------------------------------------
    0000 0001 0001 0000 0001 0001 0001 0000
    0001 0001 0000 0001 0001 0001 0000
    0001 0000 0001 0001 0001 0000
                      ...
  + 0000
  ------------------------------------------  
       ^

可以觀察到因為乘數 `0x11111111U` 第 0,4,8,...,28 bit 是 １ 所以每 4 個 bit 做 XOR 的結果會存在 `31-28 bit` ，因此我們可以從第 28 bit的是 0 或 1 看出 parity 的結果是奇數還偶數。