十進位轉二進位為什麼不是除以2？

01-08

看《編碼的奧秘》裡面講十進位轉二進位的演算法為什麼不是除以2？在百度上查到的卻都是除以2計算。為什麼會有不同？是書印錯了還是百度錯了？
下圖是書上的截圖：
下圖是百度查到的演算法截圖：

《Code》一書顯然是從左向右計算的，最先算出的是最高位的結果。而常規的進位轉換演算法是從右向左計算的，最先算出的是最低位的結果。它們內含的運算當然都是等價的咯。

兩種方法的本質是一樣的。

還有一種方法，就是十進位先轉十六進位再轉二進位。這個方法也是十進位數不斷除以16取余，算出十六進位，十六進位與二進位關係十分明顯，直接可以寫出來。優點就是可以不用像第二種方法那樣除那麼多次。。。

都沒有錯，因為這2種方法，都正確。

考慮一個二進位數轉化成10進位的公式：

$(a_3 a_2 a_1 a_0)_2 = a_3 imes 2^3 + a_2 imes 2^2 + a_1 imes 2^1 + a_0 imes 2^0$

傳統除法方案：

高次項必然是2的倍數（ $a_3 imes 2^3 + a_2 imes 2^2 + a_1 imes 2^1$ ，2的倍數，毫無疑問），餘數項( $a_1$ )應該填在最低位

取走餘數項，整除2，商為： $a_3 imes 2^2 +a_2 imes 2^1 +a_1 imes 2^0$ ，參照上面的方法，輕鬆得到次低位。

依此類推。

優點：這個方法不需要你花時間預先計算1、2、4、8、16、32、64、128、256、512、1024、2048、4096、8192、16384、32768、65536、......，就可以完成轉成2進位的任務了

缺點：紙筆答題的時候，不先估算位數寫上去，你先寫了最低位，然後往後寫著寫著，發現最高位沒地方寫了……畫面非常優美。

《Code》一書的方案：

……你別說，我以前轉二進位還真是這麼猜過來的。

想法是：

比如我一個數240，

我說這個數的二進位表示中， $2^7$ (128)這一個權值的值是0是不可能的，

因為更低次項，就算全為1，也小於這個項的權值，

（ $2^6+2^5+dots+2^0 = 2^7 -1 < 2^7$

或者，形象化的說明是，(111111)2再加1，這6位表示不能了，我們搞個更高位，成了(1000000)2，那麼顯然低位的，填到最大，也湊不出高位為1的數值的。）

更高次項，下一個就是256了，大於240。

所以上來就知道，肯定128那一位是1，減掉，剩下240-128=112，這樣不停往下減。

優點：寫答案，直接從高位開始寫，內心愉快

缺點：計算量一點也不少就算了，還得記一下1、2、4、8、16、32、64、128、...

隱藏優點：如果單純的10進位轉2進位，這個方法只要乘法（預先計算一下），再減法和比較就行，這些操作的代價遠比機器指令里除法再取模低（現在的編譯器會把這些/2、%2優化成位運算，當然位運算是飛快的）

=============================================================

至於我自己么……

如果寫代碼，用百度上的方法，最後倒著輸出結果就好了。

如果紙筆速算/口算，我會喜歡使用《Code》一書的方法（習慣了，熟練了，這種推算還能快速跳過中間連續的0位，而不用老老實實的除2、取模、除2、取模）

對於10進位數，從左到右每位的數字代表的單位是：10的0次方、10的一次方、10的二次方、10的三次方。。。

對於2進位，從左到右每位的數字代表的單位是：2的0次方、2的一次方、2的二次方、2的三次方。。。

所以對於一個十進位數比如150而言，轉換成二進位數X：

如果先計算最高位，則就是先用150除以128即2的7次方，商為1，餘數為22，這22就是二進位X除了最高位剩下位的值（即10010110除去最高位1剩下的0010110的值），如此循環。

如果先計算X的最低位，那就是先除以2，如此循環。

學彙編時，有個概念加減法的效率比乘除法高。

這本書作者可能是習慣從這方面考慮的了。

也可以視作

每次與一個 2乘方數按位與後檢查是否大於0：

a 0b1000000(128)

a 0b0100000(64)

.......

話說，作者也可能是考慮到有些人的乘除法學的不好？

原理都是一樣的啊，只不過這本書上是從高位開始計算，除2求余是從低位開始計算，書上的這種辦法一般用起來就是： $150=128+16+4+2=2^{7} *1+2^{6}*0+...+2^{4}*1+2^{3}*0+2^{2}*1+2^{1}*+2^{0}*0$

轉化了之後就是10010110

百度方法中連除n次2的本質就是初始值除以2^n，得到的餘數和第一種方法用初始值直接除以2^n得到的餘數在意義是一樣的，對結果的處理為何不同R大已經說明了。