计算机系统基础_作业2

2.75

针对补码乘法，我们得到如下式子：

其中的mod2^w 相当于截取前w位的操作，那么我们取高w位，则只需将取模运算改为除法。

得到：

于是我们的代码如下：

#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#include<math.h>

unsigned unsigned_high_prod(unsigned x, unsigned y) {
    // 将 unsigned 类型的数转换为 signed 类型
    int signed_x = (int)x;
    int signed_y = (int)y;
    int x31 = signed_x >> 31;
    int y31 = signed_y >> 31;
    // 调用 signed_high_prod 函数
    int signed_result = signed_high_prod(signed_x, signed_y);s
    unsigned unsigned_result = (unsigned)(signed_result + x31 * y + y31 * x);

    // 返回 unsigned 高位部分
    return unsigned_result;
}

2.77

A:对于 x*17 = x * (2^4 + 2^0) = x * 2^4 + x = x << 4 + x << 0 = x << 4 + x

(x<<4)+x

B: 对于 x*-7 = -(x * 2^3 - x * 2^0) = -(x<<3)+x

-(x<<3)+x

C:对于 x * (64 - 4) = x * (2^6 - 2^2) = x << 6 - x << 2

(x<<6)-(x<<2)

D:对于 x * -(128 - 16) = x * -(2^7 - 2^4) = -(x << 7 - x << 4) = -(x<<7)+(x<<4)

-(x<<7)+(x<<4)

2.79

int mul3div4(int x){
    if(x >=0){
        int high_bit = (x>>2)*3;
        int low_bit = (x&0x3)*3;
        return high_bit + (low_bit>>2);
    }
    else{
        int high_bit = (x>>2)*3;
        int low_bit = (x&0x3)*3;
        return high_bit + ((low_bit+3)>>2);
    }
}

我们通过一下代码来测试：

int main(){
    int x;
    for(x = INT_MIN;x < INT_MAX;x++)
    {
        if(mul3div4(x) != ((long long)x) *3/4)
        {
            printf("不相同:%d\n",x);
            printf("%d\n%d\n",mul3div4(x),((long long)x) *3/4);
            return 1;
        }
    }
    if( x == INT_MAX)
        printf("计算结果全部一致！");
    return 0;
}

运行结果为：

2.82

A.

错，当 x = INT_MIN,y = 0 时 x = -x仍然等于-2147483648，y = -y 仍然等于0 则 -2147483648<0 == -2147483648 > 0 显然为0

B

对，x<<4 -x + y<<4 + y = x*(2^4 - 1) + y*(2^4 + 1) = x*15 + y*17

C

对

~x + ~y + 1 = -(x + 1) + -(y + 1) + 1 = -x - 1 - y - 1 + 1 = -x - y - 1 + 1 = -x - y -1

~(x + y) = -(x + y + 1)

~x + ~y + 1 == ~(x + y)

D

对

unsigned x - unsigned y = -(unsigned)(y-x)

无符号数减法时，若x<y，结果会发生下溢，计算为x-y+w

考虑情况：

1、x>=y

ux−uy=x−y

而 −(unsigned(y−x)) 的结果为：

−(unsigned(y−x))=−(2^w + y−x)=2^w + x - y = x-y

2、x<y

unsigned x- unsigned y= x - y + 2^w

−(unsigned(y−x))= -U(y-x) = 2^w - (y -x) = 2^w -x +y

两种情况下都成立，故等式恒成立

E

对

((x>>2)<<2)<=x

右移两位后左移，最低两位一定被丢弃且无法恢复