# 2024q1 Homework4 (quiz3+4)
contributed by < `yenslife` >

$ uname -a
Linux lima-default 6.5.0-25-generic #25-Ubuntu SMP PREEMPT_DYNAMIC Wed Feb  7 15:18:19 UTC 2024 aarch64 aarch64 aarch64 GNU/Linux
$ lscpu
Architecture:           aarch64
  CPU op-mode(s):       64-bit
  Byte Order:           Little Endian
CPU(s):                 4
  On-line CPU(s) list:  0-3
Vendor ID:              0x00
  Model name:           -
    Model:              0
    Thread(s) per core: 1
    Core(s) per socket: 4
    Socket(s):          1
    Stepping:           0x0
    BogoMIPS:           48.00
    Flags:              fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 asimddp sha512 asimdfhm d
                        it uscat ilrcpc flagm sb paca pacg dcpodp flagm2 frint
NUMA:
  NUMA node(s):         1
  NUMA node0 CPU(s):    0-3

## 從 Revolution OS 看作業系統生態變化

[link](https://youtu.be/vWwvh3036Fw?si=eC_fmXJmQ4x9iMvR)

## CS:APP 第 2 章教材閱讀

[教材](https://hackmd.io/@sysprog/CSAPP-ch2)

### 第一部分
[影片](https://youtu.be/wb2u59QF2iY?si=20eisNzF9-tHEjaD)

#### 基本
Unsigned number：$B2U(X) = \sum_{i=0}^{w-1}{x_i\cdot2^i}$
Signed number (Two's complement)：$B2T(X) = -x_{w-1}\cdot2^{w-1}+\sum_{i=0}^{w-1}{x_i\cdot2^i}$

其中 w 是位數的意思。

$UMAX = 0$ , $UMIN = 2^w-1$

$TMIN = -2^{w-1}$ , $TMAX = 2^{w-1} - 1$

$UMAX = 2 \cdot TMAX - 1$

二補數轉換成十進位：教科書常用將取一補數之後的結果加一的方法來取得二補數，這邊教材提供我一個新理解。二補數的 MSB 是 signed bit，也可以理解成最高為元代表的冪取複數，然後相加，請看以下範例。


在 C 語言中，可以透過 `#include<limit.h>` 來取得最大最小值

Unsigned 和 Signed number 之間的關係，可以發現正數和負數的值都朝同一個方向變大。

| X | $B2U(X)$ | $B2T(X)$ |
| ---- | -------- | -------- |
| 0000 | 0 | 0 |
| 0001 | 1 | 1 |
| 0010 | 2 | 2 |
| 0011 | 3 | 3 |
| 0100 | 4 | 4 |
| 0101 | 5 | 5 |
| 0110 | 6 | 6 |
| 0111 | 7 | 7 |
| 1000 | 8 | -8 |
| 1001 | 9 | -7 |
| 1010 | 10 | -6 |
| 1011 | 11 | -5 |
| 1100 | 12 | -4 |
| 1101 | 13 | -3 |
| 1110 | 14 | -2 |
| 1111 | 15 | -1 |

邏輯位移 (Logical shift) 和算術位移 (Arithmetic shift) 的意義：前者補 0；後者補上 Signed bit。以前只是把算術位移會複製 MSB 的特性背下來，現在知道這麼做是為了維持正負數的性質。算術位移可以應用在判斷正負號上 (`x >> 31` if x is integer)，因為 **gcc 的實作是算術位移**。觀察下圖 MSB 的變化。


若 n 是有號 32-bit 整數
- `n >> 31` 相當於 `n >= 0 ? 0 : -1`
- `abs(n)` 等同於 `((n >> 31) ^ n) - (n >> 31)`
- 當 n 是負數時:
`n >> 31` 是 -1; -1 以 2 補數表示為 `0xFFFFFFFF`; `n ^ (-1)` 等同於 **1 補數運算**; 最後再減 -1，得到 2 補數運算的值
- 如果將 -1 右移，不會得到 0 而是會得到 -1

#### 轉換
負值的有號數轉換成無號數可能會比原本的大，如下圖。

C 語言中，有 "U" 後綴的數值表示 unsigned number

無號數及有號數進行運算時，**有號數會被強制轉型成無號數**

無號數意外結果的例子，會造成無窮迴圈，因為無號數不小於 0

unsigned i; 
for (int i = n - 1 ; i - sizeof(char) >= 0; i--)
    a[i] += a[i + 1];

另一個例子，因為 sizeof 的結果是無號數，導致無窮迴圈

#define DELTA sizeof(int)
int i;
for (i = CNT; i-DLETA >= DELTA; i -= DELTA)
    ...

### 第二部分

[影片](https://youtu.be/cGjjDea7i8g?si=5eEe-fLKzO0goO5E)

#### 微妙操作

用 xor 來判斷有沒有 overflow (正數加正數的結果為負；負數加複數的結果為正)

long a, b, x;
x = a + b;
if ((x ^ a) >= 0 || (x ^ b) >= 0) // 沒有溢位才能繼續


三種可能性


乘以二是 `>>`，除以二是 `<<`，正負號都可以用 (gcc)

- `~x + 1 == -x` ：就是二補數
- `~-x == --x`
- `-~x == ++x`
- `~0 == -1`
- `~0 + 1` == 0

原理如下圖

`-1 < 0U` 為 False，因為有號數被轉型成無號數了

#### Unsigned 迴圈寫法

- 盡可能使用 `size_t`，不論使用的機器是什麼都會自動變成 word size 的 unsigned 類型。
- 使用 `<` 而不是 `>= 0`
- `0 - 1 == UMax`

#### Byte Ordering

記憶體位置由 byte 為單位來排序，需要區分 Big endian, Little endian


#### 動腦時間
規則：回答以下問題，左邊是條件，右邊是要判斷是否 always true？若至少一種條件不為 true 則為 false；如果沒有右邊的部分就直接判斷左邊是否為 always true。考驗自己對 overflow 可能性的判斷

第一題就是當 `x < 0`，`(x*2) < 0` 是否 always true。

`(x | -x) >> 31 == -1` 有一個反例：`x = 0`

### 第三部分

[錄影](https://youtu.be/cvE39UfP74Q?si=DJ947wukxmmPCcq2)

#### 浮點數

二補數的小數表示方法與「浮點數」是不一樣的。後者利用類似科學記號表示方法。

- 二補數小數：101.11 = 4 + 1 + 0.5 +0.25

為什麼要這樣呢？為了讓能表示的值更多，如果用原本的方法只能表示 $x/2^k$ 種可能。

浮點數標準：IEEE 754

$v = (-1)^sM 2^E$
$E = exp-Bias$


兩種 Special case，當 exponent 為：
- 00000000000 = 0x000 當尾數為 0 時為 ±0，尾數不為0時為非正規形式的浮點數。

- 11111111111 = 0x7ff 當尾數為 0 時為 ∞，尾數不為 0 時為 NaN。


轉換方式


為什麼要減掉 Bias？參考 [stack overflow 上的回答](https://stackoverflow.com/questions/2835278/what-is-a-bias-value-of-floating-point-numbers)
>If you used a twos-complement representation for the exponent, a small positive number (i.e., with a negative exponent) would look like a very large integer because the second MSB would be set. By using a bias representation instead, you don't run into that -- a smaller exponent in the floating point number always looks like a smaller integer.

Denormalize 和 normalized 的 exp 有些微不同 (下圖是 8 bits 的例子)