2.2 化计算为加法

2.2.1 从小学的1+1开始

四则混合运算中加、减、乘、除是算术的基础，其中乘和除又可以通过加和减来实现，所以加和减是更为基本的运算。

先来实现两个数的乘法a*b，按照定义就是把a加b次，如3*4，就是把3加3总共加4次。

程序如下：

程序的核心是while循环，将a加b次。

读者肯定看出来了，上面的程序只能计算正整数，计算负数会出错。所以再考虑一下正负数。有四种情况：+ +、+ -、- +、- -。对这四种情况，得出它的结果的符号，然后化为正数进行计算。程序如下：

以上程序通过加法实现了乘法，循环了很多次，方法很笨拙，但确实可以实现。同样也可以用减法实现除法。

但如果b是实数就很难实现，因为有小数部分，上面的循环只对整数有效。实际上实数是由两个整数中间加点组成的，用上面的方式还是可以处理的，但过程有点复杂，暂不介绍。

读者可能又会问计算机内部真的是这么干的吗？答案是部分是。实际上，计算机内部是通过加法和移位操作联合起来实现乘法的，为了处理负数和实数，还需要用到补码和规范化存储规范。这些内容后面会讲到。

2.2.2 计算机的移位操作

接下来看一下移位操作是如何加快计算的。

举个例子，125*103，利用上节的程序需要循环103次，下面用移位操作加速。

按照十进制的定义，103 = 1*10²+0*10¹+3*10⁰。这样只要把125移位几次再相加即可。计算过程分成三步。

1）1*10²：将125移位2次，再乘1，得到12500。

2）0*10¹：0值，不计算。

3）3*10⁰：将125移位0次，再乘3，得到375。

然后把三部分相加，即12500+0+375=12875。

同样得到结果，只用了三次移位外加三次循环。

其实，Python中是有移位操作的（即＜＜）。但是操作的结果跟想的有点不一样，可以尝试45＜＜，结果会返回90，而不是450。原因是计算机内部用二进制表示，左移一次相当于乘2。可以自己模拟写一个shift函数：

这个函数将一个数乘10、100、1000，相当于移位n次。本程序实现用到了乘法，这只是示意，实际计算机中的移位是一个独立的基本运算。

这里还用到了一个新的表达n-=1，这是一个缩写，作用等同于n=n-1，但是执行效率可能会更高（依赖于具体的实现），而且看起来更加专业。

再用这个lshift()改写乘法程序：

程序的关键部分是那个嵌套循环：

上面程序中有一个for语句，这是一个固定次数的循环，次数就是数字串的位数，如对103，循环次数就是3。i的取值依次为0、1、2。之后，根据位置从右往左取该位置上的数字，即程序语句：n = int(s[len(s)-i-1])，如对103，第一次i为0，那么就是取的3-0-1=2这个位置的数字，这个位置是103的最右边一位（编号是从0开始的，所以最后一位也就是第三位的位置编号为2）。取到该数字后，先把被乘数移位，移i次，比如对103中的3，就移位0次，相当于不动，对1就要移位两次。然后用移位后的数乘以n（通过加循环n次实现），即对103中的3，把125循环三次相加得到375，对于103中的0，不用计算，对于103中的1，把12500循环1次相加得到12500，所以最后的结果为12875。拿出纸和笔，自己手工跟踪一遍。

顺便提一下，while循环中的r=r+c, n=n-1写成r+=c, n-=1会更加专业。

测试一下print(multiply(125,103))。

2.2.3 不单单是乘除法实现

再解释一下二进制下的乘法实现，为以后介绍计算机内部实现做准备。

读者已经知道，计算机内部用二进制表示数，101010…，其数值等于k*2ⁿ+k*2^n-1+…+k*2⁰。

所以a*b就相当于a*k*2ⁿ+a*k*2^n-1+…+a*k*2⁰，即把a移位后累加。二进制的好处是它只有0和1两个数字，所以不用考虑其他问题，直接移位或不移位即可（十进制中还要考虑个位数的乘法）。

尝试计算6*5，6的二进制表示为110，5的二进制表示为101，需要计算110*101的值。

1）101的右边第1位为1，将110左移0位得到110。

2）101的右边第2位为0，因此不计算（结果当成0）。

3）101的右边第3位为1，将110左移两位得到11000。

4）把1）～3）三步的结果相加：11000+0+110=11110，该结果为30。

除法类似，是通过减法和移位操作实现的，来看一个例子。

815/23，手工按照这几步从高位到低位计算。

1）先用8除23，商为0，余数为8。

2）余数8左移，得到80，再加上第2位1，得到81，除23，商为3，余数为12。

3）余数12左移，得到120，再加上第3位5，得到125，除23，商为5，余数为10。

计算完毕，得到商为035，即35，余数为10。

程序如下：

测试print(divide(815,23))。读者可以仿照乘法的过程自己把除法跟踪一遍。

二进制除法也是同样的原理，也因为只有0和1两个数，所以比十进制简单，不用除个位数，只需要比大小，大就是1，小就是0。

尝试计算85/6，用二进制表示为1010101/110，按照如下步骤操作。

1）先拿最高位1与110比大小，比110小，商为0，余数为1。

2）余数左移，为10，再加上第2位数字0，得数还是10，跟110比大小，比110小，商为0，余数为10。

3）余数左移，为100，再加上第3位数字1，得数是101，跟110比大小，比110小，商为0，余数为101。

4）余数左移，为1010，再加上第4位数字0，得数是1010，跟110比大小，比110大，商为1，余数为100。

5）余数左移，为1000，再加上第5位数字1，得数是1001，跟110比大小，比110大，商为1，余数为11。

6）余数左移，为110，再加上第6位数字0，得数是110，跟110比大小，商为1，余数为0。

7）余数左移，为00，再加上第7位数字1，得数是1，跟110比大小，比110小，商为0，余数为1。

计算完毕，最后的商为0001110（即14），余数为1。

从以上例子可以看出是把四则运算化成了加减运算，以后还会进一步将减法化为加法。这样从原理上，只需要有加法操作就可以了。万法归一。

扩展一下，如果要计算复数，上面的程序又不能支持了。这里需要一个新的表达，用一个数是不行的，复数包含实部和虚部，所以Python用12 + 3j表示。注意这里用的是j，不是数学中的i，这么做是为了遵从电子工程界的惯例。

有了这个知识，也是可以写出程序来实现复数域的运算的。在此不再赘述。