注：本节内容为 CS:APP 第三版中文版 P70 的旁注。

内容

补码 $x$ 向左位移 $k$ 位，与乘以 $2^k$ 等价。

证明

我们已经得到了下面两个结论：

1. 补码乘法与无符号数乘法的位级表示相同，硬件实现相同 (P67)
2. 无符号数乘以 $2^k$ 与向左位移 $k$ 位等价

试论证：补码 $x$ 向左位移 $k$ ($k < w$) 位，与乘以 $2^k$ 等价

证明：

对于补码数 $2^k$，因为 $k < w$，所以 $T2U(2^k)=2^k$，也就是其的补码值为无符号值相同，我们不妨将其的位级表示记作 $\vec y$。

现在有数 $\vec x$，其与 $2^k$ 的无符号乘表示为：

$$
B2U(\vec x) *_w^u B2U(\vec y)
$$

因为这个操作与想左位移 $k$ 位等价，则：

$$
U2B(B2U(\vec x) *_w^u B2U(\vec y)) = \vec x << k
$$

又因为无符号数与补码的乘法的位级表示等价，即

$$
U2B(B2U(\vec x) *_w^u B2U(\vec y)) = T2B(B2T(\vec x) *_w^u B2T(\vec y))
$$

所以

$$
T2B(B2T(\vec x) *_w^u B2T(\vec y)) = \vec x << k
$$

得证。