《深入理解计算机系统》练习题2.42-2.44 补码除以2的幂

ゝ一世哀愁。 2022-04-18 06:06 181阅读 0赞

# 补码除以2的幂 #

具体讲解在书里。这里直接给几个结论：  
1）有符号数即补码数执行的是，算术右移。

2）有变量x和 2 k 2^k 2k(0<=k<w)，那么 x > > k x >>k x>>k将产生数值 ⌊ x / 2 k ⌋ \\lfloor \{x/2^k\} \\rfloor ⌊x/2k⌋。

3）正常来说，除法是向零取整，而不是固定的向下取整。所以为了负数除法有正确的结果，在移位前加偏置。所以，当x为负数时，将执行 ( x + ( 1 < < k ) − 1 ) > > k (x + (1<<k)-1) >>k (x\+(1<<k)−1)>>k产生数值 ⌈ x / 2 k ⌉ \\lceil \{x/2^k\} \\rceil ⌈x/2k⌉。  
将 2 k 2^k 2k当做y，所以就是 ⌈ x / y ⌉ \\lceil x/y \\rceil ⌈x/y⌉= ⌊ ( x + y − 1 ) / y ⌋ \\lfloor (x+y-1)/y \\rfloor ⌊(x\+y−1)/y⌋

关于第3条结论，除了书中给出的证明，这里给出一个直观上的解释：  
 ( x + y − 1 ) / y = x y + y − 1 y (x+y-1)/y =\\frac\{x\}\{y\} + \\frac\{y-1\}\{y\} (x\+y−1)/y=yx\+yy−1  
假如 x y \\frac\{x\}\{y\} yx现在是一个负的小数，y为4， x y \\frac\{x\}\{y\} yx且可以分解为-3和 1 4 \\frac\{1\}\{4\} 41，本来-2.75向下取整是-3，就不是向零取整了。但这里再加上一个 3 4 \\frac\{3\}\{4\} 43，结果就会变成-2，再向下取整，也是正确的结果-2了。  
而且上面的分解过程， ？ 4 \\frac\{？\}\{4\} 4？是大于等于 1 4 \\frac\{1\}\{4\} 41，小于等于 4 − 1 4 \\frac\{4-1\}\{4\} 44−1，所以肯定能保证正确结果。

# 2.42原理 #

当x为非负数时，不加偏置。因为此时的向下取整就是向零取整。  
当x为负数时，加偏置。

具体来说，就是得到x的符号位上的值是0还是1，如果是1，那么就要加上偏置 2 4 − 1 2^\{4\}-1 24−1即15。

# 2.42代码 #

int book_div16(int x)
    { 
            /* Compute bias to be either 0 (x >= 0) or 15 (x < 0) */
            int bias = (x >> 31) & 0xF;//右移31位后，32位上面都是符号位的值
            //如果为非负数，符号位为0，bias变量为0
            //如果为负数，符号位为1，bias变量为0xF，即15
            return (x + bias) >> 4;
    }

如上为原书实现。

# 2.43 #

![在这里插入图片描述][20181109142231218.png]  
先看M:  
代码等价于x = x \* 32 -x = x \* 31.所以M为31.  
再看N：  
7 =  2 3 2^3 23\-1，最后的右移操作也是右移3位，所以N为 2 3 2^3 23即8.

# 2.44 #

int x = foo();  
int y = bar();  
unsigned ux = x;  
unsigned uy = y;  
对于以下的各表达式，回答两个问题：(1)对于任意的x和y值，该表达式是否为true,  
(2) 当x和y取什么值时为false

A. (x > 0) || (x-1 < 0)  
当x为TMIN时，左边不符合条件，为0；右边负溢出为TMAX，正数不小于0，为0；此时为false

B. (x & 7) != 7 || (x<<29 < 0)  
左边要求的是x的低3位不能都为1；右边要求第3位为1（先左移29位，所以有原始的低3位和29位个0组成，此时小于0，说明符号位为1，即原始的低3位的最高那个为1）；  
低3位分两种情况：  
1）除111外的所有情况：左边符合，必返回1，不用管右边。  
2）111：左边不符合，但右边符合了，也返回1。  
该表达式必为true。

