CSAPP3e第二章(整数的运算)

发表于 2025-01-25 更新于 2025-02-20 分类于组成原理阅读次数：

整数的运算(第二章 Part2)

无符号数加法溢出

无符号的数的加法溢出规则很简单, 单纯截取后 $w$ 位, 或称对 $2^w$ 取模。因此:

\[ x\ +_w^u\ y = \begin{cases} x + y, & x + y < 2^w, \\ x + y - 2^w, & 2^w \leq x + y < 2^{w+1}. \end{cases} \]

($+_w^u$ 表示最多 $w$ 位下的二进制无符号数加法。下文$+_w^t$ 即 $w$ 位补码加法)

检验无符号数加法溢出

若 $s = x +_w^u y$, 当且仅当 $s < x$ （或等价地 $s < y$）时发生溢出。

(当然, 默认 $x$ 和 $y$ 本身不会溢出, 即在 $[0, UMax_w]$ 的范围内)

原理易证, 分别证明充分性必要性即可, 注意利用以上公式

补码加法溢出

同样是截断, 但因为符号位的存在(还记得我们说的为什么补码最后被实际应用吗? 因为符号位本身是数值的一部分, 在计算中只要通过对 $2^w$ 取模和截断就能运算出正确的数值, 类似一种环绕, 本质就是数论上的同余概念)显得略微复杂。

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

多了就减, 少了就加, 数值都是 $2^w$。

推导就要用到 ”补码和无符号数的位级操作是一样的“。Formally:

\[ x +_w^t y = U2T(T2U(x) +_w^u T2U(y) \]

(严格应写作 $U2T_w$, 此处省略) 由于里面的两个 $T2U$ 只是可能地加上 $2^w$ (当且仅当最高符号位为 $1$), 而这两个带有 $2^w$ 的项都被最外面无符号数加法的截断时的 $\mod 2^w$ 消除了, 所以最后其实就是

\[ x +_w^t y = U2T[(x + y)\mod 2^w]. \]

考虑 $U2T$ 的公式以及上篇文章经典的那张无符号数转补码的数值对应图, 分类讨论即可。

检查补码加法溢出

令 $s = x +_w^t y$, 当且仅当 $x > 0, y > 0$ 但 $s \leq 0$ 或 $x < 0, y < 0$ 但 $s \geq 0$ 时发生溢出。当然这里还是默认 $x, y$ 本身在合理的 $w$ 位可表示的补码范围内。

加法逆元

感兴趣群论的知识可以去 b 站搜一下, 但实际上此处只是涉及一些概念, 浅尝辄止即可。

模数加法形成 阿尔贝群 (Abelian group) . 也就是说, 模数加法可交换、可结合。

还记得那个梗吗？

判断孩子是否有数学天赋就问孩子为什么 1+ 2 = 2 + 1 ?

然后孩子说因为整数集对加法构成阿尔贝群

对于群的操作 “$\cdot$” 和群中的元素 $a$, 单位元 $e$ 是群中唯一满足 $a e = e $ 的元素。

逆元就是对于群中某元素 $a$， $a$ 的逆元 $a^{-1}$ 满足 $a \cdot a^{-1} = e$

这个群的单位元是欧元 $0$ ,

而无符号数 $x$ 的无符号数加法逆元满足:

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

而补码 $x$ 的补码加法逆元满足:

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

乘法

无符号数乘法直接按照模 $2^w$ 截断, 补码还是按照 位级操作与无符号数相同原理 先分别转换成无符号数再按照无符号乘法计算位模式, 最后转换为补码的数值。

乘以 2 的幂次

一个常识是乘以 $2^k$ 就等价于左移 $k$ 位。虽然这一点显而易见也易于证明(通过公式定义即可), 但其实有一些可以说的地方, 例如 $x \cdot 14 = (x << 3) + (x << 2) + (x << 1) = x \cdot (x << 4) - (x << 1)$

具体来说, 如果一个表达式 $x \cdot k$ 的 $k$ 能表示为 $[(0...0)(1...1)(0...0)...(1...1)]$ 即一段的 $0$ 和一段的 $1$ 的序列，考虑一组从位置 $l$ 到位置 $r$ 的 $1$ 序列 $(l \leq r)$, 这个位对乘积的影响可以表达为两个形式:(注意虽然 $l \leq r$ 但其实二进制表示上下标大的在前面)

$(x<<r) + (x<<(r-1)) + ... + (x << l)$ 或

$(x << (r + 1)) - (x << l)$

其实还可以想一想当 $l, r$ 为什么条件时第一种更好(左移和加减次数最少), 为什么条件时第二种更好。这也是 CSAPP 的习题之一。

除以 2 的幂次

你可能会想, 不就是右移 $k$ 位？但右移 $k$ 位计算的是 $\lfloor x / 2^k \rfloor$, 而一般的编程语言中除法是向零取整(即舍去小数点)而不是向下取整的(这点是程序设计课重灾区)。而大多数 OIer 或 ACMer 应该都很熟悉向上取整的方法: $a / b = (a + b - 1) / b $。如果 $a \mod b == 0$ 那么 $b - 1$ 会直接被向下取整舍掉, 否则就会令结果 $+1$。

因此有 C 语言表达式 (x < 0 ? x + (1 << k) - 1 : x) >> k 计算数值 $x / 2^k$。

这个向上取整的方法叫做 偏置(biasing) . 我们甚至还可以用右移 $31$ 位再 and 上掩码等各种手段判负从而优化掉条件语句 ~~这也是习题~~