# 小數的儲存

###### tags: `Competitive Programming Note`

本文已停止更新，新版請至 [WiwiHo 的競程筆記](https://cp.wiwiho.me/)

## IEEE 754

浮點數（也就是小數）的儲存方式是由 [IEEE 754](https://zh.wikipedia.org/wiki/IEEE_754) 來規範。

簡單來說，浮點數是用類似科學記號的方式來儲存，只是換成二進位而已。用來儲存一個浮點數的記憶體由高位（左）到低位（右）被分成三段：
- **符號位**，只佔一個位元，`0` 表示此數為正，`1` 表示此數為負。
- **指數域**，實際表示的值是指數域儲存的值減去**指數偏移量**，通常 $k$ 位指數域的偏移量會是 $2^k-1$。
- **小數域**，表示一個介於 $[(1)_2, (10)_2)$ 的小數，因為我們知道這個小數的個位數字是 $1$，這也是唯一在小數點前的數字，所以不需要儲存它，因此這裡只儲存**小數點後的位數**。

若指數域所表示的指數值是 $n$，而小數域表示的值是 $f$，那麼這個浮點數是：
$$\pm n \times 2^f$$
至於是正或負，依符號位而定。並且 $n \in [(1)_2, (10)_2) = [(1)_{10},(2)_{10})$。

在指數域的部分，大家都知道科學記號的指數可能是負的，但這裡並不是按二補數的規則來處理正負，而是規定一個「指數偏移量」，將欲表示的指數加上指數偏移量後，才是儲存在記憶體裡的數字。若指數偏移量是 $b$，且指數域有 $k$ 個位元，則可表示的指數範圍是 $[-b+1, 2^k-b-2]$，至於 $-b$ 和 $2^k-b-1$ 被用作特殊用途，等等會介紹。

因為小數域的長度是有限的，但小數有無限小數，無限小數中又有循環小數和無理數，因此會發生不精確的問題，造成計算和判斷上的錯誤，遇到這種狀況有這幾種辦法：
- 盡量不要用到小數，需要做運算的話，如果不需要做到太多難做的操作（例如乘法就是很簡單的操作），可以先用分子分母分開存的方式來計算，要輸出的時候再換成小數就好。
- 判斷一個浮點數是否等於一個值的時候，允許一個誤差範圍（相差小於一個極小的數），例如：

    double a = /*...*/;
    if(a == 0){/*...*/}

改成

    double a = /*...*/;
    if(fabs(a - 0) < 1e-9){/*...*/}

因為浮點數利用科學計號的方式儲存一個數，因此它除了可以表示分數以外，也可以表示一個極大的整數，但要注意它的有效位數並不比 `long long` 之類的整數結構來得長。

|資料型態|指數域長度（bit）|指數偏移量|小數域長度（bit）|
|------|-----|-----|----|
|float|8|127|23|
|double|11|1023|52|

## 特殊值

前面有提到當 $k$ 位指數域的指數偏移量是 $b$ 時，$-b$ 和 $2^k-b-1$ 用於表示特殊值，而特殊值如下：

### 零與負零
指數為 $-b$ 的浮點數，符號位為正表示 $0$，為負則為 $-0$。因為一般小數域只儲存小數點後的位數，也就是自動默認小數點前有一個 $1$，因此 $0$ 這個數字必須要用特殊值來存。至於正零跟負零唯一的差別在於負零輸出的時候會有負號，我不知道要怎樣才會算出負零就是了。

### 正負無窮
指數為 $2^k-b-1$，小數域為 `0`，符號位為正表示正無窮，為負表示負無窮，需要它的話，在 C++ 中可以用 `INFINITY` 來得到，它在 `math.h` 裡面，只是在競程上沒啥用途，頂多就是除以 $0$ 會出現無窮，可以幫你 debug。

### NaN
Not a Number 的縮寫，指數為 $2^k-b-1$，小數域不是 `0`，在反三角函數丟一些超出定義域的數字時會跑出這東西。