进位

(重定向自竖式

四則運算加法減法中,进位(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是從上一位數借來的。有兩種教借位的方式:

  1. 10從上一位數(十位)移到下一位數(個位)了,因此十位數留下3 − 1
  2. 10從上一位數(十位)複製移到下一位數(個位)了,因此要在被減數中出現,將「借」走的數位還回來,因此十位數是4 − (1 + 1)

机械计算器

進位是机械计算器的基本挑戰之一。其中有二個困難點:第一個是一個進位可能會讓一個至數個位數的數值變化,例如某三位數已是999,因下一位數進位要加1,就會造成四個位數的變動,另一挑戰是進位可能在較高位數計算完成前就已經出現。

大部份的机械计算器是在原始加法的運算之後,再另外有一個週期執行進位的運算。在加法過程中,若有進位,會在對應的位數記錄,在進位週期中,再根據記錄進位的位數處理進位。這個流程需要先確認最低位數,再依序確認較高的位數。

帕斯卡計算器(目前已知第二古老,而且還可以找到的機械式計算器),使用另一種方式來處理:將數字從0加到9的過程中,觸動一個機械裝置儲存能量,若再由9進到0,釋放該該機械裝置的能量,讓下一個位數加1。帕斯卡在他的機器中用到了重物以及重力。另一個使用類似方式的機器是19世紀大為成功的Comptometer英语Comptometer,用彈簧代替重力。

有些先進的计算器則是連續傳動(continuous transmission):在某一位數加1時,自動在較高一位數加1/10(這也會將再高一位數加1/100,以此類推)。一些早期先進的计算器(例如1870年柴比雪夫的計算器)[2],以及1886年Selling的設計[3])都使用此方法,但都不成功。1930年代初期Marchant calculator英语Marchant calculator也引入了連續傳動方式,非常成功,開始了Silent Speed計算器。Marchant(後來的SCM企業)繼續使用此一技術並且創新,讓連續傳動的机械计算器到達非常快的速度,一直到1960年代末,机械计算器時代結束為止。

計算

數位電路(例如加法器中),進位的概念類似。

大部份的電腦,若數學運算後最高位元有進位(或是因為位元左移運算而出現的進位),會用特殊的旗標進位旗標英语Carry flag記錄,之後運算較高位數時,可以進位。在減法出現借位時,也會設定相同的「進位旗標」,不過因為二補數運算的效果,其意義會相反。一般來說,進位旗標的1會讓算術邏輯單元進行一次加法,若相加的資料長度大於CPU一次可處理的長度,就要考慮進位旗標的影響。針對減法,有二種不同的作法,大部份的處理器會在有借位時設定「進位旗標」,但有些處理器(像是6502PIC微控制器)是在有借位時清除「進位旗標」。

參見

參考資料

  1. ^ M. Morris Mano. Digital Logic and Computer Design. Prentice-Hall. 1979: 119-123. ISBN 0-13-214510-3. 
  2. ^ Roegel, Denis. Chebyshev’s continuous adding machine (PDF). 2015. (原始内容存档 (PDF)于2017-08-09). 
  3. ^ Ernst, Martin. The Calculating Machines (PDF). Charles Babbage Institute. 1925: 96 [2023-10-07]. (原始内容存档 (PDF)于2019-10-21). 

外部連結