# 進位制

人們平常使用的數字，是十進位的系統。
每位數逢十進位，故只記為 $0$ 到 $9$。

猜是因為人類只有十根手指，數到 $10$ 就數不下去，
只好記在一旁，空出手指後再繼續數。這就是十進位。

電腦只有兩根手指，因此使用二進位。

## 十進位制 decimal

以熟悉的十進位為例，個位數代表目前手指數到多少，
數滿 $10$ 之後在十位數記錄 $10$ 被數滿了一次，
之後解放所有手指再繼續數。

十位數可以想像成另一個人的手指，當他也數滿了 $10$，
那就在百位數記錄數滿了一次，代表著數滿 $10$ 次的 $10$。

一個十進位數 $416$ 代表著 $10$ 被數滿了 $41$ 次，之後又數到 $6$：

$$
416 = 41\times 10 + 6
$$

而 $41$ 又代表 $10$ 被數滿了 $4$ 次，之後又數到 $1$：

$$
416 = (4\times 10 + 1)\times 10 + 6
$$

展開得到

$$
416 = 4\times 100 + 1\times 10 + 6
$$

或者說 $10$ 次 $10$ 被數滿了 $4$ 次後，
又數滿了 $1$ 次的 $10$，接著又數到 $6$。

每個位數都是前一個位數數滿 $10$ 次的次數，由此規律可得：

$$
416 = 4\times 10^2 + 1\times 10^1 + 6\times 10^0
$$

同理，$32767$ 實際意義為

$$
32767 = 3\times 10^4 + 2\times 10^3 + 7\times 10^2 + 6\times 10^1 + 7\times 10^0
$$

### 推廣至任意進位制

任意 $k$ 位數的 $b$ 進位制數字 $S$，
以 $S_i$ 表達由右至左第 $i$ 位數的數字，$i$ 從 $0$ 起算，
則其代表的數值為

$$
\sum_{i=0}^{k-1} S_i\times b^i
$$

:::info
透過定義，可以將任意進位制的數字，透過以上多項式轉回十進位表達。
:::

書寫上每個位數完全相同的數字，也會因使用的進位制不同，導致實際值不同。
為了明確表達使用的進位制，會在數字右下以小字追加描述，例如：
- 十進位 $416_{10} = 4\times 10^2 + 1\times 10^1 + 6\times 10^0 = 416_{10}$
- 八進位 $416_8 = 4\times 8^2 + 1\times 8^1 + 6\times 8^0 = 270_{10}$
- 十六進位 $416_{16} = 4\times 16^2 + 1\times 16^1 + 6\times 16^0 = 1046_{10}$

:::warning
如果覺得上面的 $\sum$ 不好懂，可以參考上面幾個 $416$ 的不同進位，
或嘗試令 $b = 10$ 再隨便找個數字 $S$ 把 $i$ 從 $0$ 到 $k-1$ 代一遍看看。

代入夠小、夠簡單的數字幫助理解，是很實用的小技巧。
:::

## 十進位轉換至任意進位制

任意 $b$ 進位制數字 $S$ 從定義

$$
\sum_{i=0}^{k-1} S_i\times b^i
$$

可以展開成

$$
S_{k-1}\times b^{k-1} + S_{k-2}\times b^{k-2} + \dots + S_2\times b^2 + S_1\times b^1 + S_0\times b^0
$$

以 $32768_{10}$ 為例，就是

$$
3\times 10^4 + 2\times 10^3 + 7\times 10^2 + 6\times 10^1 + 8\times 10^0
$$

就像前面說的，還沒數滿一輪 $b$ 的部份會在個位數，
個位數以外則代表數滿了幾輪的 $b$ 所以會是 $b$ 的倍數

$$
(S_{k-2}\times b^{k-2} + S_{k-3}\times b^{k-3} + \dots + S_1\times b^1 + S_0\times b^0)\times b + S_0\times b^0
$$

以 $32768_{10}$ 為例，就是

$$
(3\times 10^3 + 2\times 10^2 + 7\times 10^1 + 6\times 10^0)\times 10 + 8\times 10^0
$$

因此，除以 $b$ 取餘數可以得到個位數；
而除以 $b$ 的商，會是「完整數滿幾輪的 $b$」的部份，
也就是說，除以 $b$ 的餘數和商，分別是個位數和個位數以外的部份。

以 $32768_{10}$ 為例，餘數為個位數的 $8$ 而商為個位數外的數字 $3276$。

由於剩下的會是 $b$ 進位數字，又可以用上面的方式，
除以 $b$ 分開個位數和個位數以外的數字，反覆至剩下個位數。

以 $32768_{10}$ 為例，除以 $10$ 可分出個位數 $8$ 和剩下的 $3276$，
餘下的 $3276$ 除以 $10$ 可分出個位數 $6$ 和 $327$，
$327$ 可再分為個位數的 $7$ 和剩下的 $32$，
$32$ 可再分為個位數的 $2$ 和剩下的 $3$，
$3$ 是個位數，所以可以停了，途中取出的 $8$、$6$、$7$、$2$ 及最後的 $3$，
即為 $32768$ 的每一個位數。

