用移位和加减法模拟CPU乘除运算

硬件中也有算法逻辑，并且使用数字电路实现，最简单的是整数加法，减法直接通过对补码做加法，还是加法。而乘法和除法，其实也是加法。CPU就是不断地不停地做加法。CPU是个加法狂魔！实现乘除法的数字电路，就是模拟和优化人类笔算的过程。ALU内实现了加减法，位移据说现在一般都不放在ALU内，anyway，CPU能够做到的最简单直接的计算，就是加减法和位移。减法也是通过加法实现的。

ALU内只做整数加减法，整数的乘除需要其它专门的电路，其内部会包含额外的ALU单元。浮点数的计算就更加复杂，包含的基本计算单元更多，这其中当然也有很多ALU单元。因此，整数加减法最快，其次是整数乘法，然后是整数除法，浮点数运算最慢。计算的快慢通过所需要的cycle数量来体现，因此不同的instruction，其cycle数量不同。

用移位和加法模拟CPU乘法

写了一小段python程序，用移位和加法这两种运算，模拟计算机做二进制乘法的过程！ALU单元做乘法，就是移位和加法。其实加法几乎是ALU单元唯一进行的运算，自己与自己相加，就是左移一位。左移一位，就相当于乘以2。

一个数，乘以10，就是左移1位；乘以100，就是左移2位；乘以101，就是自己加上自己左移2位后的和；乘以111，就是自己加上左移1位再加上左移2位的累计和......这个过程能想明白吧？

def multiply(n1, n2):
    result = 0
    sign = 0
    if n1 == 0 or n2 == 0:
        return 0
    if n1 < 0 and n2 < 0:
        n1 = -n1; n2 = -n2
    if n1 > 0 and n2 < 0:
        n2 = -n2; sign = 1
    while n2 != 0:
        if n2&1 != 0: result += n1
        n1 <<= 1; n2 >>= 1
    return result if not sign else -result


print(multiply(12,2), 12*2)
print(multiply(23,100), 23*100)
print(multiply(123,456), 123*456)
print(multiply(-10,789), -10*789)
print(multiply(10,-56789), 10*-56789)
print(multiply(-12345,-98765), -12345*-98765)
print(multiply(0, 7788), 0*7788)

multiply函数先处理了一点符号方面的细节；在循环中，n1左移，n2右移，n2&1是在判断数值的奇偶性，如果是奇数，结果就要增加，偶数就跳过，判断奇偶就是在判断那一位是0还是1。这个过程直到n2等于0为止（这时n2所以的1比特位都移走了）。

$ python3 multiplation.py
24 24
2300 2300
56088 56088
-7890 -7890
-567890 -567890
1219253925 1219253925
0 0

最简单的乘法电路

实际的CPU内的乘法电路，会在这个基础上进行深度优化加速。比如通过增加硬件资源的方式，来实现并行计算等等。（软件的优化加速，有些方法是通过增加对内存的使用，有相似之处）

用减法模拟CPU除法

计算机做除法，到底要不要做位移，似乎答案是都可以。做位移，按照人类做竖式除法一样计算，可以得到答案，不做位移，就用纯粹的减法，也可以计算除法。下面用一小段Python代码，使用纯减法的方式，模拟计算机的除法。而对于计算机而言，减法就是加法。

def divide(n1, n2):
    if n2 == 0: raise ZeroDivisionError(str(n1)+'/0')
    shang = 0
    sign = 0
    if ((n1 < 0 and n2 > 0) or
        (n1 > 0 and n2 < 0)):
        sign = 1
    n1 = abs(n1)
    n2 = abs(n2)
    while n1 >= n2:
        n1 -= n2
        shang += 1
    return (shang,n1) if not sign else (-shang,-n1)


print(divide(0,2))
print(divide(4,2))
print(divide(-5,2))
print(divide(-8,2))
print(divide(12345,5))
print(divide(10000,-50))
print(divide(29999,-50))
print(divide(30000,51))

如果除数为0，直接异常；初始化后，先判断符号位；然后取绝对值；然后开始减法，n1每减去一次n2，商都加1，直到n1 < n2；剩下的n1就是余数。

E:\py>python division.py
(0, 0)
(2, 0)
(-2, -1)
(-4, 0)
(2469, 0)
(-200, 0)
(-599, -49)
(588, 12)

最简单的除法电路

这个电路图所表达的算法，与前文有所不同，其divisor首先被左移了32位，然后在不断做减法的过程中，右移divisor。这就是在模拟人类笔算除法了！