# 2019q3 Homework1(review) contributed by < `YenHengLin` > >作業系統:Ubuntu 18.04 LTS >作業系統類型：64 位元 ## 課前測驗第二題 ### 問題 考慮以下 C 程式可取得以 `sizeof(int)` 為 alignment 基礎的整數空間，也就是說，當 `sizeof(int)` 為 `4` 的時候: * 給定 `char arr[13];`，`INT_SIZE_OF(arr)` 要得到 `16`; * 給定 `short int s;`，`INT_SIZE_OF(s)` 要得到 `4` ```cpp #include <stdint.h> #define INT_SIZE_OF(n) \ ((sizeof(n) + sizeof(int) + X) & ~(sizeof(int) + Y)) ``` * 請求出 X 、 Y * 參考資訊: [Memory access and alignment](https://lwn.net/Articles/260832/) :::success 延伸題目: 解釋運作原理並在 GitHub 找出實際應用的程式碼 ::: ### 想法&解題 #### 4 的倍數 * 本題題目要求為 alignment 4，也就是 INT_SIZE_OF(n) 得到的値要是 4 的倍數，並且這個數要大於等於 sizeof(n) * 在 2 進為底下如果這個數為 4 的倍數，則它的最後兩位 bit 必為 0 * 4~10~ = 00000100~2~ * 8~10~ = 00001000~2~ * 12~10~ = 00001100~2~ * 16~10~ = 00010000~2~ * 透過 [bitwise operation](https://hackmd.io/@sysprog/By0MltO_m?type=view) ,我們可以知道想要清除某個 bit 我們可以用 ```c unsigned char b &= ~(1 << n); ``` 的方式將某個 bit 的位元清空 * 將以上的概念整合起來我們就可以知道，為了要得到 4 的倍數我們所要做的就是讓這個數的最後兩位 bit 要是 0，也就是清空最後兩位 bit 的値，寫成 bitwise operation 為 ```c unsigned char b &= ~(3); ``` * 3~10~ = 00000011~2~ * ~(3 ~10~) = 11111100~2~ * 由於 ==(0 or 1) & 0=0==，==(0 or 1) & 1 =自己==，所以我們可以透過 ==&=~(3)==，將最後兩位 bit 清空，而不動到其它位的 bit 所以我們最後推得 ==Y = -1== #### 大於等於 sizeof(n) * 4 的倍數可以透過清空 bit 解決這個問題，那還有一個問題沒解決，也就是我們要得到的値要大於等於 sizeof(n)，這一段比較難思考，所以我一開始是先用列舉法將 sizeof(n)= 1, 2, 3, 4 * 找出最小且大於等於 1 2 3 4 的數字會發現數字 4 會滿足上述列舉的 4 個數字。將最小的數字 1 加上 3 在去掉這個數的最後 2 位 bit，就會發現值為 4 * 將 2 3 4 數字都套入跟 1 一樣的操作 ==f(x)=(x+3)&~(3)==，將會發現都得到一樣的數字 4，這樣我們可以假定為了要得到大於等於 sizeof(n)的數，必須要加 3 * ==加上 3== 為我們的猜測，所以我們來看看加數字 3 在二進位底下到底是在做甚麼事 * 00000001~2~ + 00000011~2~ = 00000100~2~ * 00000010~2~ + 00000011~2~ = 00000101~2~ * 00000011~2~ + 00000011~2~ = 00000110~2~ * 00000100~2~ + 00000011~2~ = 00000111~2~ 透過上面的觀察我們終於了解到加數字 3 到底是甚麼樣的操作，它實際的操作就是只要它加上的數字的二進位碼在最後兩位 bit 有 1，它就會讓這個數字二進位碼的第二位 bit 加 1，也就是加上 4~10~。這樣確保在清掉最後兩位 bit 時，得到的值既是 4 的倍數又不會小於 sizeof(n)，而已經是 4 的倍數的值由於最後兩位 bit 是 0 所以加 3 後不會改變這個數的第二位 bit，當然清完後面兩位 bit 後就等於原本的值。所以最後我們可以確認說 ==X的值為 -1== ## 課程簡介和注意須知 page 9~10 ### code ```c #include <stdio.h> int main() { float sum = 0.0f; for (int i = 0; i < 10000; i++) sum += i + 1; printf("Sum: %f\n", sum); return 0; } ``` #### 想法 * 依照小學學的高斯求和公式得到 (1+10000)*10000/2=50005000 ，然而實際透過電腦跑就會發現得到的結果為 `Sum: 50002896.000000`，跟我們所想的不一樣 * 參考 [浮點數 float 累加方式求解](https://www.itread01.com/content/1501405444.html?utm_source=https://www.itread01.com/content/1501405444.html) 我們了解到為何會發生這樣的事，因為浮點數的讀取的方式跟我們一般的直觀的二進位系統不太一樣，它的數值讀取方式為底下所示 * 1 bit sign * 8 bits exponent * 23 bits fraction * 圖示: ![](https://i.imgur.com/546IW33.png) * 而這樣的讀取方式使得 float 值的加減法要進行底下的操作 * 兩數的 exponent 值必須先對齊，比較 exponent 大小，小的向大的對齊 * 如果 exponent 有變動，那 fraction 必須跟著改變，以符合原來的數值 * 改動完後的 fraction 做定點相加(減) * 將相加(減)的結果規則化，以符合 float 的儲存方式 * fraction 右移時丟式的數值位做 round * 判斷結果是否溢出 * 由於 exponent 必須要對齊的緣故，所以我們很可能會面臨一種情況，那就是數值相差很大的數在做相加(減)時由於小的數字要提升 exponent 以符合大的數字的 exponent ，而把 fraction 右移，結果就是失去了尾數部份的值，例如底下的 code ``` c #include <stdio.h> int main() { float sum = 0; sum+=1; sum+=50000000; printf("Sum: %f\n", sum); return 0; } ``` 照理來說執行的結果應該要為 50000001，然而實際的程式碼結果為 `Sum: 50000000.000000`，沒錯 1 的值就在 exponent 對齊的時候被丟棄了，現在我們可以理解到為何浮點數相加會產生誤差，因為我們在做兩個相差大的數字的加法。 ### 改進辦法(一) * 將一層 for 迴圈改成兩層 for 迴圈，內層先計算得到比較小的總和，再將這些總和加總起來 * code ```c #include <stdio.h> int main() { float sum = 0.0f; float temp = 0.0f; for (int i = 0; i < 100; i++) { temp = 0.0f; for (int j = i * 100; j < 100 * (i + 1); j++) { temp += 1 + j; } sum += temp; } printf("Sum: %f\n", sum); return 0; } ``` 得到輸出結果為 `Sum: 50004968.000000` ，說明準確度有明顯的上升，然而還是錯的答案，代表在做加法時兩數的差還是有點大，所以我作了以下的修正 * code 修正版 ```c #include <stdio.h> int main() { float sum = 0.0f; float tempa = 0.0f; float tempb = 0.0f; for (int i = 0; i < 10; i++) { tempb = 0.0f; for (int j = i * 10; j < (i + 1) * 10; j++) { tempa = 0.0f; for (int k = j * 100; k < 100 * (j + 1); k++) { tempa += k + 1; } tempb += tempa; } sum += tempb; } printf("Sum: %f\n", sum); return 0; } ``` 讓兩數相加時的差更少，終於得到對的輸出 `Sum: 50005000.000000`，然而這樣做有個缺點，就是邊界的判斷變得複雜，且不適用所有的情況，所以我們開始來思考有沒有其它更直觀的方式，來修正 float 所造成的誤差。 ### 改進辦法(二)-[Kahan's Summation algorithm](https://en.wikipedia.org/wiki/Kahan_summation_algorithm)