順序上是從個位數開始，因此最先取出的 $8$ 該放在最右邊，
故可拼湊出 $32768$。

又例如 $32768_{10}$ 如果轉成 $6$ 進位，
$32768 \div 6 = 5461\dots2$
$5461 \div 6 = 910\dots1$
$910 \div 6 = 151\dots4$
$151 \div 6 = 25\dots1$
$25 \div 6 = 4\dots1$

故 $32768_{10} = 411412_6$

### 短除法

手算時通常寫成短除法形式

32768 | 2
------
5461 | 1
-----
910 | 4
----
151 | 1
----
25 | 1
---
4

## 常見進位制

除了人類用的十進位和電腦用的二進位外，
由於二進位表達起來位數太多，因此又發展出八進位和十六進位。

$8$ 和 $16$ 分別是 $2^3$ 與 $2^4$，
從定義可知 $8$ 進位每一位數剛好可對應至 $2$ 進位的 $3$ 個位數，
$16$ 進位每一位數則可對應至 $2$ 進位的 $4$ 個位數。

以 $16$ 進位為例，每位數是 $0$ 至 $15$，剛好可用 $2$ 進位的四個位數表達，且乘以 $16$ 在 $2$ 進位下，相當於平移 $4$ 個位數。

以 $63_{16}$ 為例：

$$
\begin{aligned}
63_{16}& = 6\times 16^1 + 3\times 16^0\\
&= 6\times (2^4)^1 + 3\times (2^4)^0\\
&= (2^2 + 2^1)\times (2^4)^1 + (2^1 + 2^0)\times (2^4)^0\\
&= (0110_2)\times (2^4)^1 + (0011_2)\times (2^4)^0\\
&= 01100011_2
\end{aligned}
$$

### 八進位 octal

八進位在 C++ 中以 $0$ 開頭，好處是能完全以數字表達。
不過比起十六進位，現在很少被使用。

cout << 064 << '\n';

猜猜看上述程式碼會輸出什麼？

### 十六進位 hexadecimal

除了十進位外最常見的表達方式，和 $16 = 2^4$ 具有非常大的關聯。
$1$ 個位元組（byte）有 $8$ 個位元（bit），剛好可用 $2$ 位數表達，
而 $8$ 進位則不具備此特性。

$16$ 進位以 0x 開頭，例如 0x63 代表 $63_{16}$。
每個位數必須表達 $0$ 到 $15$，阿拉伯數字不夠使用，
因此以字母 $A$ 到 $F$ 來表達 $10$ 到 $15$ 的部份。

| A | B | C | D | E | F |
|:-:|:-:|:-:|:-:|:-:|:-:|
| 10 | 11 | 12 | 13 | 14 | 15 |

例如 0xAF 代表 $AF_{16} = 10\times 16^1 + 15\times 16^0 = 175_{10}$

:::warning
C++ 中的記憶體位置，預設以 $16$ 進位表達。

int ary[1], *ptr;
ptr = ary;
cout << ary << '\n';
cout << ptr << '\n';

:::

### 輸出輸入

[iomanip](/91DlTkOhQlSTCNCRrX2FXQ) 可以控制輸出、輸入的進位制：

int n;
cin >> setbase(16) >> n;
cout << setbase(16) << n << endl;

