# W1-QA

###### tags: `c14006078` `W1-QA` `sysprog21`

## W1 課程提問
* [21 世紀的系統軟體](https://hackmd.io/s/r1srX7Za)
* 看不懂 No pain, No gain...的電路
* GPU 將會是相對，concurrency的問題，但是我好奇目前有沒有任何工具可以探測這個程式或是function的可平行度有多少，簡單來說就是一個程是來判斷這份工作要給CPU或者GPU，目前我們寫的程式都是寫我要用CPU或者GPU，一般程式vs CUDA，是否有這樣的機制呢？
*

## 隨堂測驗 W1 解法 [link](https://hackmd.io/s/r13u0Af6)

## Q1: 以下程式的作用為何？

int p(int i, int N)
{
    return (i < N && printf("%d\n", i) && !p(i + 1, N)) \
           || printf("%d\n", i);
}

## 解法
這題我再一開始並沒有馬上反映出來，先帶個數字進去才了解的，後來我領悟到這種 recursive 版本，最主要要先找中止條件，所以很明顯，即是 `i < N`，因為 printf()的 return 值是印出多少個字元，所以永遠為 true，再來是運算式是`left to right`，再來是`&&`和`||`，這個即是`and`和`or`，而`and`當前面出現`false`時後面就不用算了，而C的設計也是一模一樣，反之`or`，分析完這幾個細節後，再來就是找細部的中止條件，我們發現遞迴還會出現再這 `!p( i+1, N)`，所以他的中止條件依舊是`i < N`，所以會先 print i~N-1，會再 i == N，時，會傳回 true，因為 || printf()，再來因為 ！p(i +1, N)，所以都會前面都會是 false，所以 or 又會繼續印完，印出 `i~N~i`。
>> 根據老師的提示，我有兩個部份沒考慮清楚
>> 1.input的範圍沒考慮 2. stack depth 沒考慮
>>
>> 第1點我要補充的是當 i >=間 N 時，會輸出一個 i。
>> 第2點經過我測試，真的會有問題，我用 `i = -2147483647 N = 2147483647`，但我目前沒有一個很好的算法來測量我的 stack 到底多大，目前我只能 print 大約這個數字 260984 ~ 261800，我好奇點是他居然會浮動= =，所以目前我沒有一個很好的算法。

* `&&` 前後的敘述對調，是否影響輸出？
* 從 `i < N && printf("%d\n", i)` 變更為 `printf("%d\n", i) && (i < N)` 的話，程式輸出為何？
* 解法
* 就上面的分析，會不一樣的地方出在 i == N 時，這樣會 print出兩次 N。

## Q2: 考慮以下 swap 程式:

void swap(int *a, int *b)
{
    int t; t = *a; *a = *b; *b = t;
}

能否避免使用區域變數 t？又，可否改用 bit-wise operator 來改寫？

-->

算術:

*a = *a - *b;
*b = *a + *b;
*a = *b - *a;

## 解法
==這題我完全沒有想到該怎麼做，我已經被區域變數的解法給綁死了= =，忘了swap的真正意義，就是把值對調就好了，而我卻死腦經卡在以前的作法，這題的概念很簡單，即是算出差距，先把b 變到 a的高度，由於我們來留著 差距，再把 a的高度弄到b之前的高度。==

邏輯運算:

*a = *a XOR *b
*b = *a XOR *b
*a = *a XOR *b

## 解法
==我們要先知道一件事情，if a ^ b = c,then a ^ c = b and c ^ b = a，所以這也是變相找到差距的意思，先記算出a ^ b，再來就是保留他，並且去 XOR 另一個數字，跟上面的想法是一樣的。==

**IMPORTANT：邏輯運算的好處是，可避免前述算術會遇到的 integer overflow，而且不限定位元數。**

## Q3: 用 C 語言實做 `char *reverse(char *s)` 來反轉 NULL 結尾的字串，限定 in-place 與遞迴

參考實作 (都還可以大幅改進，只是列出來給大家看)

* [Day2](https://embedded2015.hackpad.com/GGI4IhFdLUW)

**C-style string reverse (遞迴 + in-place)**

* 先想想這個版本可用嗎? (以及對應的問題)

void reverse (char *s) {
    if (*s == ’\0’) return;
    reverse (s+1);
    printf ("%c", *s);
}

## 解法
==首先上面的實作，我認為是可行的，但效能上應該是非常差的，還有他沒有做到return reverse string的功能，只有 print，而且他有非常非常多次的 function call的 overhead，我也稍微看過老師給的參考實作，首先很漂亮的是這個==

void swap(char *c1, char *c2){
	*c1 ^= *c2 ^= *c1 ^= *c2;
}

==再來是 iterative的版本，等於找 N/2次，但我相信 strlen()必定也有很高的 overhead，我目前的想法有跳兩格找到\`\0\`後，再往前跳，這個想法可以類推到 3 4 5 ...，但重點是如何決定這個數字，所以目前我想到最好的應該就是`log N`，的strlen()==
==目前我的想法應該跟他一樣會使用 iterative的方式==