这几天一直在写《深入理解计算机系统》第二版中第二章的家庭作业，费了几天的时间，终于完成了。当初碰到若干题不会，在网上也没有搜索到答案。现在，我把这份自己完成的答案分享上来，与大家交流思想。其中错误一定会存在，如果有错误，希望指出来，共同进步。
2.67
A：左移位数大于等于int长度。
B：可以考虑用两次左移来实现<<32：
int set_msb=1<<31;
int beyond_msb=set_msb<<1;
C：可以考虑用三次左移来实现<<31与<<32：
int temp=1<<15;
temp<<=15;
int set_msb=temp<<1;
int beyond_msb=temp<<2;
2.68
Q：Clear all but least significant n bits of x，即保留x的低n位，1<=n<=w
A：可以参考2.66的提示。生成低n位全为1，其余位全为0的掩码，通常想到的是
(1<<n)-1
但是n==w的时候就会出错，左移的位数等于int长度（见2.67A），这时我们可以采用两次左移来实现：先生成低n-1位全为1，其余位全为0的掩码m，然后让m左移1位，然后加1即可，手工检验n==1时此情形仍满足，故最后的掩码为{[1<<(n-1)-1]<<1+1}，此掩码与x相与即可：
int lower_bits(int x, int n)
{
return ((1<<(n-1)-1)<<1+1)&x;
}
2.69
Q:：Do rotating right shift. Assume 0<=n<w
A：实际上相当于将x循环右移n位。我们先取x的低n位，要特别注意n==0的情形，参照2.68，使用((1<<n)-1)&x来取得x的低n位，之所以不采用2.68最终答案所示的方法的原因是n可以取到0，但是取不到w，而2.68中，n取不到0，而能取到w。
然后我们将x的高(w-n)位右移n位，在题目假设（P154页）中，右移操作是算数右移，高n位扩展了x的符号位，而我们需要的是逻辑右移。逻辑右移的解法如2.63中所示：
unsigned srl(unsigned x, int k)
{
unsigned xsra = (int) x>>k;
return ((1<<(w-k-1)-1)<<1+1)^xsra;
}
同时需要注意n为0的情形，处理该情形的方法如2.68所述。将x的低n位左移w-n位，异或上slr(x,n)即可：
((((1<<n)-1)&x)<<(w-n-1)<<1)^slr(x,n)
在上式中，同样要注意k=0的情形。
2.70
Q：Return 1 when x can be represented as an n-bit, 2’s complement number; 0 otherwise. 1<=n<=w.
A：对于w位的二进制补码数x，它能不能表示成n位的二进制补码数需要看它的最高w-n+1位是不是全0（正数）或者全1（负数）。这是由于：
我们考虑一个n-bit的二进制补码数a，最高位（第n-1位）是符号位。对于正数，有a[n-1]=0，将其扩展为w-bit时，第n-1位及其左边的w-n位都为0。这个条件是充分必要的，我们可以反证出，如果前面最高的w-n+1位中（除了最高位），某一位有1，则一定不能用n-bit的二进制补码数表示出。
而对于负数，有a[n-1]=1，将其扩展为w-bit时，第n-1位及其左边的w-n位都为1。这个条件同样是充分必要的，在此不再进行说明。
由此我们可以得到解法：（1）用掩码屏蔽掉x的高w-n位，即取得00…x[n-1]x[n-2]…x[0]。（2）然后将x[n-1]扩展到最高的w-n位中，得到x’=x[n-1]x[n-1]…x[n-1]x[n-2]…x[0]。（3）最后return x’==x即可。
步骤：
（1）y= (~((~0)<<n-1<<1))&x（分两次左移，为了处理n==w的情形）
（2）z=y>>n-1，z[0]是符号位，z==1为负，z==0为正就是符号位。
x’=((0-z)&(~0<<n-1<<1))|y
（3）return x’==x
2.71
A：packed_t是无符号数，而它包装的4个字节都是有符号数，1byte的包装在无符号数中的有符号数扩展后符号位并没有扩展。例如，1byte的0xFF表示-1，而扩展成32位后应该为0xFFFFFFFF。而按照原函数中所示，扩展后结果是0x000000FF。
B：其实这个题可以将unsigned转换成signed，然后利用算数右移来取得高位符号位的扩展。但是我们有另外一个解法：
unsigned x=word>>(bytenum<<3);
x<<=24;
x>>=24;
unsigned y=x>>7;
y<<=8;
return x-y;
这个解法不理解的话，自己动手找个示例画一画就理解其中的原理了。
2.72
A：sizeof返回size_t，实际上是无符号整型，而maxbytes-sizeof(val)则会隐式装换为无符号数减法，所的结果始终是正数。测试条件>=0始终成立。
B：maxbytes>=0&&maxbytes>=sizeof(val)
2.73
编写一个函数，当正溢出时，将结果设为Tmax，当负溢出时，将结果设置为Tmin。
首先，我们需要判断是否发生了溢出：x、y同号，而与x+y异号时则发生了溢出：即(1)=((x^(x+y))&(y^(x+y))>>(w-1)。经过这个式子处理，发生溢出时，(1)式结果为1111….111，未发生溢出时，(1)式结果为0000….000。
然后，我们判断发生的溢出是正溢出还是负溢出：即
(2)=(1)&(x>>(w-1))，正溢出时，(2)为0000…000；负溢出时，(2)为11111…111。
未发生溢出时，结果为x+y，而发生溢出时，(x+y)这部分结果需要屏蔽掉，代之以相应的Tmax或者Tmin。故最终的结果包含了(x+y)|(1)。当x+y没有发生溢出时，这部分结果为x+y，而发生溢出时，这部分结果为1111…111。而当正溢出时，我们需要的结果是0111…111，负溢出时，我们需要的结果是1000…000，即我们需要在(x+y)|(1)的基础上减去相应的值：
当未发生溢出时，减去0
当正溢出时，减去1000…000
当负溢出时，减去0111…111
综上所述，我们可以得到需要减去的那部分的值的表达式：
(1)&((1<<(w-1))^(2))。故最终的结果为：
(x+y)|(1)- (1)&((1<<(w-1))^(2))，其中(1)、(2)的表达式如上述分析中所示。
2.74
这道题是测试减法是否发生了溢出。如果我们一下子不好考虑的话，先分析在减法中哪些情况会发生溢出。设x-y=z，
当x>0，y<0，z<=0时会发生溢出；
当x<0，y>0，z>=0时会发生溢出。
即x、y异号，并且x与z异号时会发生溢出。特别注意z=0的情形。
最后的答案可以写为：
return (x^y!=0)&&(z==0||x^z!=0)
2.75
设两个bit串的signed表示为x’、y’，unsigned表示为x，y。根据本章所学，有x’=x+x[w-1]*2w，y’=y+y[w-1]*2w。
x’*y’ = (( x+x[w-1]*2w) * (y+y[w-1]*2w) mod 2w
=(x*y+(y*x[w-1]+x*y[w-1])*2w+x[w-1]*y[w-1]*2w) mod 2w
注意上式，(x*y)的高w位在(x*y)中计算出，x’*y’相对于x*y高w位所多出的数是y*x[w-1]+x*y[w-1]。故经过unsigned_high_prod计算出的结果，需要加上x（当y为负时），与y（当x为负时），就是signed_high_prod的结果。
2.76
A：a<<2+a
B：a<<3+a
C：a<<5-a<<1
D：a<<3-a<<6
2.77
书中P130页有原理叙述。对于本题，我们首先需要判断x是正数还是负数：
int a=x>>w-1;
a==111….111则为负数，a==000….000则为正数。正数时不用额外考虑，而负数时需要加上一个bias偏差来向0舍入：
int result=((y-1)&a+x)/y，y=1<<k，带入之后即可得到最终答案。
2.78
5*x/8：
x<<2+x得到5*x，而除以8的操作需要利用2.77题的结果，最终结果是： return divide_power(x<<2+x,3)。
2.79
这道题与2.78的唯一区别是计算5x/8时不能发生溢出。因为5x/8=x/2+x/8。当x为负数时，我们需要求得5x/8向上舍入的结果，在博客上我们使用celling(x)来表示x向上舍入的正数。我们可以通过对几个x的取值进行验证，得到如下关系：
celling(5x/8)=celling(x/2)+celling(x/8)+1，当x=-5-8k或-7-8k，k=0,1,2…
celling(5x/8)=celling(x/2)+celling(x/8)，其他情况。
由2.77可以得到：
celling(x/2)=divide_power2(x,1)
celling(x/8)=divide_power2(x,3)
下面判断x=-5-8k或者x=-7-8k。负值不好判断，而正值比较好判断，即：-x=5+8k，后3位为101。而-x=-7+8k，后三位为111。
故我们可以得到，
celling(5x/8)= celling(x/2)+celling(x/8)+(-x&0x5||-x&0x7)&0x1。
而当x为正数时，我们也需要经过相似的判断，经过计算，可以知道当x=5+8k或x=7+8k时，同样需要多加一个1。
故而，最后总的式子为：
celling(5x/8)= celling(x/2)+celling(x/8)+(-x&0x5||-x&0x7||x&0x5||x&0x7)&0x1
2.80
A：~((1<<n)-1)，注意此时0<n<w。
B：(1<<(n+m)-1)-(1<<m-1)=1<<(n+m)-1<<m。
2.81
A：错误，考虑x=0，y=1<<31，x>y，而-x>-y。
B：正确。数学中常用的分配律、结合律即可证明，<<5即乘以32。
C：错误。~x+~y=(-x-1)+(-y-1)=-(x+y)-2，不等于-(x+y)-1
D：正确的。signed与unsigned的加法计算在本质上是一致的。
E：正确。右移会向小值舍入。
2.82
A：我们要求出那个无穷循环的串的数学公式表示。令其为V，则有
V<<k=V+Y（高等数学知识）
则V=Y/(2k-1)
B：(a) 1/7 (b) 0.6 (c) 1/9
2.83
浮点数最高位为符号位。先处理-0、+0比较的情况：
ux<<1==0&&uy<<1==0
x为正，y为正：
sx==0&&sy==0&&ux>=uy
x为负，y为负：
sx==1&&sy==1&&ux<=uy
x为正，y为负：
!sx&&sy
以上式子使用||连接起来就是最终答案。
2.84
A：f=0.01，M=1.01，E=2。注意到E=2而原始的exp-bias=E，exp=1+2k-1。
B：f=0.11…1，M=1.11…1。而注意要精确表示最大的奇数。f的最后一个1一定要保留，所以E最大为n。此时，原始的exp=n+2k-1-1。
C：最小的正normalized值的表示为
2^(2-2k-1)。要求它的倒数，则指数部分应该是2^(2k-1-2)，以使得乘积为1。而数值部分，则为0。
2.91
unsigned sign=f>>31;
unsigned exp=f>>23&0xFF;
unsigned frac=f&0x7FFFFF;
if(!(exp^0xFF==0&&frac!=0)) f|=1<<31;
return f;
2.92
unsigned sign=f>>31;
unsigned exp=f>>23&0xFF;
unsigned frac=f&0x7FFFFF;
if(!(exp^0xFF==0&&frac!=0)) f+=1<<31;
return f;
2.93
unsigned sign=f>>31;
unsigned exp=f>>23&0xFF;
unsigned frac=f&0x7FFFFF;
if(exp^0xFF==0&&frac!=0) return f;
else if(exp>0) exp=exp-1;
else {
//round to even
if(frac&0x1!=0&&(frac>>1)&0x1==1)
frac=frac>>1+1;
else frac=frac>>1;
}
return (sign<<31)|(exp<<23)|frac;
2.94
unsigned sign=f>>31;
unsigned exp=f>>23&0xFF;
unsigned frac=f&0x7FFFFF;
if(exp^0xFF==0&&frac!=0) return f;
else if(exp&0xFE!=0&&exp!=0) exp=exp+1;
else if(exp==0)
{
if(frac>>23&0x1==0) frac<<1;
else
{
exp=1;
frac<<1;
}
}
return (sign<<31)|(exp<<23)|frac;
2.95
i是整数，故而E部分的指数最小也为0+127=127。不包括E为0的情况。我们首先判断最高位的1在哪个位置。
//符号位
int sign=i>>31;
//求i的绝对值
if(!sign) i=~i+1;
//求数值位最高位的1所在位置
int pos=0;
if(i>>16) {pos+=16; i>>=16;}
if(i>>8) {pos+=8; i>>=8;}
if(i>>4) {pos+=4; i>>=4;}
if(i>>2) {pos+=2; i>>=2;}
if(i>>1) {pos+=1; i>>=1;}
exp=pos+127;
//屏蔽掉数值部分为1的最高位（第pos位），这一位在浮点数中是隐式显示表示的。
i=~(1<<pos)&i;
//第pos位要左移或者右移到第23位，使得低23位是frac部分。
if(i>>23)
{
frac=i>>(pos-23);
//最低(pos-23)位要看是否需要round to even，并且pos!=23
if(!(pos^0x17)&&(((1<<(pos-23)-1)&&i)^(1<<(pos-23-1)))==0))
{
//round to even
if(frac&0x1) frac+=1;
//发生溢出时，需要进位
if(frac==0) exp+=1;
}
}
else
{
frac=i<<(23-pos);
}
return (sign<<31)|(exp<<23)|frac;
2.96
这道题还是比较繁琐，解法可类比2.95，但不再具体写代码了。在求解的时候，首先不考虑符号位，先求绝对值的表示，设这个绝对值为ret。
由于采用了round to zero的策略，故而不需要考虑“入”，只需要考虑“舍”即可。
（1）exp<0+127，ret=0
（1）exp=0+127，ret=1；
（2）exp=255，frac!=0时，ret=0x80000000
（3）exp等于其他值时，我们先把frac部分提出来，在第23位变为1，这是因为在float表示中，这个整数部分的1被隐藏了，我们求解int的时候，需要将其加上。此时，小数点在第23位的右侧。
当exp=127时，frac>>=23；
当exp=128时，frac>>=22；
……
当exp=150时，frac>>=0；
当exp=151时，frac<<=1；
当exp=152时，frac<<=2；
……
当exp=157时，frac<<=7；
之后，再左移的话，就会溢出。也即exp>157时，ret=0x80000000。
最后，如果是正数的话，直接拼装一下。而如果是负数的话，先按正数拼接，然后变反即可。不需要考虑Tmin的原因是float没有足够的精度来表示Tmin，故参数给出的f不可能被表示成Tmin。
转载于:https://www.cnblogs.com/XjChenny/archive/2013/03/18/2966414.html