# 進位制轉換
###### tags: `Competitive Programming Note`

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

大家應該都知道，平常我們用的數字系統是十進位制的，而計算機使用的是二進位制，而時、分、秒這樣的時間單位，用的是六十進位制……，這裡會幫大家複習一下進位制的轉換和一些性質，接下來的章節會需要用到。

接下來我會用 $(a)_n$ 這樣的方式來表示括號中的數字 $a$ 是用 $n$ 進位制表示的，例如 $(12345)_{10}$ 表示十進位的 $12345$，$(\text{ABCDE})_{16}$ 表示十六進位的 $\text{ABCDE}$，也就是十進位的 $703,710$。

## 基本轉換

大家都知道，一個十進位的數字 $a_{n}a_{n-1}...a_2a_1a_0$ （$a_i$ 表示一個位數）可以表示為：
$$
a_n \times 10^n + a_{n-1} \times 10^{n-1} + ... + a_2 \times 10^2 + a_1 \times 10^1 + a_0 \times 10^0
$$
舉例來說，$(1234)_{10}$可以表示為：
$$
1 \times 1000 + 2 \times 100 + 3 \times 10 + 4 \times 1
$$

相同的，非整數的十進位數字 $a_{n}a_{n-1}...a_1a_0.a_{-1}a_{-2}...a_{-(m-1)}a_{-m}$ 可以表示為：
$$
a_n \times 10^n + ... + a_0 \times 10^0 + a_{-1} \times 10^{-1} + ... 10^{-m}
$$
也就是
$$
\sum_{i=-m}^{n} a_i \times 10^i
$$

而 $k$ 進位制的數字 $a_{n}...a_0.a_{-1}...a_{-m}$ 表示的值就是：
$$
\sum_{i=-m}^{n} a_i \times k^i
$$
大部分人應該都知道怎麼算整數部分的值，而小數部分其實也是一樣的算法。

舉例來說 $(101.11)_2$ 轉換為十進位會是：
$$
1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 + 1 \times 2^{-1} + 1 \times 2^{-2}\\
= 4 + 0 + 1 + 0.5 + 0.25 = 5.75
$$
而 $(ABC.DD)_{16}$ 轉換為十進位會是：
$$
10 \times 16^2 + 11 \times 16^1 + 12 \times 16^0 + 13 \times 16^{-1} + 13 \times 16^{-2} \\
= 2560 + 167 + 12 + 0.8125 + 0.05078125‬ = 2739.86328125
$$

## 浮點數精確性

在算十進位除法的時候，經常會出現循環小數，例如：
$$
\frac{1}{3}=0.\overline{3} \\
\frac{1}{7}=0.\overline{142857}
$$
仔細看一下，$(\frac{1}{7})_{10}=(7^{-1})_{10}=(0.1)_7$，由此可知，有些在十進位會出現循環小數的數值，在其他進位制可能就不會有循環小數的狀況，反過來也一樣，在十進位看起來很簡單的值，在其他進位制可能會是很複雜的循環小數，更重要的是，二進位很容易發生這種狀況：
$$
(0.55)_{10}=(0.10\overline{0011})_2\\
(0.12)_{10}=(0.\overline{00011110101110000101})_2
$$
這會導致一個很討厭的結果，在儲存浮點數時，只能儲存有限的位數，因此有小數時很容易發生不精準的狀況，在[小數的儲存](/@wiwiho/CPN-float-type))會介紹更多。

## $k^i$ 進位制的互相轉換

$2^i$ 進位的每一位範圍是 $[0, 2^i-1]$，這恰好跟二進位的 $i$ 個 bit 能表示的範圍一樣，因此，在進行 $2^i$ 進位的互相轉換時，可以先轉成二進位。

