# 2020q3 Homework3 (quiz3)

contributed by < ddj5523fa >

---

### 想法 & 思考

#### 測驗一

題目:

int asr_i(signed int m, unsigned int n)
{
    const int logical = (((int) -1) OP1) > 0;
    unsigned int fixu = -(logical & (OP2));
    int fix = *(int *) &fixu;
    return (m >> n) | (fix ^ (fix >> n));
}

1.
(1)==const int logical = (((int) -1) OP1) > 0;== 根據參考資料unspecified behavior，得知需先判斷是logic shift或是
arithmetic shift。
所以OP1應為>>1(右移才有logic或arithmetic的差別)<------==answer==
(2)==unsigned int fixu = -(logical & (OP2));== 若m值是正的，則不管是logical或arithmetic，右移時候最左bit一定是補0所以沒有影響。 但是如果是負值最左bit補上的數將不一樣 此行程式碼便是判斷此部分，所以
OP2應為==m<0== <--------------------------------==answer==
(3)==int fix = *(int *) &fixu;== 因型態是unsigned int 與 int所以才以取fixu值的位置再取值assign給fix。

---

#### 測驗二:

bool isPowerOfFour(int num)
{
    return num > 0 && (num & (num - 1))==0 &&
           !(__builtin_ctz(num) OPQ);  
}

4的power首先先得知是的binary:==100==。
16=$4^2$，其binary: ==10000== 相當於100左移動2格。
64=$4^3$，其binary: ==1000000== 相當於10000左移2格。
1.
(1)由程式碼中num>0可過濾負數，然後(num & (num - 1))==0可得知過濾掉了不是2冪次的數了，因為n是2冪次的時候binary是1後面跟著數個(假設m個)0，而n-1就是0後面跟著"數個(m個)"1，做 AND 就會是0。
(2) 已經過濾了負數且確定是2冪次情況下， ==__builtin_ctz(num)== 可得到num的binary中，後面有幾個0。而根據前面分析4冪次的binary可知後面0的數量必定是偶數個(2的倍數個)。所以__builtin_ctz(num)得到偶數值就是4的冪次，但程式碼取了 ==NOT(!)==

由以上可得知，OPQ應為 ==&0x1== <------------------------==answer==

---

#### 測驗三:

題目是說num是偶數就除以2，是奇數就-1，重複做了幾次操作會得0。
程式碼:

int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}

p.s. ```__builtin_popcount(x):``` 計算 x 的二進位表示中，總共有幾個 1
由```1342. Number of Steps to Reduce a Number to Zero```的例子14推演一次: binary是0000 0000 0000 0000 0000 0000 0000 1110
而除以2相當於>>1，所以得知最高位元在第幾位便可知道需要右移幾次，而奇數減1則可觀察到在binary中有1的部分在右移到最低位時候變成了奇數要減掉。
所以檢測有幾個1跟最高位元是幾位是此題關鍵!
1.(1)```__builtin_popcount(x)```便是找出幾個1
(2)程式碼中有個31讓人聯想到，題目提到的==假設 int 為 32 位元寬度==，
所以最高位元應是以int __builtin_clz (unsigned int x)取得前面有多少個0然後用31去扣來得知。
所以AAA為==builtin_popcount(x)== <--------------------answer
BBB為==builtin_popcount(x)==   <------------------answer

##### 延伸學習:

考慮到不能用判斷式，想到的便是 AND OR NOT等邏輯式
因該題理解到他會用到偶數判斷與奇數判斷，所以想到num與0x1做and可得之。
於是產生以下程式碼:

int numberOfSteps (int num){
int res=0,subtimes=0,divtimes=0;
while(num>0)
{
int odd=num&1;
int even=!(num&1);
subtimes=subtimes+odd;
divtimes=divtimes+even;
num=(num-odd)>>even;
};
res=subtimes+divtimes;
return res;
}

測試有成功submit:
![](https://i.imgur.com/96ucmKw.jpg)



---

#### 測驗四:

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (XXX);
return YYY;
}

1.
(1).上方程式碼第5行 !((u|v)&1) 表示出u跟v binary中最左是1的時候，該迴圈結束:此效果能表達出迴圈成立時，表示u、v都還有==2的因數==。
所以程式碼該for迴圈中的shift便是紀錄有多少個共同有的2的因數數量。
(2).while迴圈中除去2的因數是為了製造出兩奇數相減，而此時去除2的因數不會影響結果。
(3).接下來 if else中可以看出，每次操作都將減過得成果存至v是因為兩奇數相減變成偶數，而do while中只有處理v所以，必須將偶數存至v。
(4).do while 結束條件:
根據參考 [此篇](https://hackmd.io/@sysprog/gcd-impl#Binary-GCD)的==Binary GCD Algorithm== 。知道最後依然有採用輾轉相除法，所以最後終止結果為0而每次相減結果存於v。 
所以，XXX答案應為==v==    <--------------answer!
而 GCD(u,0)=u，所以最大公因數答案應為u，但是必須回復之前for迴圈提出的2的因數，
所以，YYY答案應為==u<<shift==   <----------answer!


------------------------------
測驗五: