第2章 信息的表示和处理

2.3 整数运算

2.3.1 无符号加法

对于参数x和y的相关运算，操作 $+_w^u$ 描述为：

原理：无符号数加法

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

$$
x +_w^u y =
\begin{cases}
x + y, & x + y < 2^w \quad \text{正常} \
x + y - 2^w, & 2^w \le x + y < 2^{w+1} \quad \text{溢出}
\end{cases}
\tag{2.11}
$$

此外，判定是否发生的溢出的原理如下：
原理：检测无符号数加法中的溢出
对在范围 $0 \le x, \ y \le UMax_w$ 中的 $x$ 和 $y$，令 $s \mathrel{\dot{=}} x +_w^u y$。则对计算 $s$，当且仅当 $s < x$（或者等价地 $s < y$）时，发生了溢出。

假发的逆操作可以表述如下：
原理：无符号数求反
对满足 $0 \le x < 2^w$ 的任意 $x$，其 $w$ 位的无符号逆元 $-_w^u x$ 由下式给出：

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

2.3.2 补码加法

补码加法的相关原理如下：
原理：补码加法
对满足 $-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 \quad \text{正溢出} \
x + y, & -2^{w-1} \le x + y < 2^{w-1} \quad \text{正常} \
x + y + 2^w, & x + y < -2^{w-1} \quad \text{负溢出}
\end{cases}
$$

2.3.3 补码的非

补码的非原理如下：
原理：补码的非
对满足 $TMin_w \le x \le TMax_w$ 的 $x$，其补码的非 $-_w^t x$ 由下式给出：

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

2.3.4 无符号乘法

将一个无符号数截断为 $w$ 位等价于计算该值模 $2^w$，得到：

原理：无符号数乘法

对满足 $0 \le x, \ y \le UMax_w$ 的 $x$ 和 $y$ 有：

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

2.3.5 补码乘法

补码乘法的原理如下：
原理：补码乘法

对满足 $TMin_w \le x, \ y \le TMax_w$ 的 $x$ 和 $y$ 有：

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

对于无符号和补码乘法来说，乘法运算的位级表示都是一样的。

2.3.6 乘以常数

乘以2的幂的原理如下：
原理：乘以 2 的幂

设 $x$ 为位模式 $[x_{w-1}, \ x_{w-2}, \ \cdots, \ x_0]$ 表示的无符号整数。那么，对于任何 $k \ge 0$，我们将 $x$ 拓展为 $[x_{w-1}, \ x_{w-2}, \ \cdots, \ x_0, \ 0, \ 0, \ \cdots, \ 0]$ 给出了 $x2^k$ 的 $w+k$ 位的无符号表示，这里右边增加了 $k$ 个 0。

其余的情况与之类似。

2.3.7 除以2的幂

原理：除以 2 的幂的无符号除法

C 变量 $x$ 和 $k$ 有无符号数值 $x$ 和 $k$，且 $0 \le k < w$，则 C 表达式 $x >> k$ 产生数值 $\lfloor x/2^k \rfloor$。

原理：除以 2 的幂的补码除法，向下舍入

C 变量 $x$ 和 $k$ 分别有补码值 $x$ 和无符号数值 $k$，且 $0 \le k < w$，则当执行算术移位时，C 表达式 $x >> k$ 产生数值 $\lfloor x/2^k \rfloor$。