CS:APP 第二章部分作业解答

第 2 章 信息的表示和处理

2.65

每一次操作，将 $w$ 位的整数 $x$ 从中间分成两个 $\frac{w}{2}$ 位的整数 $y$ 和 $z$，接着令 $\texttt{x = y \^{} z}$。操作 5 次后即得到答案。

我们将这样的思路称为“折半递归法”。

2.66

每一次操作，令 $\texttt{x = x | (x >> y)}$，其中 $y=1,2,4,\cdots$。操作 5 次后即实现了提示的转换。

2.75

$x,y$ 是补码数，$x'=T2U_w(x),y'=T2U_w(y)$。

$$\begin{aligned} x'\cdot y'&=(x+x_{w-1}\cdot 2^w)\times(y+y_{w-1}\cdot 2^w)\\ &=x\cdot y+(x_{w-1}\cdot y+y_{w-1}\cdot x)2^w+x_{w-1}\cdot y_{w-1}\cdot 2^{2w} \end{aligned}$$

进一步，令 $\texttt{a = signed\_high\_prod(x, y), b = unsigned\_high\_prod(x', y')}$，有 $$b\cdot 2^w+x'*^u_w y'=a\cdot 2^w+T2U_w(x*^t_wy)+(x_{w-1}\cdot y+y_{w-1}\cdot x)2^w+x_{w-1}\cdot y_{w-1}\cdot 2^{2w}$$

化简得 $$b=a+x_{w-1}\cdot y+y_{w-1}\cdot x+x_{w-1}\cdot y_{w-1}\cdot 2^w$$

即 $$\begin{aligned} b&=(a+x_{w-1}\cdot y+y_{w-1}\cdot x)\bmod 2^w\\ &=T2U_w(a)+^u_t x_{w-1}\cdot y'+^u_t y_{w-1}\cdot x' \end{aligned}$$

2.80

$$\verb|threefourths(x)|=\left\{\begin{aligned} &3\cdot\lfloor x/4\rfloor+x\bmod 3-[x\bmod 3\neq0], &x\ge0\\ &3\cdot\lfloor x/4\rfloor+x\bmod 3, &x<0 \end{aligned}\right.$$

2.97

不失一般性地，令 $i$ 为正数。$i$ 的有效位数不超过 24 位的时候可以不舍入地直接转换成 $\verb|float|$。当有效位数超过 24 位时，一般而言，取最高位往后第 23 位作为舍入时的最低有效位，但是当最高位及其后 23 位均为 1，并且向上舍入后，有效位数由于进位而超过预期的 24 位，此时最低有效位应取高一位。

代码参见 https://git.gzezfisher.top/FISHER_/CSAPP-sol/src/branch/main/homework/chapter2。