:::warning
[setbase()](https://en.cppreference.com/w/cpp/io/manip/setbase) 僅對 $8$、$10$、$16$ 有效，其餘數字皆為重置回預設值 $10$。
此外，$8$ 進位可用 `oct` 代替 `setbase(8)`，
$10$ 進位可用 `dec` 代替 `setbase(10)`，
$16$ 進位可用 `hex` 代替 `setbase(16)`。
:::

## C++ 儲存負數的方式

負數的儲存雖可透過犧牲一個位元代表正負號（signed bit）來處理，
但是除了不方便計算，還會有 $+0$ 和 $-0$ 兩種都是 $0$ 的結果。

因此，目標是找出一套方法，能從 $a$ 找出一個數字 $b$，
使得 $a+b = 0$，就能以 $b$ 表達 $-a$。

### 二的補數法

由於電腦儲存位數固定不變，要讓兩數相加為 $0$，
透過溢位使得能被儲存的位數均為 $0$ 即可。

例如 $32$ 位元整數，可在計算後讓最小的 $32$ 位全變成 $0$，
而不是 $0$ 的部份溢出至 $33$ 位或以後即可。

由於 $32$ 位有點長，以下用 $8$ 位元整數作為例子。

以數字 $13_{10} = 00001101_2$ 為例，
希望找到一個二進位數字 $b$ 使其與 $00001101_2$ 相加後，
末 $8$ 位數全變成 0，則 $b = -13_{10}$。

$$
00001101_2 + b = 100000000_2
$$

一個簡單的想法是：$11111111_2 + 00000001_2 = 100000000_2$

要找到一數使得 $00001101_2 + y = 11111111_2$ 相對簡單。
只要將每個位數反轉，$0$ 變成 $1$，$1$ 變成 $0$ 即可。

$$
00001101_2 + 11110010_2 = 11111111_2
$$

這時對左式加上 $1_2$ 即可讓末 $8$ 位全數歸 $0$。

$$
00001101_2 + 11110010_2 + 00000001_2 = 100000000_2
$$

代回一開始的式子可知

$$
b = 11110010_2 + 00000001_2
$$

這就是二的補數法：將一數 $a$ 二進位表達下每個位數反轉後加 $1$
得到一個新的數 $b$，則 $a+b = 0$ 推得 $b = -a$。

## 進位制的應用

進位制有不少應用，初學時可能較難想到它能用在哪，
這裡介紹一些例子。

可能不存在對應的題目，不過可以體會一下它們的核心概念。

:::warning
有些應用仰賴於其它尚未提及的知識，後面會慢慢補上。
:::

### 編碼 encode

編碼可以將一些情況轉成整數來保存，
例如將一串字母 $ABC$ 用 $27$ 進位以 $A$ 代表 $1$，$B$ 代表 $2$，…
可記為

$$
123_{27} = 1\times 27^2 + 2\times 27^1 + 3\times 27^0 = 786_{10}
$$

這可以讓文字在需要大量比較時，可以避免逐字比對，
只需一次的整數比較，就能知道兩串文字是否相等，不管字數。

:::info
由於 $27$ 進位不用幾位數就會讓 int 存不下，
但相同數字溢位後仍會相同，且 int 可保存 $2^{32}$ 種不同情況。

不同文字因溢位得到完全同樣結果的機會並不大，
仍可用以作為初步判讀，在數字相同時才進行原文的比對。
:::

:::warning
不使用 $26$ 進位是因為會分不出 $A$ 和 $AAA$，兩者都會被記為 $0$。
:::

也能用來保存像棋盤盤面等複雜狀況，例如黑白棋棋盤大小固定，
每格只有黑、白、空三種情況，可透過三進位編碼成整數。

### 窮舉多層決策

:::success
### 擲骰結果

輸入兩個整數 $n$、$t$，計算擲 $n$ 次六面骰後，
點數總和至少為 $t$ 的情況總共有幾種。

$1 \le n \le 8$
$1 \le t \le 2147483647$

#### 範例輸入

1 4

#### 範例輸出

3

> 共 $6$ 種情況，其中 $1$、$2$、$3$ 不符合，$4$、$5$、$6$ 符合，共計 $3$ 種。

#### 範例輸入

2 9

#### 範例輸出

10

> $3+6$
> $4+5$、$4+6$
> $5+4$、$5+5$、$5+6$
> $6+3$、$6+4$、$6+5$、$6+6$
> 共計 $10$ 種
:::

這道題目如果骰子數固定，例如 $3$ 顆，那麼 $3$ 層迴圈即可窮舉所有情況。
但這題骰子數需要輸入才知道，可是無法依照輸入來動態決定迴圈層數。

當然這有其他解決方式，例如把 $1$ 到 $8$ 圈各寫一遍，用 if 分開；
或者後面才會學到的方法。

一種就是利用編碼，將每顆骰子的 $6$ 種不同情況，以 $6$ 進位表達，
那麼最多 $8$ 顆骰子，就是窮舉所有 $6$ 進位的 $8$ 位數數字即可。
總共有 $6^8 = 1679616$ 種不同的情況。

窮舉 $0$ 到 $1679615$ 所有整數，即可窮舉所有可能的擲骰結果；
對每個整數求出 $6$ 進位下的 $8$ 個位數，即可得到每顆骰子的點數。

:::info
更廣義的定義上，每一步可以依結果不同，每個位數進位的數字可以不同。
例如：投一顆四面骰、一顆六面骰、一顆八面骰和一顆十面骰，
可以被編碼為：

$$
a\times (6\times 8\times 10) + b\times (8\times 10) + c\times (10) + d\times (1)
$$

用來表達四面骰擲出 $a+1$ 點、六面骰擲出 $b+1$ 點、
八面骰擲出 $c+1$ 點、並且十面骰擲出 $d+1$ 點的結果。

這已經不符合進位制的定義，但可以用來編碼。
:::

## 歡樂練習時間

:::success
### TOJ 292 - Jessica好仁慈
https://toj.tfcis.org/oj/pro/292/
:::

:::success
### UVa 389 - Basically Speaking
http://domen111.github.io/UVa-Easy-Viewer/?389
:::

:::success
### UVa 10473 - Simple Base Conversion
http://domen111.github.io/UVa-Easy-Viewer/?10473
:::

{%hackmd @sa072686/__style %}

###### tags: `競程：二章`, `競程`