整數的儲存

tags: Competitive Programming Note

本文已停止更新，新版請至 WiwiHo 的競程筆記

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

最簡單的方式是用最高位元來表示正負號，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

一般只會用到 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(\mathrm{mod}{2}^k)$（模除取正數），證明如下（

$a\ge 0$ 時

$a=b$，所以不需要證）：

證明

$k$ 位元的二進位值所表示之有號數

$a$（

$a<0$） 及無號數

$b$ 滿足

$a\equiv b(\mathrm{mod}{2}^k)$：

$a=-(2^k-1-b+1)=-2^k+b$

$amod{2}^k=b$

$b<2^k$，故

$bmod{2}^k=b$
得

$a\equiv b(\mathrm{mod}{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(\mathrm{mod}{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(\mathrm{mod}{2}^k)$

如果這兩個條件都滿足，就表示我們可以正確得到

$c+d$ 的結果。

已知

$k$ 位二進位值

$a$、

$b$ 所表示之有號數分別為

$c$、

$d$

$a\equiv c(\mathrm{mod}{2}^k)$

$b\equiv d(\mathrm{mod}{2}^k)$
根據同餘性質

$a+b\equiv c+d(\mathrm{mod}{2}^k)$

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

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