# 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) :::