C. (x \* x) >= 0  
很明显会出现正溢出，但这里和加法的溢出不一样，加法正溢出最多能获得第w+1位的权值 2 w 2^w 2w，且正溢出结果必为负数。  
但这里就不一样了，因为乘积的结果可能很大。正溢出的结果也是可能正，可能负。  
规律如下：  
将乘积设为s，如果s- 2 w 2^w 2w为负数，那么s- 2 w 2^w 2w则为溢出结果。  
如果s- 2 w 2^w 2w为非负数，那么(s- 2 w 2^w 2w)% 2 w 2^w 2w则为溢出结果。

short a, b, c;
    	a = b = 182;
    	c = a * b;

![在这里插入图片描述][20181109164458946.png]  
182\*182-65536=33124-65536=-32412

short a, b, c;
    	a = b = 270;
    	c = a * b;

![在这里插入图片描述][20181109164649405.png]  
(270\*270-65536)%65536=(72900-65536)%65536=7364%65536=7364

short a, b, c;
    	a = b = 400;
    	c = a * b;

![在这里插入图片描述][20181109164907314.png]  
(400\*400-65536)%65536=(160000-65536)%65536=94464%65536=28928  
**非要说原因的话，就是加法正溢出会导致第w位的值为1，而乘积正溢出就不一定了。**

D. x<0 || -x <= 0  
当x为0时，右边成立；  
当x为\[1,TMAX\]，右边必成立；  
当x为\[TMIN+1,-1\]，左边成立；  
当x为TMIN，左右都成立；  
综上，此表达式必为1.

E. x>0 || -x >= 0  
当x为0时，右边成立；  
当x为\[1,TMAX\]，左边成立；  
当x为\[TMIN+1,-1\]，右边成立；  
当x为TMIN，左右都不成立；

F. x+y == uy+ux  
表达式中含有无符号数，所以左边也会转换为无符号数。等价于unsigned(x+y) == uy+ux.  
在二进制上，无符号数和有符号数的加法是一样的，故都为真。  
例如：x=y=-1,则ux=uy= 2 32 − 1 2^\{32\}-1 232−1(TMAX).  
x+y = -2 ,再转无符号明显是 2 32 − 2 2^\{32\}-2 232−2（TMAX-1，除最低一位为0外，其余都为1）  
x+y = ( 2 32 − 1 2^\{32\}-1 232−1)\*2 -  2 32 2^\{32\} 232 =  2 33 2^\{33\} 233 \- 2 -  2 32 2^\{32\} 232 =  2 32 − 2 2^\{32\}-2 232−2.

G. x\*~y + uy*ux == -x  
\-y = ~y+1,故 ~y=-y-1, 左边= x*(-y-1)+uy*ux = uy*ux - x*y -x, 不管是无符号数还是有符号数，在二进制层面上相乘后截短后的结果都是相同的。故 uy*ux-x\*y=0, 故结果都为真，道理同上。

参考链接：  
\[1\] [https://github.com/haiiiiiyun/book\_exercises/blob/master/csapp-v3/chap2/2.43-2.54.txt][https_github.com_haiiiiiyun_book_exercises_blob_master_csapp-v3_chap2_2.43-2.54.txt]

[20181109142231218.png]: /images/20220418/1e0513ebc38343ca98033960e3357244.png
[20181109164458946.png]: /images/20220418/6d5cdb6158e54e06ba8914d4ec97f957.png
[20181109164649405.png]: /images/20220418/255ba8ac4beb4ced8e1274a026107d9d.png
[20181109164907314.png]: /images/20220418/9fadc05335d54450b4cb36ef59268ec9.png
[https_github.com_haiiiiiyun_book_exercises_blob_master_csapp-v3_chap2_2.43-2.54.txt]: https://github.com/haiiiiiyun/book_exercises/blob/master/csapp-v3/chap2/2.43-2.54.txt