进位

(重定向自竖式

四则运算加法减法中,进位(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). 

外部链接

编辑