19th

计算机如何做乘法？

图一所列的竖式是人类在做乘法时使用的一个方式，其实计算机做乘法遵循的也是类似的方式。乘数上的每一位从右到左依次去乘以被乘数，所得的结果每次向左移一位，最后用加法器相加，就得到了乘法的结果。

但是这样顺序执行速度很慢，时间复杂度是 O(N)，N 是做乘法的数的位数。可以这样改进：将每次得到的中间结果两两相加，这样一下子就减少了一半，再次将得到的结果两两相加，又少了一半，如此反复，直到只剩下一个数，就是最终的结果了（如图二所示），时间复杂度是 O(logN)。这样做为什么可行，因为电路天然就是可以并行的，一个输入信号，可以同时传播到所有接通的线路当中。

二进制乘法列竖式

img

参考资料：

• https://time.geekbang.org/column/article/97477