# 2019q3 Homework1 (review)
contributed by < `kaeteyaruyo` >
## 課前測驗第3題
考慮以下 C 程式碼:
```cpp
#include <stdbool.h>
bool func(unsigned int x) {
return x && ((x & (~x + 1)) == x);
}
```
可改寫為以下等價的程式碼:
```cpp
bool func(unsigned int x) {
unsigned int unknown = 0;
while (x && unknown <= 1) {
if ((x & Z) == 1)
unknown++;
x >>= 1;
}
return (unknown == 1);
}
```
請補完程式。
:::success
延伸題目: 舉出 abs 以外，透過 bitwise 操作將原有運算改為 const-time 實作的案例，應當解釋並探討應用場景。
:::
### 解題
首先需要先知道原本的`func`的作用是什麼，才可能根據語意來完成改寫的程式。以我腦內現有的知識，可以將原返回式化簡如下：
:::danger
工程人員儘量用「客觀推論」，避免說「以我腦內現有的知識」
:notes: jserv
:::
```cpp
x && ((x & (~x + 1)) == x)
= x && ((x & -x) == x) // C 語言中，整數以二補數的形式表示，因此 ~x + 1 = -x
```
由此算式可得知，`func`函數將在以下兩個條件皆為`true`的情況下返回`true`：
* `x`不是 0 時，因為在 C 語言中，所有的非 0 數都判定為 `true`
* `（x & -x）` 和 `x` 相等時
很顯然，問題在於第二條。（廢話）
:::danger
不要急著說「廢話」，論述是一點一滴前進
:notes: jserv
:::
快速列個表來觀察這個函數的output：
| x | x | -x | x & -x | output |
| - | ---- | ---- | ------ | ------ |
| 1 | 0001 | 1111 | 0001 | true |
| 2 | 0010 | 1110 | 0010 | true |
| 3 | 0011 | 1101 | 0001 | false |
| 4 | 0100 | 1100 | 0100 | true |
| 5 | 0101 | 1011 | 0001 | false |
| 6 | 0110 | 1010 | 0010 | false |
| 7 | 0111 | 1001 | 0001 | false |
| 8 | 1000 | 1000 | 1000 | true |
看起來這是個判斷此數是否為2的乘冪(power of 2)的函數。
根據[這篇討論](https://stackoverflow.com/questions/15395317/meaning-of-bitwise-and-of-a-positive-and-negative-number)當中 Mark Ransom 的回答，由於二補數表示中，某數的負數定義為`-n = ~n + 1`，所以
* 在`~n`中的LMB為 1 時，`+ 1`會造成該位數變成 0 ，然後往前進位一個 1
* 若被進位的位數也是 1 時，又會造成下一次的進位，直到遇到第一個 0 為止
* 造成進位連鎖停止的第一個 0 的位數會變成 1
* 在那之後的位數維持原樣
我們用以下算式作為範例：
```
~ 0101 0011 1000 0100 0000 0000 0000 0000
-----------------------------------------
1010 1100 0111 1011 1111 1111 1111 1111
+ 0000 0000 0000 0000 0000 0000 0000 0001
-----------------------------------------
1010 1100 0111 1100 0000 0000 0000 0000
| 沒進位的部份 |↑| 進位掉的部份 |
第一個 0
```
由於 and 運算只有在兩個運算元都是 1 時才會得 1，因此當`x & -x`時，我們如果將以上三個部份分別計算：
* 沒進位的部份：因為是反相得來的，如果在`x`中是 1 ，在`-x`中就是 0，得 0
* `~x`中第一個 0 的位數：在`x`當中，該位數是 1，在`-x`當中，因為上述第三點的關係，也會是 1，得 1
* 進位掉的部份：在`x`中全是 0，在`-x`中因為進位掉了也是 0，得 0
會發現只有`~x`中第一個 0，也就是`x`中第一個 1 的地方會得 1，由此可知，`x & -x`是一個用來偵測 x 中第一個 1 在哪裡的算式。而很恰巧的，2 的 n 次方以二進位表示，正好會是僅在左起第 n 位（從 0 開始）為 1 的數字，正好與`x & -x`的結果相同；而其他的數字都會包含至少兩個 1，不可能與`x & -x`的結果相同，因此可以得知:`x & -x == x`的功能，就是用來偵測一個正整數是否是 2 的乘冪。
但是因為這個算式在`x`為 0 的情況下也會回傳`true`，所以需要補上`x`不為 0 的檢查。
再來看到改寫後的<s>函數</s>，逐行註解如下:
:::danger
"function" 有兩種翻譯，一個是數學意義上的「函數」，另一個是對應於 sub-routine/sub-program 的「函式」，下方應翻譯為「函式」
:notes: jserv
:::
```cpp
// 有一個叫 func 的函數，吃一個非負整數 x 為參數
bool func(unsigned int x) {
// 用一個叫 unknown 的容器計數（我偷看下面知道的）
unsigned int unknown = 0;
// 重複以下動作
while (x && unknown <= 1) {
// 如果 x 與 Z and 為 1， unknown 累加一次
if ((x & Z) == 1)
unknown++;
// 然後把 x 往右捨去一位
x >>= 1;
}
// 直到 x 為 0，或 unknown 大於 1 為止
// 如果 unknown 只被累加一次，回傳 true ，否則回傳 false
return (unknown == 1);
}
```
* 觀察`while`迴圈的部份，可以猜想迴圈的功能是用來記錄`x`中 1 出現的次數（從最右邊檢查起，檢查完就向右捨去位數，直到沒有1為止）
* 最後回傳 1 出現的次數是否為一次的結果，符合 2 的乘冪的規則
* 因此，判斷式`(x & Z) == 1`的部份應用來檢查`x`的最低位數是否為1
綜合以上事實，可得出`Z = 1`
### 延伸題目
舉出 abs 以外，透過 bitwise 操作將原有運算改為 const-time 實作的案例，應當解釋並探討應用場景。
#### 大小寫轉換
##### 應用場景
英文字母的大小寫轉換是在處理字串時很常用到的功能。一般來說，我們可以直接呼叫 <type.h> 函式庫當中的`toupper()`和`tolower()`函數，而他們在 [Linux 函式庫](https://github.com/torvalds/linux/blob/master/include/linux/ctype.h)中的實作方法如下：
```cpp
static inline unsigned char __tolower(unsigned char c)
{
if (isupper(c))
c -= 'A'-'a';
return c;
}
static inline unsigned char __toupper(unsigned char c)
{
if (islower(c))
c -= 'a'-'A';
return c;
}
#define tolower(c) __tolower(c)
#define toupper(c) __toupper(c)
```
但如果使用 bitwise operation，其實可以有 branchless 的作法：
```cpp
char tolower(char c){
return (c | ' ');
}
char toupper(char c){
return (c & '_');
}
```
實測結果（大小寫的 A 到 Z 我都測過了，但是銀幕塞不下所以只放前 5 個）：
:::danger
文字訊息==不要==用圖片去展現
:notes: jserv
:::
##### 原理
英文字母在 [ASCII 編碼](https://zh.wikipedia.org/wiki/ASCII)中的排列是有經過設計的，以下表格節錄前5個英文字母：
| case | A / a | B / b | C / c | D / d | E / e |
| ---- | ----- | ----- | ----- | ----- | ----- |
| upper | 01**0**0 0001 | 01**0**0 0010 | 01**0**0 0011 | 01**0**0 0100 | 01**0**0 0101 |
| lower | 01**1**0 0001 | 01**1**0 0010 | 01**1**0 0011 | 01**1**0 0100 | 01**1**0 0101 |
根據上表規律(以及維基百科中的完整表格)，可以觀察出來，大寫字母與小寫字母唯一的差別在於左邊數來第 3 位數，大寫為 0，小寫為 1。因此，只要透過遮罩來 set / clear 這個 bit，就可以完成大小寫的轉換了。
`tolower（）`比較簡單，要將一個字母（無論大小寫）轉為小寫字母，我們需要 set 他的第 3 個 bit。 set bit 最簡單的方式就是跟一個 1 or，也就是：
```
0100 0001
| xx1x xxxx
-----------
0110 0001
```
但是我們也需要保證 or 完之後其它所有的 bit 都不會被變更。我們知道任何數與 0 or 之後依然會是那個數，所以遮罩剩下的部份以 0 填充即可：
```
0100 0001
| 0010 0000
-----------
0110 0001
```
`0010 0000`剛好是空白鍵`' '`的 ASCII code，因此，任何英文字母與`' '` or 後都會被轉換為對應的小寫。
`toupper（）`稍微複雜一點。要將一個字母（無論大小寫）轉為大寫字母，我們需要 clear 他的第 3 個 bit。 clear bit 最簡單的方式是跟一個 0 and，也就是：
```
0110 0001
& xx0x xxxx
-----------
0100 0001
```
但是我們也需要保證 and 完之後其它所有的 bit 都不會被變更。我們知道任何數與 1 and 之後依然會是那個數，所以將遮罩剩下的部份以 1 填充：
```
0100 0001
| 1101 1111
-----------
0110 0001
```
問題是，傳統 ASCII code 只有 128 個字元，也就是只用了 7 個 bit，剩下 MSB 被設為 0。因此遮照應該改為
```
0100 0001
| 0101 1111 // 反正大家的 MSB 都是 0，沒差拉
-----------
0110 0001
```
`0101 1111`剛好是底線`'_'`的 ASCII code，因此，任何英文字母與`'_'` and 後都會被轉換為對應的大寫。
#### 我自己的經驗
##### 應用場景
在我的畢業專題當中，有一段程式邏輯是這樣的：
* 當一個節點顯示時，與之相連且另一端的節點有顯示的邊必須被顯示
* 當一個節點隱藏時，與之相連且另一端的節點不顯示的邊必須被隱藏
我原本的寫法是這樣
```javascript
if(node.visible)
node.links.filter(link => link.source.visible && link.target.visible).forEach(link => { link.visible = true; });
else
node.links.filter(link => !(link.source.visible && link.target.visible)).forEach(link => { link.visible = false; });
```
（實際的情況更複雜一點，這是簡化的版本）
但因為某些原因，這段程式碼需要重複出現三次，每一次`node`的地方會是不同的東西。重複的程式碼一直出現會害我很想把他們包成function，所以我把他改寫成：
```javascript
const display = (node) => {
node.links.filter(link => !node.visible ^ (link.source.visible && link.target.visible)).forEach(link => { link.visible = node.visible; });
}
```
##### 原理
這個問題可以被簡化為：
```javascript
if(a == true)
b.filter(c => condition).forEach(c => { c = true; });
else
b.filter(c => !condition).forEach(c => { c = false; });
```
* 當 a 為真時，我需要正常的 condition 結果
* 當 a 為假時，我需要反相的 condition 結果
* 最後將 c 設為跟 a 一樣
用表格來說就是
| a | condtion | result |
| ----- | -------- | ------ |
| true | true | true |
| true | false | false |
| false | true | false |
| false | false | true |
如果光是 NAND 或 NOR 就可以組出任意功能的邏輯閘，那我相信一定有簡單的布林運算可以在一個判斷式以內達成這樣的效果。
仔細觀察發現，這個表格的行為很相似於 XOR 閘：
| a | condtion | a ^ condition |
| ----- | -------- | ------------- |
| true | true | false |
| true | false | true |
| false | true | true |
| false | false | false |
只要把結果反相就行了，不管是反相整個算式還是其中一個運算元都有一樣效果：
| a | condtion | ！a ^ condition |
| ----- | -------- | -------------- |
| true | true | true |
| true | false | false |
| false | true | false |
| false | false | true |
現在 12 行 code 變成 3 行 10 個字的 code 了，很開勳。（？）
## 課程簡介第 11 頁
考慮以下程式碼：
```cpp
#include <stdio.h>
int main() {
return (*******puts)("Hello");
}
```
能否編譯並執行呢？若可，為什麼呢？
### 解題
這個程式可以成功編譯，也可以成功執行，他的輸出是：
```shell
$ ./a.out
Hello
```
為什麼`puts`前面放那麼多個`*`也沒關係呢？根據 [C99 的規格書第 6.3.2.1 節 *Lvalues, arrays, and function designators* 第四條](http://port70.net/~nsz/c/c11/n1570.html#6.3.2.1p4):
> A function designator is an expression that has function type. Except when it is the operand of the sizeof operator, the _Alignof operator, or the unary & operator, a function designator with type "function returning type" is converted to an expression that has type "pointer to function returning type".
當中提到的 **function designator**，中文可直翻為「函數命名符」，簡單來說就是這個 function 的名字。上面這段話大概的意思是
> 除非函數的名字作為 sizeof, _Alignof 或是 & 運算元的運算子，否則其型態都會自動從「函數的返回型態」轉換為「指向函數返回型態的指標」。
由此可知，當函數名字前面什麼都沒有寫的時候，其型態是「指向函數返回型態的指標」。因此`puts`的型態，是一個指標。
在指標前面放上`*`，可以取得指標所指向的記憶體位址內含的值，這個行為叫作反參照（dereference），例如：
```cpp
int i = 10;
int *p = &i;
printf("%p\n", p); // Print address of i
printf("%d\n", *p); // Dereference p to get value of i
```
但是由於上述的規定，當你 dereference 一個 function name （型態為指標）的時候，實際上還是會得到指向這個 function return type 的指標，也就是`puts = *puts = **puts = **.....*puts`，不管 dereference 幾次，都只寫`puts`是一樣的意思。
因此我們可以得知，以上程式其實跟以下程式是等價的：
```cpp
#include <stdio.h>
int main() {
return puts("Hello");
}
```
其次，為什麼 return 這個表達式沒有問題呢？
根據 [Cplusplus.com 的 reference](http://www.cplusplus.com/reference/cstdio/puts/)，`puts（）`函數的原型如下：
```cpp
int puts ( const char * str );
```
由此可知，`puts()`的 return type 是一個整數，實測了之後發現這個整數是成功印出的字數。
因此，其實這個函式真正的意思是：
```cpp
#include <stdio.h>
int main() {
puts("Hello")
return 6; // 'H', 'e', 'l', 'l', 'o', '\0'，一共 6 個字元
}
```
透過`echo $?`可以看到 Linux kernel 收到的 exit status code，完整實測如圖：
雖然的確可以成功編譯也可以成功執行，但好像不能說是正常的執行結束呢~
:::danger
工程人員說話要精準，避免用「好像不能說是正常的執行結束」這類詞彙
:notes: jserv
:::
## 課程簡介第 9 頁
考慮以下程式碼：
```cpp
#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;
}
```
你覺得會輸出什麼？
### 解題
我一直很好奇是加到什麼時候開始不準的，所以我改寫了這個程式：
```cpp
#include <stdio.h>
int main() {
float sum = 0.0f;
int s = 0;
for (int i = 0; i < 10000; i++){
sum += i + 1;
s += i + 1;
printf("+ %d: %d -> %.0f\n", i, s, sum);
}
printf("Sum: %f\n", sum);
return 0;
}
```
節錄他開始不準的那一段輸出如下：
```
...
+ 5789: 16764945 -> 16764945
+ 5790: 16770736 -> 16770736
+ 5791: 16776528 -> 16776528
+ 5792: 16782321 -> 16782320
+ 5793: 16788115 -> 16788114
+ 5794: 16793910 -> 16793908
+ 5795: 16799706 -> 16799704
+ 5796: 16805503 -> 16805500
...
```
在 5792 行，原本應該是 16782321 卻變成了 16782320，並且從這行開始之後的數字都是偶數。
為什麼會這樣呢？回想起計組時學到的 IEEE 754 floating point number 的規格：
| sign(1 bit) | exponent(8 bits) | mantissa(23 bits) |
|-|-|-|
| 0 | 10000000 | 10000000000000000000000 |
這個數字是 3，因為轉換的公式如下：
$$ value = sign \times (1 + mantissa) \times 2 ^ { exponent - 127 } $$
所以
$$ +1 \times (1 + \frac{1}{2}) \times 2 ^ {128 - 127} = 3 $$
雖然浮點數理論上可以表示很大和很小的數（因為指數位可以高達 2^+-128 = 10^+-38 這麼多位），但實際上因為單精度的 mantissa 位數有限，到了某一個數字之後就會開始有失真的現象。那會是哪個數字呢？
以十進位為例，如果今天有個十進制的浮點數表示法，其 mantissa 只有三位：
```
0001 = 1.00 * 10 ^ 0
0002 = 2.00 * 10 ^ 0
...
0023 = 2.30 * 10 ^ 1
...
0145 = 1.45 * 10 ^ 2
...
0999 = 9.99 * 10 ^ 2
1000 = 1.00 * 10 ^ 3
1001 = 1.00 * 10 ^ 3
...
```
可以發現，因為三位數的 mantissa 只有三位的有效位數，因此 1001 的最後一個 1 無法有效保存，就被丟掉了，從 10 ^ 3 = 1000 開始的數字，每 10 個才有一個是對的。
同樣道理用在二進制：
```
0001 = 1.00 * 2 ^ 0
0010 = 1.00 * 2 ^ 1
0011 = 1.10 * 2 ^ 1
...
0111 = 1.11 * 2 ^ 2
1000 = 1.00 * 2 ^ 3
1001 = 1.00 * 2 ^ 3
```
在超越了有效位數可以表達的數字之後，每兩個數字才會有一個是對的，數字愈大，失真的範圍會愈大。而最後一個不會失真的數字，就是 2 ^ 24 = 16777216。（因為二進制浮點數的小數點前面那個數字一定是 1， matissa 只記錄小數點後的尾數，所以有效位數是 23 + 1 = 24 位）使用 IEEE 754 規範的浮點數表示法來表示整數，在 16777216 這個數字之後，就沒有辦法精確的表示每一個數字了。而 50005000 和 50002896 之間的差距，就是每加上一個數字就少一點，逐漸累積起來的。
雖然使用第 10 頁的方法記錄誤差改善精確度可以有一點點幫助，但是隨著數字越來越大，有效位數與真實數字的位數差距越來越大，改善精確度的效果依然有限。要徹底解決這個方法，除了使用unsign long進行運算以確保整數的精確表示，要對抗 overflow 的問題就只能用大數運算（以 array 儲存超過 10 位數的大數字）解決了。
:::danger
避免說「可以有一點點幫助」，儘量使用客觀事實和量化。另外，在訊號處理的情境中，要提升每個儲存單位的空間意味著成本和頻寬大幅地增加，所以工程範疇已有許多手法去改善精準度，這也是本題著重的議題。
:notes: jserv
:::
## 參考資料
- 課前測驗第 3 題
- [Meaning of bitwise and(&) of a positive and negative number? - Stack Overflow](https://stackoverflow.com/questions/15395317/meaning-of-bitwise-and-of-a-positive-and-negative-number)
- [10 cool bitwise operator hacks and tricks every programmer must know - Codeforwin](https://codeforwin.org/2018/05/10-cool-bitwise-operator-hacks-and-tricks.html)
- [linux/ctype.h at master · torvalds/linux - Github](https://github.com/torvalds/linux/blob/master/include/linux/ctype.h)
- [ASCII - Wikipedia](https://zh.wikipedia.org/wiki/ASCII)
- 課程簡介第 11 頁
- [How does dereferencing of a function pointer happen? - Stack Overflow](https://stackoverflow.com/questions/2795575/how-does-dereferencing-of-a-function-pointer-happen)
- [6.3.2.1 Lvalues, arrays, and function designators - ISO/IEC 9899:201x Committee Draft April 12, 2011 N1570](http://port70.net/~nsz/c/c11/n1570.html#6.3.2.1p4)
- [puts - C++ Reference](http://www.cplusplus.com/reference/cstdio/puts/)
- 課程簡介第 9 頁
- [IEEE 754 - Wikipedia](https://zh.wikipedia.org/wiki/IEEE_754)
- [Which is the first integer that an IEEE 754 float is incapable of representing exactly? - Stack Overflow](https://stackoverflow.com/questions/3793838/which-is-the-first-integer-that-an-ieee-754-float-is-incapable-of-representing-e)
Sign in with Wallet
Connect another wallet