Python 裡的整數（二）Ｎ進位演算法

接續昨天的鐵人內容，我們來設計一個Ｎ進位演算法試試看！

從認識十進位和二進位開始

預設 int 方法是十進位：

int(12)

12

想知道 12 的二進位如何表示，我們可以使用 bin 方法：

bin(12)

'0b1100'

開頭的'0b'提示你此字串是二進位制表示，如此一來字串轉回整數時，你就知道這邊是用二進位：

int('0b1100', 2)

12

Python 還有內建八進位 oct 方法和十六進位 hex 方法：

print(oct(12))
print(hex(12))

0o14
0xc

開頭'0o'暗示此數字是八進制，'0x'是十六進制。有了這些提示，我們也可以把他們轉回十進制整數：
(提示是方便，不寫也不會錯)

print(int('0o14', 8))
print(int('c', 16))

12
12

那如果Python內建的這些進制都不是我們要的呢？

假設我今天想做一個五進制演算法，怎麼做？

請出昨天提到的恆等式！

A = A // B * B + A % B

我們以整數 81 為例：

81
= 81 // 5 * 5 + 81 % 5 = 16 * 5 + 1
= 16 * 5^1 + 1 * 5^0
= (3 * 5 + 1) * 5^1 + 1 * 5^0
= 3 * 5^2 + 1 * 5^1 + 1 * 5^0
= (0 + 3) * 5^2 + 1 * 5^1 + 1 * 5^0
= 3 * 5^2 + 1 * 5^1 + 1 * 5^0
= 0 * 5^3 + 3 * 5^2 + 1 * 5^1 + 1 * 5^0
= 中斷點 * 5^3 + 第3個mod * 5^2 + 第2個mod * 5^1 + 第1個mod * 5^0

發現了嗎？以上規律讓我們做出來五進制的規則了！
81 = 3 * 5^2 + 1 * 5^1 + 1 * 5^0 = 311（五進制)

那上面為什麼要多此一舉，添一個 0 * 5^3？這是中斷點，方便我們寫演算法：

def index_to_n_base(number, base):
    """number: 大於零正整數
       base: 大於等於2的基底
    """
    if number < 0 or base < 2:
        raise Exception
    elif number == 0:
        return [0]
    
    index_list = []
    while number:
        index_list.insert(0, number % base)
        number = number // base
    
    return index_list
    

index_to_n_base(81, 5)

[3, 1, 1]

客制你的 encoding

上面得到的陣列是轉換成五進制後，各個五次方數每個位數的值，有了這個陣列，我們可以客製自己的 encoding：

encoding = "甲乙丙丁戊"
idx_list = index_to_n_base(81, 5)
ans = ''
for i in idx_list:
    ans += encoding[i]

print(ans)

丁乙乙

丁乙乙 是我們用客製的 encoding 規則 "甲乙丙丁戊" 得到的結果。不過這是我們自己訂的規則，不跟別人解釋別人是看不懂的。
所以已經有人訂定公認的規則，比如十進制是 "0123456789"，常用的十六進制 encoding 規則如下：

"0123456789ABCDEF"

Ｘ進制，與其說是整數轉換，不如說是整數編碼，其實數字永遠是十進制的"81"，只是我們可以用各種進制（編碼）代表它，數字的值是不會變的！

好啦，我們明天見～～～

參考：Python 3: Deep Dive (Part 1 - Functional)