進位
在四則運算的加法及減法中，進位（carry）是指某兩數或多數的某一位，經計算後產生一個數字，會影響此位左側高一位的計算結果。在加法的算法中，一般會由最小位數開始計算，計算後若有進位，上一位數字計算時需考慮進位的結果。例如6和7相加後得到13，3是個位數，和6跟7相同，會進位1到十位數，此處的1即為進位。若在減法中，也會有類似的情形，稱為借位（borrow）。
進位也在更高等的數學中出現。在加法器的電路設計中，進位也是重要的一部份。只處理二個位元相加，無法考慮進位的稱為半加法器，能處理二個位元及一個進位位元相加的才稱為全加法器[1]。
直式計算
[編輯]以下是一個直式計算中，用到進位的例子：
¹ 27 + 59 ---- 86
7 + 9 = 16，最上方的1就是進位，一般會用較小的數字，避免和原來相加的數字混淆。
相反的是借位，以下是借位的例子：
−1 47 − 19 ---- 28
此處7 − 9 = −2，因此改用(10 − 9) + 7 = 8，其中的10是從上一位數借來的。有兩種教借位的方式：
- 10從上一位數（十位）移到下一位數（個位）了，因此十位數留下3 − 1。
- 10從上一位數（十位）複製移到下一位數（個位）了，因此要在被減數中出現，將「借」走的數位還回來，因此十位數是4 − (1 + 1)。
機械計算器
[編輯]進位是機械計算器的基本挑戰之一。其中有二個困難點：第一個是一個進位可能會讓一個至數個位數的數值變化，例如某三位數已是999，因下一位數進位要加1，就會造成四個位數的變動，另一挑戰是進位可能在較高位數計算完成前就已經出現。
大部份的機械計算器是在原始加法的運算之後，再另外有一個週期執行進位的運算。在加法過程中，若有進位，會在對應的位數記錄，在進位週期中，再根據記錄進位的位數處理進位。這個流程需要先確認最低位數，再依序確認較高的位數。
像帕斯卡計算器（目前已知第二古老，而且還可以找到的機械式計算器），使用另一種方式來處理：將數字從0加到9的過程中，觸動一個機械裝置儲存能量，若再由9進到0，釋放該該機械裝置的能量，讓下一個位數加1。帕斯卡在他的機器中用到了重物以及重力。另一個使用類似方式的機器是19世紀大為成功的Comptometer，用彈簧代替重力。
有些先進的計算器則是連續傳動（continuous transmission）：在某一位數加1時，自動在較高一位數加1/10（這也會將再高一位數加1/100，以此類推）。一些早期先進的計算器（例如1870年柴比雪夫的計算器）[2]，以及1886年Selling的設計[3]）都使用此方法，但都不成功。1930年代初期Marchant calculator也引入了連續傳動方式，非常成功，開始了Silent Speed計算器。Marchant（後來的SCM企業）繼續使用此一技術並且創新，讓連續傳動的機械計算器到達非常快的速度，一直到1960年代末，機械計算器時代結束為止。
計算
[編輯]大部份的電腦，若數學運算後最高位元有進位（或是因為位元左移運算而出現的進位），會用特殊的旗標進位旗標記錄，之後運算較高位數時，可以進位。在減法出現借位時，也會設定相同的「進位旗標」，不過因為二補數運算的效果，其意義會相反。一般來說，進位旗標的1會讓算術邏輯單元進行一次加法，若相加的資料長度大於CPU一次可處理的長度，就要考慮進位旗標的影響。針對減法，有二種不同的作法，大部份的處理器會在有借位時設定「進位旗標」，但有些處理器（像是6502及PIC微控制器）是在有借位時清除「進位旗標」。
參見
[編輯]參考資料
[編輯]- ^ M. Morris Mano. Digital Logic and Computer Design. Prentice-Hall. 1979: 119-123. ISBN 0-13-214510-3.
- ^ Roegel, Denis. Chebyshev’s continuous adding machine (PDF). 2015. （原始內容存檔 (PDF)於2017-08-09）.
- ^ Ernst, Martin. The Calculating Machines (PDF). Charles Babbage Institute. 1925: 96 [2023-10-07]. （原始內容存檔 (PDF)於2019-10-21）.