# 整數的儲存
###### tags: `Competitive Programming Note`

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

在數學上，表示負數很簡單，就加個負號就好了。那在電腦中該怎麼表示負數？

最簡單的方式是用最高位元來表示正負號，0 代表正，1 代表負，像是如果用 8 個位元來表示一個數，$-5$ 就是 `1000 0101`，$-3$ 就是 `1000 0011`，但這樣會發生一個問題，就是表示 $0$ 有兩種方式：不管最高位是 `1` 或 `0`，只要其他位都是 `0`，這樣它就是表示 $0$，所以勢必需要另一個方法來有效利用空間。

## 補數和二補數

將一個二進位數字的 0、1 互換後，就可以得到它的補數，例如（以 8 位元為例）：
`0000 0001` 的補數是 `1111 1110`
`0101 1010` 的補數是 `1010 0101`
在 C++ 中，`~` 這個運算子就是用來做這件事情。

接下來，把補數加 $1$，如果進位到超出範圍（像剛剛的例子都是 8 位元），稱為**溢位**，就把超出的部分捨去，這樣就得到了一個數的二補數，例如（以 8 位元為例）：
`0000 0001` 的補數是 `1111 1110`，二補數是 `1111 1111`
`0101 1010` 的補數是 `1010 0101`，二補數是 `1010 0110`
`0000 0000` 的補數是 `1111 1111`，**加 1 後是** `1 0000 0000`，二補數是 `0000 0000`
`1000 0000` 的補數是 `0111 1111`，二補數是 `1000 0000`

這就是目前最常見的電腦儲存有號（正負）整數的方式，一個數的二補數所表示的就是它的相反數，例如（以 8 位元為例）：$3$ 的二進位是 `0000 0011`，二補數是 `1111 1101`，那麼 `1111 1101` 所表示的值就是 $-3$。

顯而易見地，如果我們用 $k$ 位元儲存一個數，那麼我們可以儲存 $2^k$ 種數字，然後我們各分一半給正數（含 $0$）和負數，所以扣除掉 $0$，可以表示 $2^{k-1}-1$ 個正數，因此最大正數就是 $2^{k-1}-1$，然後還有 $2^{k-1}$ 個負數，因此最小負數是 $-2^{k-1}$。

所以說，C++ 中常見的整數型態範圍是這樣：
（`unsigned` 開頭的是**無號**的，也就是只有 $0$ 和正數，因此 $k$ 位元的無號整數最大值是 $2^k-1$）
|型態|byte 數|最大整數|最小整數|
|---|---|---|---|
|char|1|127|-127|
|short|2|32767|-32768|
|int|4|2147483647|-2147483648|
|long long|8|9223372036854775807|-9223372036854775808|
|unsigned char|1|255|0|
|unsigned short|2|65535|0|
|unsigned int|4|4294967295|0|
|unsigned long long|8|18446744073709551615|0|

:::info
一般只會用到 `int` 和 `long long` 與它們的 `unsigned` 版本，我會建議大概記一下這些的範圍，像是 `int` 的最大值大約是 $2 \times 10^9$、`long long` 的最大值大約是 $9 \times 10^{18}。$
:::

接下來，有個特殊狀況，就是有兩個數取二補數後會跟原本一樣，這兩個數分別是 $0$ 和最小整數。

很顯然地，$0$ 的二進位就是每一位都是 `0`，而它的補數是每一位都是 `1`，再加一後顯然會溢位，所以 $0$ 的二補數還是 $0$，不過這也很剛好，$0$ 的相反數本來就是 $0$。

至於最小整數，是除了最高位是 `1`，其他都是 `0`，它的補數是除了最高位是 `0`，其他都是 `1`，加一後就進位，變回去最高位是 `1`，其他是 `0` 了，正好最小整數的絕對值比最大整數的絕對值多 $1$，所以最小整數的相反數必定會超過最大整數，因此不可能透過取二補數來得到最小整數的相反數。

接下來會有一些證明，先說明一件事，二進位值都可以用一個十進位無號數來表示，即使我們本來想要它是表示一個有號數，它還是可以當作一個無號數，也就是用一般的方式去看它表示的值，例如：八位元 `1110 0011` 是有號數 $-29$，也可以是無號數 $227$，然後這兩個數有一個關係：若這兩個數分別是 $a$ 和 $b$，然後位元數是 $k$，那麼 $a \equiv b \pmod{2^k}$（模除取正數），證明如下（$a \geq 0$ 時 $a=b$，所以不需要證）：

