整数运算

无符号加法怎样处理溢出？

• 对满足 $0\le x,y<2^w$ 的 $x$ 和 $y$:

$x+_w^u y=\begin{cases}x+y, & x+y<2^w\\ x+y-2^w, & 2^w\le x+y<2^{w+1}\end{cases}$

• 正常: 和未超出 w 位可表示范围;
• 溢出: 和超出 $2^w$ 时丢弃进位, 等价于对 $2^w$ 取模;

无符号数的逆元怎么求？

• 对满足 $0\le x<2^w$ 的 $x$:

$-_w^u x=\begin{cases}x, & x=0\\ 2^w-x, & x>0\end{cases}$

• 结论: 无符号逆元就是 $2^w-x$, 与补码 $-x$ 的位模式完全相同;

补码加法怎样处理溢出？

• 对满足 $-2^{w-1}\le x,y\le 2^{w-1}-1$ 的 $x$ 和 $y$:

$x+_w^t y=\begin{cases}x+y-2^w, & 2^{w-1}\le x+y\\ x+y, & -2^{w-1}\le x+y<2^{w-1}\\ x+y+2^w, & x+y<-2^{w-1}\end{cases}$

• 正溢出: 结果减 $2^w$, 得到一个大负数;
• 负溢出: 结果加 $2^w$, 得到一个大正数;

补码的逆元怎么求？

• 对满足 $TMin_w\le x\le TMax_w$ 的 $x$:

$-_w^t x=\begin{cases}TMin_w, & x=TMin_w\\ -x, & x>TMin_w\end{cases}$

• 特例: 最小值的逆元仍是自身, 因为 $|TMin_w|=|TMax_w|+1$;

无符号乘法和补码乘法的结果是什么？

• 无符号乘法:

$x*_w^u y=(x\cdot y)\bmod 2^w$

• 补码乘法:

$x*_w^t y=U2T_w((x\cdot y)\bmod 2^w)$

• 共同点: 都先算完整乘积再截断到 w 位;
• 推论: 两种乘法的位级结果相同, 只是解释方式不同;

编译器如何用移位实现乘除？

• 乘以 2 的幂: 左移, 右端补 0;
• 乘以任意常数: 乘法指令开销大, 编译器尝试用移位与加减的组合替代;
• 除以 2 的幂: 右移, 左端保留符号位或补 0;
• 结果: 无符号除法满足 $x'=\lfloor x/2^k\rfloor$;