凌云的博客

整数运算

分类：data| 发布时间：2025-02-01 12:04:00

无符号加法

考虑两个非负整数 x 和 y，满足 0 ≤ x, y ≤ 2^w+1-2。表示这个和可能需要 w+1 位。

无符号加法等价于计算模 2^w 的和。可以简单地丢弃 x+y 的 w+1 位表示的高位，来计算这个数值。

如果 x+y < 2^w，和的 w+1 位表示中的最高位会等于 0，因此丢弃它不会改变这个数值。 另一方面，如果 2^w ≤ x+y < 2^w+1 和的 w+1 位表示中的最高位会等于 1，因此丢弃它就相当于从和中减去了 2^w。

我们定义 x 和 y 的运算 ${+}_w^u$ ，这里 0 ≤ x, y < 2^w，如下：

$$\text{x}{+}_w^u\text{y}=\{\genfrac{}{}{0ex}{}{x+y,x+y<2^{\text{w}}}{x+y-2^{\text{w}},2^{\text{w}}\le x+y<2^{\text{w+1}}}$$

$$\text{等式 2.11}$$

这正好是在 C 中执行两个 w 无符号数值加法时我们得到的结果。

当执行 C 程序时，不会将溢出作为错误而发出信号。 不过有时候，我们可能希望判定是否发生了溢出。 比如，假设我们计算 $s\doteq x{+}_u^{w}y$，并且我们想要判定 s 是否等于 x+y。 我们声称当且仅当 s<x（或者等价于 s<y），发生了溢出。 要弄明白这一点，请注意 x+y ≥ x，因此如果 s 没有溢出，我们能够肯定 s ≥ x。 另一方面，如果 s 溢出了，我们有 s = x + y - 2^w。 假设 y < 2^w，我们有 y - 2^w < 0，因此 s = x + y - 2^w < x。

模数加法形成了一种数学结构，称为阿贝尔群，也就是说，它是可交换的和可结合的。 它有一个单位元 0，并且每个元素都有一个加法逆元。让我们考虑这样一个情况：w 位的无符号数的集合，执行加法运算 ${+}_w^u$。 执行每个值 x，必然有某个值 ${-}_w^u$ 满足${-}_w^u{+}_w^u=0$

对于 0 ≤ x < 2^w 其加法逆元为：

$${\text{-x}}_w^u=\{\genfrac{}{}{0ex}{}{x,x=0}{2^{\text{w}}-x,x>0}$$ $$\text{等式 2.12}$$

二进制补码加法

两个数的 w 位二进制补码之和与无符号之和有完全相同的位级表示。 实际上，大多数计算机使用同样的机器指令来执行无符号或者有符号加法。 我们定义字长为 w 的二进制补码加法，在运算数 x 和 y 上表示为 ${+}_w^t$，满足 ${-2}^{\text{w-1}}\le x,y\le 2^{\text{w-1}}$：

$$x{+}_w^{t}y\doteq {\text{U2T}}_w\left({\text{T2U}}_w\right(x\left){+}_w^u{\text{T2U}}_w\right(y\left)\right)$$ $$\text{等式 2.13}$$

根据等式 2.5，我们可以把 T2U_w 写成 x_w-12^w+x，把 T2U_y 写成 y_w-12^w+y。使用模数加法的属性，我们可以得到：

$$x{+}_w^{t}y={\text{U2T}}_w\left({\text{T2U}}_w\right(x\left){+}_w^u{\text{T2U}}_w\right(y\left)\right)$$ $$={\text{U2T}}_w\left[\right(x_{\mathrm{w-1}}{2}^w+x+y_{\mathrm{w-1}}{2}^w+y)mod{2}^w]$$ $$={\text{U2T}}_w\left[\right(x+y)mod{2}^w]$$

对于范围在 -2^w-1 ≤ x, y ≤ 2^w-1-1 的 x 和 y 实时运算 ${+}_w^t$ 时，我们有：

$$x{+}_w^{t}y=\{\begin{array}{ccc}x+y-2^w,& 2^{\text{w-1}}\le x+y& 正溢出\\ x+y,& {-2}^{\mathrm{w-1}}\le x+y<2^{\mathrm{w-1}}& 正常\\ x+y+2^w,& x+y\le -2^{\mathrm{w-1}}& 负溢出\end{array}$$ $$\text{等式 2.14}$$

二进制补码的非

范围 -2^w-1 ≤ x < 2^w-1 中的每个数字 x 都有 ${+}_w^t$ 下的加法逆元：首先对于 x ≠ -2^w-1，它的加法逆元是 -x。 另一方面，对于 x=-2^w-1=TMin_w，-x=2^w-1 不能被表示为一个 w 位的数。 我们声明这个值本身就是它在 ${+}_w^t$ 下的加法逆元。 ${-2}^{\mathrm{w-1}}{+}_w^t{-2}^{\mathrm{w-1}}$ 的值由等式 2.14 的第三种情况给出，得到 ${-2}^{\mathrm{w-1}}{+}_w^t{-2}^{\mathrm{w-1}}={-2}^{\mathrm{w-1}}+{-2}^{\mathrm{w-1}}+2^w=0$

综上，对于范围在 -2^w-1 ≤ x < 2^w-1 内的 x，二进制补码的非运算如下：

$${-}_w^{t}x=\{\begin{array}{cc}{2}^{\mathrm{w-1}},& x={-2}^{\mathrm{w-1}}\\ -x,& x>{-2}^{\mathrm{w-1}}\end{array}$$ $$\text{等式 2.15}$$

一种有名用来执行二进制补码的非的技术是，对每个位取反（或取补）然后将结果加 1。 在 C 中，这可以写成 ~x+1。 为了验证这种技术的正确性，可以观察，对于每一个位 x_i，我们有 ~x=1 - x_i。 设 $\overrightarrow{x}$ 是一个长度为 w 的位向量， $x\doteq {\mathrm{B2T}}_w\left(\overrightarrow{x}\right)$ 是它表示的二进制补码数。 根据等式 2.3 取反的位向量 $~\overrightarrow{x}$ 有如下数值：

$${\text{B2T}}_w(~\overrightarrow{x})=-(1-x_{\mathrm{w-1}})2^{\mathrm{w-1}}+\sum _{\mathrm{i=0}}^{\mathrm{w-2}}(1-x_i)2^i$$ $$=[-2^{\mathrm{w-1}}+\sum _{\mathrm{i=0}}^{\mathrm{w-2}}{2}^i]-[-x_{\mathrm{w-1}}{2}^{\mathrm{w-1}}+\sum _{\mathrm{i=0}}^{\mathrm{w-2}}{x}_i{2}^i]$$ $$=[-2^{\mathrm{w-1}}+2^{\mathrm{w-1}}-1]-{\mathrm{B2T}}_w\left(\overrightarrow{x}\right)$$ $$=-1-x$$

上述的推导中，关键的简化是 ${\sum }_{\mathrm{i=0}}^{\mathrm{w-2}}{2}^i=2^{\mathrm{w-1}}-1$。

无符号乘法

范围 0 ≤ x, y ≤ 2^w - 1 内的整数 x 和 y 可以被表示为 w 位无符号数字，但是它们的乘积 x ∙ y 的取值范围为 0~(2^w-1)²=2^2w-2^w+1+1 之间。 这可能需要 2w 位来表示。

在 C 语言中无符号乘法被定义为产生 2w 位的整数积的低 w 位表示的值。 根据等式 2.9，我们可以看出这等价于计算模 2^w 的乘法。 因此，w 位无符号乘法运算 ${*}_w^u$ 的效果为：

$$x{*}_w^{u}y=(x\bullet y)mod{2}^w$$ $$\text{等式 2.16}$$

模运算形成了环，因此我们可以推断 w 位数字上的无符号运算形成了环 <{0, 1, ..., 2^w-1}, ${+}_w^u$, ${-}_w^u$, ${*}_w^u$, 0, 1}>。

二进制补码乘法

范围 -2^w-1 ≤ x, y ≤ 2^w-1 - 1 内的整数 x 和 y 可以被表示为 w 位的二进制补码数字，但是它们的乘积 x ∙ y 的取值范围在 -2^w-1 ∙ (2^w-1-1)=-2^w-2+2^w-1 到 -2^w-1 ∙ -2^w-1=2^2w-2 之间。 想要用二进制补码表示这个乘积，需要 2w 位——大多数情况下只需要 2w-1 位，但是特殊情况 2^2w-2 需要 2w 位（包括一个符号位0）。

C 中的有符号乘法是通过将 2w 位的乘积截断为 w 位来实现的。 根据等式 2.10，w 位的二进制补码乘法运算 ${*}_w^t$ 的效果为：

$$x{*}_w^{t}y={\mathrm{U2T}}^w\left(\right(x\bullet y)mod{2}^w)$$ $$\text{等式 2.17}$$

对于无符号和二进制补码乘法来说，乘法运算的位级表示都是一样的。 也就是，给定长度为 w 位的向量 $\overrightarrow{x}$ 和 $\overrightarrow{y}$，无符号乘积 ${\mathrm{B2U}}_w\left(\overrightarrow{x}\right){*}_w^u{\mathrm{B2U}}_w\left(\overrightarrow{y}\right)$ 的位级表示与二进制补码乘积 ${\mathrm{B2T}}_w\left(\overrightarrow{x}\right){*}_w^t{\mathrm{B2T}}_w\left(\overrightarrow{y}\right)$ 的位级表示相同。 这表明机器可以用一种乘法指令来进行有符号和无符号乘法。

设 $x={\mathrm{B2T}}_w\left(\overrightarrow{x}\right)$ 和 $y={\mathrm{B2T}}_w\left(\overrightarrow{y}\right)$ 是这些位模式表示的二进制补码值，而 $x\text{'}={\mathrm{B2U}}_w\left(\overrightarrow{x}\right)$ 和 $y\text{'}={\mathrm{B2U}}_w\left(\overrightarrow{y}\right)$ 是这些位模式表示的无符号值。

根据等式 2.5，我们有 $x\text{'}=x+x_{w-1}{2}^w$ 和 $y\text{'}=y+y_{w-1}{2}^w$。计算这些值的模 2^w 乘积得到以下结果：

$$x\text{'}\bullet y\text{'}=\left[\right(x+x_{w-1}{2}^w)\bullet (y+y_{w-1}{2}^w\left)\right]mod{2}^w$$ $$=[x\bullet y+(x_{w-1}y+y_{w-1}x)2^w+x_{w-1}{y}_{w-1}{2}^{2w}]mod{2}^w$$ $$=(x\bullet y)mod{2}^w$$ $$\text{等式 2.18}$$

因此 $x\bullet y$ 和 $x\text{'}\bullet y\text{'}$ 的低 w 位相同的。

下表展示了不同的三位数字乘法的结果。

模式	x	y	x ∙ y	截断的 x ∙ y
无符号 二进制补码	5 [101] -3 [101]	3 [011] 3 [011]	15 [001111] -9 [110111]	7 [111] -1 [111]
无符号 二进制补码	4 [100] -4 [100]	7 [111] -1 [111]	28 [011100] 4 [000100]	4 [100] -4 [100]
无符号 二进制补码	3 [011] 3 [011]	3 [011] 3 [011]	9 [001001] 9 [001001]	1 [001] 1 [001]

w 位数字上的无符号运算和二进制补码运算是同构的——运算 ${+}_w^u$、 ${-}_w^u$、 ${*}_w^u$ 和 ${+}_w^t$、 ${-}_w^t$、 ${*}_w^t$ 有相同的位级效果。 据此，我们可以推断 w 位数字上的二进制补码运算形成了环 <{0, 1, ..., 2^w-1}, ${+}_w^t$, ${-}_w^t$, ${*}_w^t$, 0, 1}>。

乘以 2 的幂

在大多数机器上，乘法运算相当慢，需要 12 或者更多个时钟周期，而其他整数运算——比如：加法、减法、位级运算和移位——只需要 1 个时钟周期。 因此编译器使用的一项重要的优化是试着使用移位和加法运算的组合来代替常数因子的乘法。

设 x 为位模式 [x_w-1, x_w-2, ..., x₀] 表示的无符号整数。 那么对于任何 k ≥ 0，我们都认为 x2^k 的位级表示是由 [x_w-1, x_w-2, ..., x₀, 0, ..., 0] 给出的，这里右边增加了 k 个 0。 这个等式可以通过 等式2.1 推导出来：

$${\mathrm{B2U}}_{w+k}\left(\right[x_{w-1},x_{w-2},\mathrm{...},x_0,0,\mathrm{...},0\left]\right)=\sum _{i=0}^{w-1}{x}_i{2}^{i+k}$$ $$=\left[\sum _{i=0}^{w-1}{x}_i{2}^i\right]\bullet 2^k$$ $$=x{2}^k$$

对于 k < w，我们可以将移了位的位向量截断到长度 w，得到 [x_w-k-1, x_w-k-2, ..., x₀, 0, ..., 0]。 根据等式 2.9 和等式 2.16 我们有： $x{2}^{k}mod{2}^w=x{*}_w^u{2}^k$。 因此，对于无符号变量 x，C 表达式 x<<k 等价于 x * pwr2k，这里 pwr2k 等于 2^k。

通过类似的推理，我们可以给出，对于一个位模式为 [x_w-1, x_w-2, ..., x₀] 的二进制补码数 x，以及范围在 0 ≤ k < w，内任意的 k，位模式 [x_w-k-1, x_w-k-2, ..., x₀, 0, ..., 0] 就是 $x{*}_w^t{2}^k$ 的二进制补码表示。

除以 2 的幂

在大多数机器上，整数除法比整数乘法还要慢——需要 30 或者更多的时钟周期。 除以 2 的幂也可以通过移位运算来实现，只不过我们用的是右移而不是左移。 对于无符号和二进制补码数，分别使用逻辑移位和算术移位来达到目的。

整数除法总是舍入到 0 的。 对于 x ≥ 0 和 y > 0，结果会是 ⌊x/y⌋，这里对于任何实数 a，⌊a⌋ 定义为唯一的整数 a'，使得 a' ≤ a < a'+1。 例如：⌊3.14⌋=3，⌊-3.14⌋=-4，⌊3⌋=3。

考虑在一个无符号数上执行逻辑右移的效果。 设 x 为位模式 [x_w-1, x_w-2, ..., x₀] 表示的无符号整数，而 k 的取值范围为 0 ≤ k < w。 设 x' 为 w-k 位表示的无符号数 [x_w-1, x_w-2, ..., x_k]，而 x'' 为 k 位表示 [x_k-1, x_k-2, ..., x₀] 的无符号数。 我们有 x'= ⌊x/2^k⌋。 证明如下：根据等式 2.1，我们有 $x={\sum }_{i=0}^{w-1}{x}_i{2}^i$， $x={\sum }_{i=\mathrm{k}}^{w-k-1}{x}_i{2}^{i-k}$ 和 $x={\sum }_{i=0}^{k-1}{x}_i{2}^i$。 因此，我们可以把 x 写为 x=2^kx'+x''。 可以观察到 $0\le x\text{'}\text{'}\le {\sum }_{i=\mathrm{k}}^{w-k-1}{2}^i=2^k-1$，因此 0 ≤ x'' < 2^k，这意味着 ⌊x''/2^k⌋ = 0。 因此 ⌊x/2^k⌋ = ⌊x'+x''/2^k⌋=x'。

现在考虑对一个二进制补码数进行算术右移的结果。 设 x 为位模式 [x_w-1, x_w-2, ..., x₀] 表示的二进制补码数，而 k 的取值范围为 0 ≤ k < w。 设 x' 为 w-k 位表示的二进制补码数 [x_w-1, x_w-2, ..., x_k]，而 x'' 为 k 位表示 [x_k-1, x_k-2, ..., x₀] 的无符号数。 通过对无符号情况的类似分析，我们有 x=2^kx'+x''，而 0 ≤ x'' < 2^k，得到 x'= ⌊x/2^k⌋。 此外，我们可以观察到，算术右移位向量 [x_w-1, x_w-2, ..., x₀] k 位，得到位向量 [x_w-1,...,x_w-1, x_w-2, ..., x_k]，它刚好就是将 [x_w-1, x_w-2, ..., x_k] 从 w-k 位符号扩展到 w 位。 因此，这个移位了的位向量就是 ⌊x/y⌋ 的二进制补码表示。

对于 x ≥ 0，我们的分析结果表明这个移位的结果就是所期望的值。 不过对于 x < 0 和 y > 0，整数除法的结果应该是 ⌈x/y⌉，这里对于任何实数 a， ⌈a⌉ 被定义为使得 a'-1 < a ≤ a' 的唯一整数 a'。 也就是说，整数除法应该将负的结果向上朝零舍入。 例如 -5 的四位表示为 [1011]。如果我们将其算术右移移位我们得到 [1101]，这是 -3 的二进制补码表示。

我们可以通过移位前“偏置(biasing)”这个值，修正这种不合适的舍入。 这种技术利用的是这样一个属性：对于整数 x 和有 y>0 的 y，⌈x/y⌉=⌊(x+y-1)/y⌋。 因此对于 x<0，如果我们在右移之前，先将 x 加上 2^k-1，那么我们就会得到正确的舍入结果了。 这个分析表明对于使用算术右移的二进制补码机器，C 表达式：

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

等价于 x/pwr2k。