---
# System prepended metadata

title: 2020q3 Homework6 (quiz6)

---

# 2020q3 Homework6 (quiz6)
contributed by < `fwfly` >

## 測驗 3
```c=
#define cons(x, y) (struct llist[]){{y, x}}
```

### Compound literals
通常是用在初始化． 


回到題目
```c=
struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);
```



A = (d)7、B = (c)4、C = (b)5、D = (a)9
SS1 = (d) node->next = *head、SS2 = (b) *head = node。



## 測驗 4
條件: 
有 n+1 個數的數列
數字從 1 ~ n 
裡面會有一個數字重複

### 思考
從 binary 的角度去想可以找到答案
比方說有一串數列 12342 翻成 binary 就會是下表
然後每個 bit 的總數如下

|Number| 3rd bit | 2ed bit | 1st bit  | 
|---| -------- | -------- | -------- |
|1| 0     | 0     | 1     |
|2| 0     | 1     | 0     |
|3| 0     | 1     | 1     |
|4| 1     | 0     | 0     |
|2| 0     | 1     | 0     |
|bit 總數|1 |**3**|2|    

再來看單純 1 到 4 個數列 (因為數字是從 1 ~ n 且 n 目前為 4)
1,2,3,4
|Number| 3rd bit | 2ed bit | 1st bit  | 
|---| -------- | -------- | -------- |
|1| 0     | 0     | 1     |
|2| 0     | 1     | 0     |
|3| 0     | 1     | 1     |
|4| 1     | 0     | 0     |
|bit 總數|1 |**2**|2|    

從上面兩個表格可看到第二個 bit 總數比較大 (3 > 2)
因此就可以找出來 2 是重複的數字


### 如果重複數字是 3 的情形 ?
同樣把數列拉出來轉 binary
|Number| 3rd bit | 2ed bit | 1st bit  | 
|---| -------- | -------- | -------- |
|1| 0     | 0     | 1     |
|2| 0     | 1     | 0     |
|3| 0     | 1     | 1     |
|4| 1     | 0     | 0     |
|3| 0     | 1     | 1     |
|bit 總數|1 |**3**|**3**|    

再來看單純 1 到 4 個數列 (因為數字是從 1 ~ n 且 n 目前為 4)
k = 1...4
|Number| 3rd bit | 2ed bit | 1st bit  | 
|---| -------- | -------- | -------- |
|1| 0     | 0     | 1     |
|2| 0     | 1     | 0     |
|3| 0     | 1     | 1     |
|4| 1     | 0     | 0     |
|bit 總數|1 |**2**|**2**|    

可以看得出來 1st 跟 2ed 的 bit 數都比較大 (3 > 2)
那這樣答案是 1 還是 2 ?
在這個時候就會做`把較大的 bit 加總起來`
```c=
            res += bit;
```

### 結論
概念上就是`題目的數列`跟`單純的 1~n 數列`做 bit 的比較
```
12234 跟 1234
12334 跟 1234
14234 跟 1234
以此延伸
```
因為重複的數字會讓那個數字的 bit 多 1 
```
12234 跟 1234 -> 多一個 010
12334 跟 1234 -> 多一個 011
14234 跟 1234 -> 多一個 100
```
所以透過兩個 counter 一個去紀錄`題目的數列` 另一個去紀錄`單純的 1~n 數列` 依照題目就是 : 
c1 : `單純的 1~n 數列`
c2 : `題目的數列`
如果 c2 > c1 表示找到多出來的 bit
最後再把這些 bit 作加總就可以得出重複的數字


### log_2
```c=
const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
```
8 * sizeof(int) 考量到各種不同長度的 int 大小(可能 64 也可能 32)
最後再用 __builtin_clz 去找出有多少個 0 不用去計算
透過上面的方式可以有彈性的找到回圈長度 log_2

由於是 bit by bit 的執行，時間上會比跑整個數列還要少很多, 假設用暴力方式每個數字去做比較
從 2^31 ( 假設整數是 32bits ) -> 最多跑 31 次就可以跑完一輪數列


### 參考
-  sizeof
[C99 規格書](http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf)  
:::info
6.5.3.4 The sizeof operator:
The sizeof operator yields the size (in bytes)
:::
