进位
在四则运算的加法及减法中，进位（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）.