C/C++加减乘除运算效率分析

梦里梦外; 2022-11-11 14:50 247阅读 0赞

# 运算效率 #

> 移位 > 赋值 > 大小比较 > 加法 > 减法 > 乘法 > 取模 > 除法。

# 使用移位来代替乘除法，提高运算效率 #

int a = 64;
    	cout << "a / 2 = " << (a >> 1) << endl;
    	cout << "a / 4 = " << (a >> 2) << endl; 
    	cout << "a / 8 = " << (a >> 3) << endl;
    	cout << "a * 2 = " << (a << 1) << endl;
    	cout << "a * 4 = " << (a << 2) << endl;
    	cout << "a * 8 = " << (a << 3) << endl;
    
    /*
    a / 2 = 32
    a / 4 = 16
    a / 8 = 8
    a * 2 = 128
    a * 4 = 256
    a * 8 = 512
    */

加法比减法快,乘法比除法快原因是计算机硬件只能做加法,CPU里面都是加法器  
计算机中有专门的移位功能部件，这也是最基础的部件。**乘法和除法都是靠移位实现的。乘2^n，左移n位，除2^n，右移n位**。

另外，原始的乘法器是一步一步乘(移位)出来的，每次取乘数的一位与被乘数操作，1则把被乘数照写，0则为0，然后乘数右移。这样循环，最后把每一步结果加起来。  
后面通过阵列连乘器改进速度，一次算出上面每一步的结果，然后直接相加。

乘法是加操作，而除法是每步的结果作加法或减法(加减交替法)，有的算法还需要恢复上一次的结果(余数恢复法)，而且每一步加减后还要进行移位，所以最慢。

从数学上讲，CPU中的ALU在算术上只干了两件事，加法，移位，顶多加上取反，在逻辑上，只有与或非异或。

> 加法->加法。
> 
> 减法->取反，加法。
> 
> 乘法->移位，逻辑判断，累加
> 
> 除法->移位，逻辑判断，累减

至于乘法除法为什么这样，搜索二进制数如何进行乘法除法，说白了，和我们熟悉的十进制运算流程上一模一样。

所以只需要加法器，移位器和基本逻辑门电路就构成一个简单的ALU。

从硬件实现上讲，可以看出，实现这四种基本运算只需要上述硬件组件就行。早期的cpu里结构简单，只有这些组件，没有专门的乘法器、除法器。但是可想而知效率也是低下的（其中除法效率最低，因为每次移位后比乘法还多出一次试错操作），后来的cpu会集成专门的并行处理电路在cpu内建的协处理器（比如浮点运算器，很早的cpu是没有专门计算浮点的电路的）中，在硬件上实现，这样计算速度就快了。当然，计算的逻辑还是没变。