舉例來說，$(147)_8$ 要轉換為四進位，那麼我們可以先轉成二進位，以 3 個 bit 表示八進位下的一個位數：
| 1 | 4 | 7 |
|:-:|:-:|:-:|
|001|100|111|
接下來，用 2 個 bit 表示四進位下的一個位數：
|01|10|01|11|
|:-:|:-:|:-:|:-:|
| 1| 2| 1| 3|
我們得出 $(147)_8=(1213)_4$

事實上，$k^i$ 進位的一個位數都可以用 $k$ 進位的 $i$ 個位數去表示，因為 $k^i$ 進位的每一位數範圍都是 $[0, k^i-1]$，$k$ 進位的 $i$ 個位數能表示的範圍恰好也是這樣。

## 進位制的簡易互轉法

先來知道一件事情，當一個數字乘以 $k$ 時，它在 $k$ 進位下的小數點會右移一位；而除以 $k$ 時，它在 $k$ 進位下的小數點會左移一位；對整數部分 $\bmod k$ 時，可以得到它的個位數。

在一些計概課本上會有像這樣的十進位轉二進位的方法：
有一個數字 $n$，整數部分是 $a$，小數部分是 $b$，將 $a$ 不斷除以 $2$ 並向下取整，直到 $a=0$ 為止，在這個過程中得到的餘數，倒過來寫就會是 $a$ 的二進位，例如：
$$a=19 \\
19 \div 2 = 9 ... 1 \\
9 \div 2 = 4 ... 1 \\
4 \div 2 = 2 ... 0 \\
2 \div 2 = 1 ... 0 \\
1 \div 2 = 0 ... 1$$
然後我們可以得到 $(19)_{10}=(10011)_2$。

可以這麼做的原因是，每次取 $a \bmod 2$ 時，我們會得到它在二進位下的個位數，接著把 $a$ 除以 $2$ 後，$a$ 在二進位下會右移一位，重複操作就可以依序得到從個位數開始往左的每一位數。

接著是小數部分 $b$，將 $b$ 不斷乘以 $2$，記錄它的整數部分後，把整數部分扣掉，再繼續重複這個動作，直到小數後沒東西為止，然後將記錄下來的整數部分依序寫下來就是 $b$ 的二進位。例如：（箭頭後方是整數部分）
$$
b=0.375 \\
0.375 \times 2 = 0.75 \rightarrow 0\\
0.75 \times 2 = 1.5 \rightarrow 1\\
0.5 \times 2 = 1 \rightarrow 1\\
$$
我們得到 $(0.375)_{10}=(0.011)_2$。

可以這麼做是因為，每次乘以 $2$ 時，$b$ 在二進位下的小數點後第一位會變成個位數，如此一來我們就可以依序得到小數點後第一位開始往右的位數。

至於 $n$，就把 $a$ 和 $b$ 加起來就好了，以上面的舉例來說，我們會得到 $(19.375)_{10}=(10011.011)_2$。

其實無論多少進位，都可以使用這種方式互相轉換，且這個方式無論在手動計算或寫程式計算都很方便，像這樣可以將 $n$ 轉為 $k$ 進位：

#include <string>
#include <algorithm>
using namespace std;
string convert(double n, int k){
    int a = (int) n;
    double b = n - a;
    string ans;
    while(a > 0){
        ans += a % k + '0';
        a /= k;
    }
    reverse(ans.begin(), ans.end());
    if(b == 0) return ans;
    ans += '.';
    while(b > 0){
        b *= k;
        ans += (int)b + '0';
        b -= (int)b;
    }
    return ans;
}

需要注意的是，有可能會遇到某進位制無法精確表示的狀況（見上方的[浮點數精確性](#%E6%B5%AE%E9%BB%9E%E6%95%B8%E7%B2%BE%E7%A2%BA%E6%80%A7)），此時在 `while(b > 0)` 這個迴圈就會卡住，例如 `convert(0.375, 3)` 就會發生這個狀況，可以加個位數限制之類的，至於手算時會比較容易注意到這個問題，就沒有太大影響。