2.3-整数的运算

2.3 整数的运算

2.3.1 加法

无符号加法

$w$位无符号数的取值范围是：${\color{tomato}{0 \leq x < 2^w}}$

• 两个无符号数$x,y$相加，如果和小于$2^w$，结果为$x+y$，与实际情况一致
• 如果和大于等于$2^w$，结果会发生溢出，为${\color{tomato}{x+y-2^w}}$

$$x +_w^u y=\left\{ \begin{array}{cl} {\color{deepskyblue}{x+y}} & {\color{deepskyblue}{x+y<2^w}} & \rm{Normal}\\ {\color{tomato}{x+y-2^w}} & {\color{tomato}{2^w \leq x+y < 2^{w+1}}} & \rm{Overflow}\\ \end{array} \right.$$

可以有2种理解：

1. 相当于把最高位$w$位的1去掉了，所以是减去$2^w$
2. 截断后面$w$位，相当于对$2^w$取模，也是减去$2^w$

溢出后的结果肯定比$x,y$小，所以可以作比较来判断有没有溢出

有符号加法

$w$位有符号数的取值范围是：${\color{tomato}{-2^{w-1} \leq x \leq 2^{w-1} - 1}}$
两个有符号数的相加的范围是：${\color{tomato}{-2^{w} \leq x+y \leq 2^{w} - 2}}$

有符号数的溢出分为正溢出和负溢出

$$x+_w^ty=\left\{ \begin{array}{cl} {\color{LightSeaGreen}{x+y-2^w}} & {\color{LightSeaGreen}{2^{w-1} \leq x+y}} & \rm{Positive\enspace overflow}\\ {\color{deepskyblue}{x+y}} & {\color{deepskyblue}{-2^{w-1} \leq x+y < 2^w-1}} & \rm{Normal} \\ {\color{tomato}{x+y+2^w}} & {\color{tomato}{x+y < -2^{w-1}}} & \rm{Negative \enspace overflow}\\ \end{array} \right.$$

• 结果大于等于$2^{w-1}$，发生正溢出，和为${\color{LightSeaGreen}{x+y-2^{w}}}$
• 结果小于$-2^{w-1}$，发生负溢出，和为${\color{tomato}{x+y+2^{w}}}$

如果两个正数相加得到负数，说明是正溢出
如果两个负数相加得到正数，说明是负溢出

2.3.2 减法

减去一个数就相当于加上这个数的相反数（加法逆元）

无符号的加法逆元

如果$x=0$，相反数也是$x^{\prime}=0$

如果$x \geq 0$，如果加到$2^w$会溢出，结果还是0，所以$x+x^{\prime}=2^w=0$，所以相反数是$x^{\prime} = 2^w-x$

有符号数的加法逆元

当$x>Tmin_w$，相反数就是$-x$

当$x=Tmin_w$，因为补码表示的最大值比最小值小1，$|Tmin_w| = |Tmax_w| + 1$，所以要通过负溢出来表示，因为$Tmin_w + Tmin_w = -2^{w-1}-2^{w-1}=-2^w$，会发生负溢出，需要加上$2^w$，就得到$0$，所以$Tmin_w$的加法逆元就是它本身

2.3.3 乘法

乘以$2^k$就相当于左移$k$位，可以把乘法分解为加法和移位
例如：$x$乘以$14=2^3+2^2+2^1$，就相当于$x \cdot (2^3+2^2+2^1) = (x<<3) + (x<<2) + (x<<1)$，这样就把乘法分解为3个移位操作和2个加法操作

2.3.4 除法

除以$2^k$就相当于右移$k$位，注意无符号数是逻辑右移，有符号数是算术右移

• 整数除法向0取整，即负数上取整，整数下取整

负数的补码除法会出现下取整的问题，与规定不符
所以，负数右移的时候要先加上一个偏置

$$\lceil x/y \rceil = \lfloor (x+y-1)/y \rfloor$$

所以负数除以$2^k$需要先加上$2^k-1$，$2^k$就是1左移$k$位

(x < 0 ? x + (1 << k) - 1 : x ) >> k;