# 2022q1 Homework2 (quiz2) contributed by < `happyjack91630` > >[作業需求](https://hackmd.io/@sysprog/linux2022-quiz2) ## 測驗 `1` :::success EXP1 = a & b EXP2 = a & b EXP3 = a ^ b ::: ```c= uint32_t average(uint32_t a, uint32_t b) { return (a >> 1) + (b >> 1) + (EXP1); } ``` `a>>1`，就是floor(a/2)的動作，但是floor((a+b)/2)有時候並不會等於floor(a/2) + floor(b/2)。在a和b都是奇數的時候，就會出問題。比如: a=7,b=3，floor((7+3)/2)=5，但是floor(7/2)+floor(3/2)=4，會少一個單位。所以`EXP1`就是要在a和b都是奇數情況下把1加回去。`EXP1 = (a&1)&(b&1)`因為a如果是奇數，a&1就會是1，所以如果a和b都是奇數，1&1=1，就能把兩個奇數各別floor過後加起來少1的值加回去了。`(a&1)&(b&1)`能夠化簡成`a&b`。 ```c= uint32_t average(uint32_t a, uint32_t b) { return (EXP2) + ((EXP3) >> 1); } ``` 前面一題，是先分開除在相加，那這題則是**先相加在除**。位元相加可以用`(a ^ b)`代表加完後LSB的位元是甚麼，但是相加過後還要考慮進位的問題。進位的問題則是利用了`(a & b) <<1 `去處理。所以a + b 可以被表示為`(a & b) << 1 + (a ^ b)`，最後在做除二的動作，就是>>1。化簡就會變成`(a & b) + (a ^ b) >> 1`。 ## 測驗 `2` :::success EXP4 = a ^ b EXP5 = a < b ::: ```c= #include <stdint.h> uint32_t max(uint32_t a, uint32_t b) { return a ^ ((EXP4) & -(EXP5)); } ``` 以下面case分析: | a = 3 b = 8 | a = 8 b = 3 | | -------- | -------- | | => 0011 ^ ((EXP4) & -(EXP5)) = 1000 | => 0011 ^ ((EXP4) & -(EXP5)) = 0011| | => ((EXP4) & -(EXP5)) = 1011 (a ^ b) | => ((EXP4) & -(EXP5)) = 0000 | | 若EXP4 = a ^ b| 若EXP4 = a ^ b | | => ( 1011 & -(EXP5)) = 1011 | => ( 1011 & -(EXP5)) = 0000 | | => -(EXP5) = 1111 (補數)| => -(EXP5) = 0000 | | => EXP5 = 0001 | => EXP5 = 0000 | 左邊的EXP5 == 0001，右邊EXP5 == 0000，可以想成右邊的EXP5為true，左邊的為EXP5為false，那能比較的就是a和b的大小了。所以`EXP5 = a < b`。如果a = b就會回傳a，但也沒關係。 ## 測驗 `3` :::success COND = v == 0 RET = u << shift ::: ```c= #include <stdint.h> uint64_t gcd64(uint64_t u, uint64_t v) { //若u or v 為0,則回傳不是0的數，若u,v皆為0則回傳0 if (!u || !v) return u | v; int shift; //以下for迴圈先計算u,v共同有幾個2次方的因數，結果存在shift裡 for (shift = 0; !((u | v) & 1); shift++) { u /= 2, v /= 2; } //上述for迴圈跑完就會計算所有共同2次方的因數了，所以while可以把u裡2的因數都除掉 while (!(u & 1)) u /= 2; do { while (!(v & 1)) //跟上面for迴圈想法類似，把2的因數刪掉 v /= 2; if (u < v) { //因為等等要用減法算餘數，所以不能有負數情況出現 v -= u; } else { uint64_t t = u - v; //利用減法算餘數 u = v; //gcd u,v對調 v = t; //gcd u,v對調 } } while (COND); //gcd如果還找不到公因數，v != 0，還要再進while迴圈找 return RET; //u為公因數，但是不要忘記前面有先計算2的次方的公因數，所以要把它乘回來，所以最終公因數為 u << shift } ``` ### 在 x86_64 上透過 __builtin_ctz 改寫 GCD ```c= #include <stdint.h> //回傳min(a,b) uint64_t min(uint64_t a, uint64_t b) { uint64_t diff = (a - b); return b + (diff & (diff >> 63)); } //__builtin_ctz回傳尾巴有幾個0 uint64_t gcd64(uint64_t u, uint64_t v) { if (!u || !v) return u | v; int shift = min(__builtin_ctz(u), __builtin_ctz(v)); u >>= shift; v >>= shift; u >>= __builtin_ctz(u); do { v >>= __builtin_ctz(v); if (u < v) { v -= u; } else { uint64_t t = u - v; u = v; v = t; } } while (COND); return RET; } ``` ## 測驗 `4` :::success EXP6 = bitset & -bitset ::: ```c= #include <stddef.h> size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out) { size_t pos = 0; uint64_t bitset; for (size_t k = 0; k < bitmapsize; ++k) { bitset = bitmap[k]; while (bitset != 0) { uint64_t t = EXP6; //找出最低位元為1的 int r = __builtin_ctzll(bitset); out[pos++] = k * 64 + r; bitset ^= t; } } return pos; } ``` 題目有敘述，其中第 9 行的作用是找出目前最低位元的`1`，並紀錄到 t 變數。那`EXP6 = bitset & -bitset`。那第12行就能在使用XOR的方式將最低位元的1清掉為0，再繼續找下一個最低位元為1的地方。 ## 測驗 `6` >參考 kevinshieh0225 >[linux 内核container_of剖析](https://zhuanlan.zhihu.com/p/54932270) :::success M = _h X = 0 ::: ```c= /* * ALIGNOF - get the alignment of a type * @t: the type to test * * This returns a safe alignment for the given type. */ #define ALIGNOF(t) \ ((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X) ``` 在看懂上述程式碼之前，可以先去看`offestof`這個function。 ```c= #define offsetof(s,memb) \ ((size_t)((char *)&((s *)0)->memb-(char *)0)) ``` 讀懂順序: 1. `((s *)0` => 先將`0`轉型成`s`這個結構體，這麼做是在給定一個起始地址在0的結構，以便後續算出`memb`的offset。 2. `&((s *)0)->memb` => 取得`memb`地址。 3. `(char *)&((s *)0)->memb` =>將地址轉型成(char *)來看，這樣就能1byte，1byte來算了。 4. `((char *)&((s *)0)->memb-(char *)0))` => 用`memb`的地址減掉`0`的地址就能算出offset了。 5. `(size_t((char *)&((s *)0)->memb-(char *)0)))` => 將算出來的`offset`轉型成`size_t`型態。 依照`offsetof`的邏輯，`ALIGNOF`的答案就顯而易見了。