theme: qklhk-chocolate
highlight: xcode
本文主要介绍的是计算机内部定点数的加减乘除如何实现，涉及到补码，原码补码的一位乘，一位除等相关知识。
计算机只能做加法, 我们大学老师经常这么念叨，那他是如何通过加法把其他三种运算：减乘除 给实现的呢？ 这些最基础的实现里又包含哪些精彩绝伦的算法呢，下边我们一起看看。
这里首先有个基本认识， 一个数的二进制表示
数字的二进制表示
我们现实中经常使用到的数字是十进制的，而计算机内部则以二进制形式表示，并且有符号数的最高位是其符号位0表示正数，1表示负数。二进制的一般表示有原码，反码，补码这三种，他们的关系是这样的 对于正数，他们都是一样的，对于负数，原码每位求反就是反码，反码再加1就是补码。（这里再介绍一种码，移码，补码的符号位如果取反就成为了移码）：
graph LR负数 --> |符号为为1|原码原码 --> |每位求反|反码反码 --> |加1|补码
这么多码中，大多数计算机采用的是补码，为什么是补码是一个比较值得寻味的话题，一般而言有以下几个原因：
- 比起原码跟反码，补码0的表示是唯一的，即零元唯一，运算是可逆的，然后可以比原码还有反码多表示一位数字， 并且可满足 x + (-x) = 0
- 符号位与数位可以一起参与运算，无需单独设置符号位处理路线
- 计算机只需做加法
- 便于扩充直接补齐符号位就行
下边开始讲一下加法
加法
补码加法
补码的加法 符号位是参与运算的，且有公式：
$[x+y]补 = [x]补 + [y]_补$
补码减法
前边也讨论过计算机只会做加法，而要实现减法，则需要将减法转换成加法：
因此， 找到$[y]补$与$[-y]补$之间的关系就能用加法算出减法了，这里也给出求$[-y]补$的方法： 就是将$[y]补$连同符号位按位取反然后再加1即可得到$[-y]_补$
下边一个例子将加减串起来讲一下：
$$
计算： [x]补 = 0.0010 ，[y]补 = 1.1010 求[x-y]补 \
首先 由上边知识可以得到[-y]补 = 0.0110\
[x-y]补 = [x]补 + [-y]_补 \
= 0.0010 + 0.0110 \
= 0.1000
$$
这里多说一句，就是机器字长固定的情况下任何计算都是要考虑到溢出的，计算结果溢出后，则需要扩充数值位，否则就会产生错误。对于加发来讲，若相加的两个数符号相同，但是结果的符号与之不同，则可认为是溢出。
乘法
原码一位乘
乘法就是多个加法，拿$x\times0.1011$举例如下：
x\times0.1011 = x(0.1 + 0.00+ 0.001 + 0.0001)\
= 0.1(x + 0.0x + 0.01x+ 0.001x)\
= 0.1(x + 0.1(0x + 0.1x + 0.01x)\
= 0.1(x + 0.1(0x + 0.1(x+0.1x)))\
= 0.1(x + 0.1(0x + 0.1(x + 0.1(x + 0))))\
二进制中0.1等于2^{-1} \
因此原式最终可写成\
2^{-1}(x + 2^{-1}(0x + 2^{-1}(x + 2^{-1}(x + 0))))
二进制数乘以$2^{-1}$ 可以当成右移一位来实现，因此乘以n位数就可以用n次移位和n次加法来实现。
我们以$x=0.1101,y=-0.1011$为例， 阐述计算机实际是怎么实现的：
两个n位数相乘会产生长度最大为2n位的结果，因此直接保留部分积的结果会需要2n位的寄存器，为了使得尽可能节省性能，部分积会分成两部分来保存，高位保存在一个寄存器中，低位会逐渐往y的寄存器上移过去，这是因为整个运算过程y的每一位（二进制要么0要么1）所起的作用就是要不要加上x，他是无需保留的，没进行一次加法都可以将当前最低位移出。所以总共需要三个寄存器： 1个保存被乘数x，一个保存部分积的高位，一个保存y和部分积的低位，一次运算过程可以如下描述：
$x = 0.1101, y= -0.1011$
源码一位乘的移位都是逻辑移位。
补码一位乘
校正法
当乘数为正数时，可以按照原码一位乘的规则来做运算，当乘数为负数时，也还是按原码一位乘规则来做计算，但是需要在最后的结果加上$[-x]_补$ 矫正。
要注意补码一位乘的移位是算术移位。校正法部分积采用双符号位最高位才是其符号位，次高位参与移位
算术移位和逻辑移位的区别就是符号位参不参与移位，参与的是逻辑移位，移位后空缺位补0，不参与的是算术移位，正数时和逻辑移位一样，负数时原码不变，补码右移左边添1，左移右边添0
$[x]补 = 0.1101, [y]补= 1.0101, [-x]_补 = 1.0011$
比较法（booth算法）
基于校正法的描述，可以很明显看到由于乘数符号位的不同最后一步的运算规则就会不同，这样的设计线路会比较复杂，基于此，比较法就应运而生了，他的运算规则是统一的，不随符号改变而改变。
具体实现上，被乘数与部分积取双符号位，与校正法不同比较法的符号位是参与运算的，乘数取单符号位，乘数末尾增设附件位$y{n+1}$ 初始值为0， 具体运算以$y{n},y_{n+1}$ 的状态进行运算
| $y{n},y{n+1}$ | 操作 |
|---|---|
| 00 | 部分积右移一位 |
| 01 | 部分积加 $[x]_$补，并右移一位 |
| 10 | 部分积加 $[-x]_$补，并右移一位 |
| 11 | 部分积右移一位 |
通过实际例子可以更好的阐述整个过程：
$[x]补 = 1.0101, [y]补= 1.0101, [-x]_补 = 1.0011$
除法
既然乘法可以分成多个加法去实现， 那么。。。是的，除法就可以用多个减法去实现。只是在上商的时候计算机要判断当前商是不是上大了，从而决定要不要恢复被减去的除数，这就是恢复余数除法，在此基础上又衍生出了不恢复余数除法（加减交替法）接下来主要探讨的是原码恢复余数除法 不恢复余数除法和补码不恢复余数除法
原码除法
原码恢复余数除法
原码恢复余数除法符号位单独处理，取除数和被除数的绝对值补码计算， 若余数正，商上1，左移一位减去除数；若余数为负商上0，加上除数，左移一位，继续减去除数，若除数尾数有n为则，重复此步骤n次，实际实现时机器会设置一个计数器统计n控制循环次数，最后一步若尾数为负则需要恢复余数加上除数：
$[x] = -0.10110, [y]= 0.11111, [-y]_补 = 1.00001 求x/y$
除数尾数为5位，count = 6
符号位可由两数的符号位做异或运算的到即最后结果位： -0.10110
原码不恢复余数除法
基于恢复余数除法，余数的正负决定了下一步该如何运算，当余数大于0的时候：
$R’ = 2R - y ^*$
当余数小于0的时候：
$R’ = 2 (R + y^) - y^ = 2R + y*$
不难看出，不恢复余数除法就是根据余数的符号，先左移再加或减去除数:
例子：
$[x] = -0.10110, [y]= 0.11111, [-y]_补 = 1.00001，求x/y$
补码除法
补码不恢复余数除法
补码不恢复余数除法，遵循以下规则
补码除法要注意末位需要横置1
基于上述规则的实现，还需要加上$1+2^{-n}$,其中1用于修正商符
$[x] = 0.1000, [y]= -0.1010, [-y]_补 = 0.1010，求x/y$
count = 4
假商等于0.001。然后需要加上$1+2^{-4}$
即最终商等于0.001 + 1.0001 = 1.0011