> **證明 $k$ 位元的二進位值所表示之有號數 $a$（$a<0$） 及無號數 $b$ 滿足 $a \equiv b \pmod{2^k}$：**
> $a=-(2^k-1-b+1)=-2^k+b$
> $a \bmod 2^k = b$
> $b < 2^k$，故 $b \bmod 2^k = b$
> 得 $a \equiv b \pmod{2^k}$

再特別說明一下 $a=-(2^k-1-b+1)$ 這個部分，這個二進位值的補數表示成無號數是 $2^k-1-b$，再加 $1$ 就是二補數了，因為 $a$ 是負數，所以先找到它的相反數，比較好得到 $a$。還有一個特例在，如果 $a=-2^{k-1}$，也就是 $a$ 是最小整數的話呢？為什麼取二補數還是可以找到它的相反數？我們知道有號最小整數的二進位值是除了最高位是 `1`，其他都是 `0`，也就是說用無號數表示是 $2^{k-1}$，用剛剛的方法取二補數會得到：$2^k-1-2^{k-1}+1=2^k-2^{k-1}=2^{k-1}$，完全沒變，但最小整數恰好是 $-2^{k-1}$，所以如果用這個邏輯（以無號數的想法來看，剛剛說「不能得到相反數」是以有號數的想法），我們還是可以找出它的相反數的，而且我們得到一個結論，若一個 $k$ 位元二進位值所表示的無號數是 $b$，則可以這樣得到它的二補數所表示的無號數 $c$：
$$c=2^k-b$$

接下來來證明一件事：取二補數得到的值可以當作相反數，這必需滿足一個條件，就是對二補數再取二補數要是本來的數。**如果接下來沒有特別說明，則「二進位值 $a$」 的 $a$ 是指該二進位值所表示的無號數。**

> **證明 $k$ 位元的二進位值 $a$ 之二補數為 $b$，且 $b$ 之二補數為 $a$：**
> $b=2^k-a$
> $b$ 之二補數為 $2^k-b=2^k-(2^k-a)=a$

如果證明都看不懂也沒關係，記得結論就好：
- $k$ 位元可以表示的有號數範圍為 $[-2^{k-1}, 2^{k-1}-1]$
- $k$ 位元可以表示的無號數範圍為 $[0, 2^k-1]$
- $k$ 位元的同個二進位值所表示的有號數 $a$ 和無號數 $b$ 滿足 $a \equiv b \pmod{2^k}$
- $0$ 和最小整數取二補數後不變
- $k$ 位元二進位值 $a$ 的二補數是 $2^k-a$

## 二補數的加減運算

在討論完怎麼儲存一個整數後，來討論怎麼做運算。最基本的運算當然是加和減了，如果是兩個非負整數相加，那顯然很簡單，就加起來，再處理一下進位就好，但是在二補數系統下，會發生一個問題：如果數字太大，進位到最高位甚至超過怎麼辦？一樣用 8 位元來舉例，如果要把 `0110 0000`（$96$）和 `0100 0000`（$64$）相加，我們希望得到的結果是 $160$，然而這顯然大於最大整數，也就是 $2^7-1=127$ 了，實際上把它們的二進位值加起來，會得到 `1010 0000`（$-96$），所以這是一件很需要注意的事。

除了正數，還有負數。在數學上，$a-b=a+(-b)$，那在二補數系統上也可以這麼做嗎？答案是可以，如果你有兩個整數 $a$ 和 $b$，要計算 $a-b$ 時，找出 $b$ 的二補數後再與 $a$ 相加，這樣會是對的，接下來要證明這件事：就像上面的證明一樣，「二進位值 $a$」中的 $a$ 是指某一二進位值所表示的無號數，然後，我們有兩個 $k$ 位元的二進位值 $a$ 和 $b$，它們所表示的有號數是 $c$ 和 $d$，且 $c$、$d$ 可以是正數，也可以是負數，然後我們必需證明它們滿足：$a+b \equiv c+d \pmod{2^k}$

如果這兩個條件都滿足，就表示我們可以正確得到 $c+d$ 的結果。

> 已知 $k$ 位二進位值 $a$、$b$ 所表示之有號數分別為 $c$、$d$
> $a \equiv c \pmod{2^k}$
> $b \equiv d \pmod{2^k}$
> 根據同餘性質
> $a + b \equiv c + d \pmod{2^k}$

至於乘除的運算也很簡單，類似於國小時學的直式乘、除法，只是換成二進位而已。

事實上，無論是幾進位的運算，都可以用這種取補數、取模的方式來做減法。