最近在準備一些面試時看到的題目，覺得挺有趣的！對電腦來說，除法所需要耗費的時間是比加法與減法來要多的。畢竟電腦的設計是透過邏輯運算來進行，透過設計邏輯電路就可以理解除法的複雜度。此外，模數運算就更不用說了…模數運算本身就是基於除法的。所以，如果能夠不使用除法就儘量不要使用，這也是為什麼有時候看到一些程式碼中，明明除以二寫成 x / 2 是多麼的直覺，但卻會有人寫成 x >> 1！這就是因為位元運算比除法運算快速許多，不過以這個例子來說，很多時候編譯器會自動幫我們優化就是。
回到本文的主題－「如何不使用除法來判斷一個整數是否被 3 整除？」。一般來說，我們都知道要判斷一個整數是否被 3 整除相當的容易，只要把該整數中的每一位數字加總，並判斷加總後的數字是否被 3 整除即可。如果加總後的數值仍然過大，也可以繼續套用將每一位數字加總的方法，直到數值夠小為止。但是如果直接使用該方法，那麼似乎要能夠將每一位數字取出來，這時候最直覺的方法似乎就是一直對 10 取模，並將該數除以 10 直到數值為 0 停止，參見以下程式碼：
1
2
3
4
5
6
7
def add_digits(x):
if x >= 10:
return add_digits(x // 10) + (x % 10)
return x
def divisible_3(x):
return add_digits(x) % 3 == 0
不過看了以上的程式碼後，應該會覺得有點愚蠢。如果要在加總後再進行一次對 3 取模的運算，那乾脆一開始就對 3 取模就好啦！所以我們應該再進行些改進，讓他反覆的加總直到變成個位數。而在個位數下能被 3 整除的數字有 0、3、6、9。僅修改 divisible_3 該函式，如下：
1
2
3
4
def divisible_3(x):
while x >= 10:
x = add_digits(x)
return x in [0, 3, 6, 9]
不過，為了將十進位的數字加總，仍然需要透過除法來進行，是否有不需要除法的方式呢？！以下提供四種方法：
方法一 - 數字轉字串
將數字轉為字串後，就能夠不採用除法來將每一位數字分開了，參見以下程式碼：
1
2
3
4
5
6
7
def add_digits(x):
return sum([int(d) for d in str(x)])
def divisible_3(x):
while x >= 10:
x = add_digits(x)
return x in [0, 3, 6, 9]
不過，其實這根本不是個改進方法。由於將數字轉成字串是透過 Python 的 str 來進行轉型，其內部可能非常複雜所以導致執行時間反而比用除法還要來的高。所以，該方法僅適用於「整數轉字串」比「除法」來得快時才有用。
方法二 - 十六進位加總
在十六進位的狀況下，將每一位數字加總後，若仍然可以被 3 整除，那麼也代表原本的整數可以被 3 整除的特性仍然適用。電腦雖然是二進位的方式設計的，要取出每個 bit 可以透過 and 運算與右移運算來完成。但 16 剛好是 2 的四次方，要取出十六進位的每個數字其實也只需要 and 運算與右移運算！只是變成要跟 0xF 進行 and 運算，並且變成右移 4 個單位。而在十六進位的個位數下能被 3 整除的數字有 0x0, 0x3, 0x6, 0x9, 0xC, 0xF。
1
2
3
4
5
6
7
8
9
def add_digits_16(x):
if x >= 0x10:
return add_digits_16(x >> 4) + (x & 0xF)
return x
def divisible_3(x):
while x >= 0x10:
x = add_digits_16(x)
return x in [0x0, 0x3, 0x6, 0x9, 0xC, 0xF]
方法三 - 二進位下交錯加總
在十進位下，有個很容易判斷一個數是否能被十一整除的方法。就是將其奇數位的和與偶數位的和乘上 -1 後相加，若結果為可以被 11 整除，那麼原本的數字就能被 11 整除，而在二進位下也能夠用相同的方式來判斷一個數是否能夠被 3 整除。
1
2
3
4
5
6
7
8
9
def alt_add_digits(x, sign):
if x > 1:
return alt_add_digits(x >> 1, sign * -1) + (x & 1) * sign
return (x & 1) * sign
def divisible_3(x):
while x > 1:
x = abs(alt_add_digits(x, 1))
return x == 0
方法四 - 有限狀態機
下圖表示為一有限狀態機：
→ ⓪ ← 1 → ① ← 0 → ②
只要將該整數以轉為二進位後輸入，並從狀態 ⓪ 出發。以下是狀態轉移表格：
| 當前狀態 | 輸入 | 轉移狀態 |
|---|---|---|
| ⓪ | 0 | ⓪ |
| ⓪ | 1 | ① |
| ① | 0 | ② |
| ① | 1 | ⓪ |
| ② | 0 | ① |
| ② | 1 | ② |
只有最後停留在狀態 ⓪ 時，該表示該整數能夠被 3 整除。
1
2
3
4
5
6
7
8
9
table = [[0, 1], [2, 0], [1, 2]]
def stat_transfer(stat, x):
if x > 0:
return stat_transfer(table[stat][x & 1], x >> 1)
return stat
def divisible_3(x):
return stat_transfer(0, x) == 0
以下是上面所提出的四種方法，測試方式為測試 0 ~ 1,000,000 中的所有數字是否能夠被 3 整除隻時間：
| 方法 | 時間 (sec) |
|---|---|
| 除法 | 3.686 |
| 數字轉字串 | 12.386 |
| 十六進位加總 | 3.262 |
| 二進位下交錯加總 | 8.024 |
| 有限狀態機 | 7.332 |
可以發現，除了十六進位的方法明顯比除法快速外，其他似乎表現的都不怎麼樣。數字轉字串推估是 str 內部較純粹使用除法來獲得各個數字複雜，因此有較大的負擔存在，也使得該方法成為最慢的方法。此外，「二進位下交錯加總」與「有限狀態機」這兩個方法表現較差的可能推估是採用了遞回的方式，並且可以明顯看出該兩個方法因為轉換為二進位使得遞回深度明顯多於單純的除法，也導致執行時間較長。
不過，在我嘗試更改成迭代版本後，似乎也沒有說有大幅度的改進，仍舊比單純除法還慢。比較結果如下：
| 方法 (迭代) | 時間 (sec) |
|---|---|
| 除法 | 4.483 |
| 數字轉字串 | 12.845 |
| 十六進位加總 | 3.101 |
| 二進位下交錯加總 | 7.557 |
| 有限狀態機 | 6.063 |
此時，懷疑「乘法」的花費是大於「除法」的，並因而導致「二進位下交錯加總」該方法會如此緩慢！因此我決定再修改一下，讓該方法不要用到乘法，修改 alt_add_digits 如下：
1
2
3
4
5
6
7
8
def alt_add_digits(x):
ret = 0
sign = True
while x > 1:
ret = ret + (x & 1) if sign else ret - (x & 1)
x = x >> 1
sign = not sign
return ret
但僅有些微的效能增進，仍舊無法與除法進行比較。雖然已經沒有乘法了但仍舊效率低落，因此我想原因應該是轉為二進位大幅度的增加迭代（遞回）的次數，而導致最後兩個轉為二進位的方法會有如此低效的表現。而轉為十六進位的方法也是因為迭代（遞回）的次數較少，因此有高效的表現。以下為各個方法的時間複雜度：
| 方法 | 時間複雜度 |
|---|---|
| 除法 | log10N |
| 數字轉字串 | 未知 |
| 十六進位加總 | log16N |
| 二進位下交錯加總 | log2N |
| 有限狀態機 | log2N |
參考資料