# 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`的答案就顯而易見了。
Sign in with Wallet
Connect another wallet