owned this note
owned this note
Published
Linked with GitHub
# 2018q1 Homework3 (Assessment)
contributed by <`piggyking1421`>
## 第1週測驗題 第5題
考慮以下整數乘法的實作程式碼:
```C=
int mul(int n, int m)
{
int ret = 0;
for (int c = 0; m; c++, m /= 2)
if (!(m % 2 - 1)) OP
return ret;
}
```
上述 `OP` 對應到下方哪個程式敘述呢？
`(a)` ret = n << c;
`(b)` ret += n;
`(c)` ret <<= n;
`(d)` ret = c << n;
`(e)` ret += n << c;
### 想法
當初測驗一時想不到，後來想想發現是利用二進位乘法的特性，以直式的想法去思考才想通。
以 $n \times m$ 兩個數字相乘來說，若將$n$和$m$分別以二進位表示
$n=[n_w,n_{w-1},n_{w-2},\ ...\ ,n_2,n_1]$
$m=[m_w,m_{w-1},m_{w-2},\ ...\ ,m_2,m_1]$
$w$ 代表位數
做乘法時用
$n \times m_1 \ +\ n \times m_2\times 2^{1}\ +\ n \times m_3\times 2^{2}
...n \times m_w \times 2^{w-1}$
即可求得解。
舉例來說若$n=1011\ ,m=1010$ 寫成直式如下
```
1 0 1 1
x 1 0 1 0
----------
0
1 0 1 1
0
1 0 1 1
----------------
1 1 0 1 1 1 0
```
因此程式中第4行 for 迴圈的 變數c 便是用來紀錄乘到 $m$ 的第幾位，m /= 2則是每次迴圈將 $m$ 向右 shift，直到 shift 到 m 為0才停止執行，第5行的 if 則是判斷 m 現在的最低有效位數是否為 1 ( m 為 int ，小數自動捨去)，若為1則將 n 乘上 $2^c$ 加進 ret 中，因此思考後可求得解為 ==ret += n << c==
上例若寫成直式則拆解如下
```
1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1
x 1 0 1 0 x 1 0 1 x 1 0 x 1
---------- ==> ---------- ==> ---------- ==> ----------
0 1 0 1 1 0 1 0 1 1
c = 0 c = 1 c = 2 c = 3
ret = 0 ret = 10110 ret = 10110 ret = 10110 + 1011000 = 1101110
```
:::info
不知為何 if 中要用 !(m % 2 - 1) 而不是直接使用 (m % 2) ，前者可以確保$m_1$恰為1才執行，後者則是$m_1$非0即執行，實際跑了一遍好像沒有差，是為了確保移植的安全性？可能我哪裡想漏了
:::
>後面寫一寫發現好像和負值modulo出來為負有關
### 嘗試
測試了一下發現原本的程式在負數的乘法上會有問題，m為負時return 0，n負m正卻正常計算，想嘗試修正
其實對C語言的位移並不是很熟，原本查來查去還是覺得不太清楚，後來去查了一下[*ISO/IEC 9899:1999*](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 的 6.5.7 Bitwise shift operators，裡面提到了
* 若是右邊的運算元為負值，或是大於左邊的運算元型態的最大寬度，則此行為是未定義的行為
* 原本沒看懂第二句的意思，後來自己測試了一下
```c=
main()
{
int x = 0x0000ffff;
printf("%x\n",x << 16);
printf("%x\n",x << 17);
printf("%x\n",x << 32);
printf("%x\n",x << 33);
printf("%x\n",x << 1);
}
```
顯示結果為
```=
ffff0000
fffe0000
ffff
1fffe
1fffe
```
我的環境 int 是32bit ，看到結果比較清楚它的意思(我的英文不好，看到測試結果比較安心一點QQ)，從結果可以得知在大於等於左方的運算元寬度後，會執行位移(右方的運算元-寬度)的行為
>等等 我測一測好像想到CS:APP上有提到這段，看完就忘了阿阿阿阿 書都白看了
* 位移時會看左方的運算元為signed或是unsigned，若左移時左方運算元為signed且為負，則此行為是undefined。因為最左方代表sign的bit會被捨去。
* 向右位移時若左方運算元為signed且為負則會做sign extension，維持正負。
* ```c
main()
{
unsigned int ux;
signed int sy, sz;
ux = 0x0000ffff;
sy = 0x0000ffff; //正值
sz = 0x8000ffff; //負值
printf("%x\n%d\n%d\n\n",ux<<8,ux,ux<<8);
printf("%x\n%d\n%d\n\n",sy<<8,sy,sy<<8);
printf("%x\n%d\n%d\n\n",sz<<8,sz,sz<<8);
printf("%x\n%d\n%d\n\n",ux>>8,ux,ux>>8);
printf("%x\n%d\n%d\n\n",sy>>8,sy,sy>>8);
printf("%x\n%d\n%d\n\n",sz>>8,sz,sz>>8);
}
```
結果如下
左移
|type |原值(HEX)| shift後(HEX)|原值(DEC)|shift後(DEC)|
|-|-|-|-|-|
| unsigned | 0x0000ffff | ffff00 |65535|16776960|
| positive |0x0000ffff | ffff00 |65535|16776960|
| negative | 0x8000ffff | ffff00 |-2147418113|16776960|
可以看到負值左移後變為正值了
右移
|type |原值(HEX)| shift後(HEX)|原值(DEC)|shift後(DEC)|
|-|-|-|-|-|
| unsigned | 0x0000ffff | ff |65535|255|
| positive |0x0000ffff | ff |65535|255|
| negative | 0x8000ffff | ff8000ff |-2147418113|-8388353|
可看到負值右移後還是負值，可知C語言中的 shift operator 是算術位移，有做sign extension
看完這些之後才發現還是不能解釋為什麼乘負數出來的結果和預期不符，才發現原來我忽略了 負數的 % (modulo operator)...
一樣去翻[*ISO/IEC 9899:1999*](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 找了一下才找到，6.6.5 Multiplicative operators
* When integers are divided, the result of the `/` operator is the algebraic quotient with any fractional part discarded.If the quotient `a/b` is representable, the expression `(a/b)*b + a%b` shall equal `a`.
* 也就是說當 `a%b `的時候因為`/`捨去小數部份，是`a - (a/b)*b`，因此若回去看程式，當m是負數的時候，`m%2`會是0或-1，所以當m是負值的時候if判斷就會為false，因為 !(m % 2 - 1) 要恰為1才會為true，導致ret永遠為0。
>上面的問題原因應該就是因為`m%2`不能分辨-1和1吧？
所以code改成
```C
int mul(int n, int m)
{
int ret = 0;
for (int c = 0; m; c++, m /= 2) {
if (!(m % 2 - 1)) ret += n << c;
else if (!(m % 2 + 1)) ret -= n << c;
}
return ret;
}
```
如此當跑for迴圈時，m為負數便會一直執行else if 或是不執行 ，m為正數時便會執行if或不執行。
想通之後才發現這種程式的運算方法和一個bit相乘累加到一個暫存器再位移，和以前上計算機組織提到乘法器的好像很像
## 第2週測驗題 第3題
考慮到某些實數的二進位表示形式如同 $0.yyyyy...$ 這樣的無限循環小數，其中 $y$ 是個 $k$ 位的二進位序列，例如 $\frac{1}{3}$ 的二進位表示為 $0.01010101...$ (y = `01`)，而 $\frac{1}{5}$ 的二進位表示為 $0.001100110011...$ (y = `0011`)，考慮到以下 y 值，求出對應的十進位分數值。
* y = `010011` => $\frac{19}{X1}$
* y = `101` => $\frac{5}{X2}$
* y = `0110` => $\frac{2}{X3}$
### 想法
當時看到這題都沒什麼想法，只記得好像以前國高中有記過十進位的循環小數轉分數的公式，但早就忘了為什麼了。
google後看到等比級數就突然想起來了，是利用無窮等比級數和的公式$\dfrac{a}{1-r}$
若是原本的十進位為
$0.0$$\overline{76}$
則可看成
=>$\frac{76}{10} \times(\frac{1}{100}+\frac{1}{10000}+\frac{1}{1000000}...)$
=>$\frac{76}{10} \times \frac{\frac {1}{100}}{\frac {99}{100}}$
=>$\frac {76}{990}$
同理，若是要算二進位則可推得若是
$0.yyyyy$，$y有k位$，則公比為$\frac{1}{2^k}$
==>$y \times (\frac{1}{2^k-1})$
$0.$$\overline{010011}$ ==>$\frac {19}{2^6-1}$ ==>$X_1$=63
$0.$$\overline{101}$ ==> $\frac {5}{2^3-1}$ ==>$X_2$=7
$0.$$\overline{0110}$ ==>$\frac {6}{2^4-1}$ ==>約分後得$X_3$=5
## 第3週測驗題 第1題
延續 [從 $\sqrt{2}$ 的運算談浮點數](https://hackmd.io/s/ryOLwrVtz)，假設 double 為 64-bit 寬度，考慮以下符合 IEEE 754 規範的平方根程式，請補上對應數值，使其得以運作：
```Clike
#include <stdint.h>
/* A union allowing us to convert between a double and two 32-bit integers.
* Little-endian representation
*/
typedef union {
double value;
struct {
uint32_t lsw;
uint32_t msw;
} parts;
} ieee_double_shape_type;
/* Set a double from two 32 bit ints. */
#define INSERT_WORDS(d, ix0, ix1) \
do { \
ieee_double_shape_type iw_u = { \
.parts.msw = ix0, \
.parts.lsw = ix1, \
}; \
(d) = iw_u.value; \
} while (0)
/* Get two 32 bit ints from a double. */
#define EXTRACT_WORDS(ix0, ix1, d) \
do { \
ieee_double_shape_type ew_u; \
ew_u.value = (d); \
(ix0) = ew_u.parts.msw; \
(ix1) = ew_u.parts.lsw; \
} while (0)
static const double one = 1.0, tiny = 1.0e-300;
double ieee754_sqrt(double x)
{
double z;
int32_t sign = 0x80000000;
uint32_t r, t1, s1, ix1, q1;
int32_t ix0, s0, q, m, t, i;
EXTRACT_WORDS(ix0, ix1, x);
/* take care of INF and NaN */
if ((ix0 & KK1) == KK2) {
/* sqrt(NaN) = NaN, sqrt(+INF) = +INF, sqrt(-INF) = sNaN */
return x * x + x;
}
/* take care of zero */
if (ix0 <= 0) {
if (((ix0 & (~sign)) | ix1) == 0)
return x; /* sqrt(+-0) = +-0 */
if (ix0 < 0)
return (x - x) / (x - x); /* sqrt(-ve) = sNaN */
}
/* normalize x */
m = (ix0 >> 20);
if (m == 0) { /* subnormal x */
while (ix0 == 0) {
m -= 21;
ix0 |= (ix1 >> 11);
ix1 <<= 21;
}
for (i = 0; (ix0 & 0x00100000) == 0; i++)
ix0 <<= 1;
m -= i - 1;
ix0 |= (ix1 >> (32 - i));
ix1 <<= i;
}
m -= KK3; /* unbias exponent */
ix0 = (ix0 & 0x000fffff) | 0x00100000;
if (m & 1) { /* odd m, double x to make it even */
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
}
m >>= 1; /* m = [m/2] */
/* generate sqrt(x) bit by bit */
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
q = q1 = s0 = s1 = 0; /* [q,q1] = sqrt(x) */
r = 0x00200000; /* r = moving bit from right to left */
while (r != 0) {
t = s0 + r;
if (t <= ix0) {
s0 = t + r;
ix0 -= t;
q += r;
}
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
r >>= 1;
}
r = sign;
while (r != 0) {
t1 = s1 + r;
t = s0;
if ((t < ix0) || ((t == ix0) && (t1 <= ix1))) {
s1 = t1 + r;
if (((t1 & sign) == sign) && (s1 & sign) == 0)
s0 += 1;
ix0 -= t;
if (ix1 < t1)
ix0 -= 1;
ix1 -= t1;
q1 += r;
}
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
r >>= 1;
}
/* use floating add to find out rounding direction */
if ((ix0 | ix1) != 0) {
z = one - tiny; /* trigger inexact flag */
if (z >= one) {
z = one + tiny;
if (q1 == (uint32_t) 0xffffffff) {
q1 = 0;
q += 1;
} else if (z > one) {
if (q1 == (uint32_t) KK4)
q += 1;
q1 += 2;
} else
q1 += (q1 & 1);
}
}
ix0 = (q >> 1) + 0x3fe00000;
ix1 = q1 >> 1;
if ((q & 1) == 1)
ix1 |= sign;
ix0 += (m << KK5);
INSERT_WORDS(z, ix0, ix1);
return z;
}
```
### 想法
當初在上課就覺得對浮點數並沒有很熟悉，之後雖然有回去有稍微練習一下，但感覺還是應該完整一下。
:::info
延伸題目: 解釋上述程式碼何以運作，並且改為 float (單精度) 版本，注意應該用更短的程式碼來實作
:::
## [因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1)心得及上課三週心得
* 看完文章真的很佩服作者這種對目標的執著和強大的執行力，從最基本的硬體機構到軟體的編寫都是嘗試自行製作，雖然最終為了繼續做下去還是在硬體上妥協，但是因為這種接觸、研究自己從沒碰過的領域真的是很難，何況現實與所學又有著很多差別，有許多現實因素要考慮。
* 以前在我們系上修過一門有關機器人的課程，分上下學期兩堂，我只修了上學期，課程目的是希望同學分組，最終各組能自己製作出簡易的機器人。在剛開始討論的時候就發現定了功能、目標，卻對要怎麼設計完全無法下手，上網想要學習，看一些現成的一些機器、機構等等的影片，感覺就只能"哇～太厲害了吧"，當時我們這組有個對機構比較了解、興趣就是手工自己幹出一些小工具的同學，當時討論問題就感覺知識落差很大，其他人可能一提出意見問他就馬上會被他打槍XD，最終課程我們這組幾乎沒做出什麼成果，只有一台能在水上跑然後向左向右轉躲避障礙物的看似小船的東西。在過程中我也有像作者一樣嘗試去學習焊電路在洞洞板上，當時自己在網路上看著影片學，實際動手起來真的是慘不忍睹，雖然只是很簡單很簡單的電路，但是焊接的一些小知識和技巧似乎真的很多，後來我決定拿幾個焊壞的洞洞板每一個洞都拿來練習XD，雖然成果還是不怎樣就是了。
* 我覺得整體的決策真的很重要，首先要花時間和金錢在哪個方向上，一步一步計畫、行動。決策錯了，努力錯了方向就是一整個浪費時間，但是這種決策的能力似乎只能靠經驗累積，至少我是幾乎完全沒有，常常做很多事情感覺都努力錯了方向，事倍功半。文章中下面有許多網友的回文也有許多人都覺得作者起初應該不用考慮一些限制 e.g.食用性之類的，應該以簡單的方式嘗試設計出整體的草模，看運行情況之後要進行修改再說，我也覺得蠻有道理的，但實際上我也不知道是好是壞，感覺作者這種作法也因此讓作者學習到許多不同的經驗。
* 文章中提到 jserv老師說的有一句話讓我印象深刻，「你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。」我對失敗的承受度也很差，甚至會為了避免努力後仍然失敗的結果而選擇放棄努力。
* 在實際設計出東西上，「取捨」似乎真的很重要，現實世界會用到的真的跟課本上所學的差了很多，我曾經以為是因為我讀的是「大學」而不是「科大」，但在我詢問了一些科大的朋友後，卻了解到了還是要自己動手去嘗試過後的經驗才對現實有所幫助。現實中的問題不像課本上僅僅只是一兩個條件的取捨，而是很多因素要考量，當出現一個bug也不只是單純上code出問題，而是很多地方都有可能是原因，然而一個人所學所知終究有限，這時候可能只能依賴團隊的力量了。
-----------------------
* 上了三週課程，發現自己對時間的規劃能力真的是很差，雖然找房子、換電腦、重灌、結果電腦打不開真的花了我不少時間，但是其實一週正常作息下應該還是有遠多於16小時的時間可以使用，卻都瑣碎的浪費掉了，總是另外挑幾天熬夜來看書、寫作業。
* 在查資料的過程中，才知道以前學的東西有多麼不扎實，也才知道自己原來和別人知識落差這麼大，很多新的東西要學的同時，學過的卻也無法掌握，實在是...，不過，一步一步查資料，慢慢從最基本的從一手的資料上弄懂，實在是很不一樣的感覺，比較不會再有不確定的答案，雖然也比較花時間，但我覺得很值得。
* 除了知識的落差，表達的能力也相當的不足，不只當不了理組，連文組都當不了，看其他同學的共筆都寫的很清楚有條理，自己嘗試寫過才知道對我來說有多困難，覺得自己已經懂了，但把他整理出來又花了更多時間，只是用打的、可以重複修改都已如此，難以想像要我口述會有多慘。
* 資訊工程領域的知識，似乎要一直去閱讀新的基礎規則，都是建構在別人設計出來的規範上運作，伴隨著規則一直更新，自己所要運用到的範圍也越來越廣泛，是永遠閱讀不完的大坑，儘管經驗有用，但似乎卻不像其它像是機械、電學領域那樣有用，機械、電學上的更新還是建構在物理知識上。感覺資訊領域會一直需要「砍掉重練」，軟體要一直去配合硬體改善，可能也只是我對這些領域也沒什麼了解就是了。
* 儘管每週的進度我都沒有趕完，我還是會嘗試在完成該週進度的條件下回去補完以前沒做完的進度，希望自己能有所成長。
## Reference
[*ISO/IEC 9899:1999*](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
Google Drive
Gist
Clipboard
Sign in with Wallet
