Csapp中截断数值的推倒公式如何理解

Question

Csapp 2.2.7 truncating numbers.
请问第一行是如何推倒至第二行的，第二行到第三行呢？

谢谢

Answer 1

$mod 2^k$就是对$2^k$取余数，这个余数自然就是不能被$2^k$整除的部分，也就是后$k$位$[2_{k-1}, 2_{k-2}, ..., 2_0]$
所以有公式$$[\sum_{i=0}^{w-1}x_i2^i] mod 2^k = [\sum_{i=0}^{k-1}x_i2^i] mod 2^k$$

Answer 2

第一行的【】中就是一个长度是w位的二进制数一种表示方式
第二行的【】就是一个长度是k位的二进制数的一种表示方式
所以，第一行到第二个就是将w位的数取mod，得到一个k位的数
第二行到第三行是说，k位的数取mod后依旧是k位的数。

举个例子：
13的二进制表示是1101，可以表述为一个长度为4位的二进制数。对它取2^3（即8）的mod。对应第一行。
可以等于是对5（二进制表示是101）取8的mod。对应第二行。
最后，对5（101）取8的mod，结果其实就是5。对应第三行。

Answer 3

因为
$$2^k\quad2^{k+1}\dots $$
这些数
$$mod2^k=0$$
所以原式不为0的只剩下
$$\sum_{i=0}^{k-1}x_i2^i$$

其中$x_i$只可能等于0或者1，由此，$x_i2^i<2^k$恒成立。
所以mod的值只能是$x_i2^i$

这个很好理解，比如8mod16=8, a mod b=a (a<b)