注:本节内容为 CS:APP 第三版中文版 P67 的旁注。
内容
书上已经为我们证明了「补码乘法与无符号数乘法的位级表示相同」这一命题,在这里我想讨论一下它的含义,以及到底意味着什么。
首先不妨写出两种乘法的定义:
$$
x *_w^u y = (x \cdot y) \pmod {2^w}
$$
$$
x *_w^t y = U2T((x \cdot y) \pmod {2^w})
$$
上述结论的表达式:
$$
U2B(B2U(\vec x) *_w^u B2U(\vec y)) = T2B(B2T(\vec x) *_w^t B2T(\vec y))
$$
证明:
下面不再沿用上面的 $x, y$,只沿用 $\vec x, \vec y$
$$
x = B2T(\vec x) = -x_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i
$$
$$
x' = B2U(\vec x) = +x_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i
$$
$$
y = B2T(\vec y) = -y_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} y_i 2^i
$$
$$
y' = B2U(\vec y) = +y_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} y_i 2^i
$$
故有
$$
x' = x + x_{w-1}2^w
$$
$$
y' = y + y_{w-1}2^w
$$
由
$$
\begin{aligned}
& x' *_w^u y' = (x' \cdot y') \pmod {2^w} \\
=& [(x + x_{w-1} 2^w)(y + y_{w-1} 2^w)] \pmod {2^w} \\
=& \boxed{\color{skyblue} {(x \cdot y) \pmod {2^w}}}
\end{aligned}
$$
则
$$
\begin{aligned}
& T2B(\boxed{x *_w^t y}) \\
=& T2B(\boxed{U2T(x \cdot y \pmod {2^w})}) \\
=& \boxed {T2B} (\boxed{U2T} (x \cdot y \pmod {2^w})) \\
=& U2B(\boxed{\color{skyblue} {x \cdot y \pmod {2^w}}}) \\
=& U2B(x' *_w^u y')
\end{aligned}
$$
得证。
讨论
现在有两个向量 $\vec x, \vec y$:
$\vec x, \vec y$ 表示为 补码时相乘,与 $\vec x, \vec y$ 表示为 无符号数相乘,这两种情况得到的结果的位级表示是相同的。
也就是说,可以使用相同的表示和硬件实现来进行两种不同的乘法。