计算机系统基础——上机作业3

发表于 分类于 ， 阅读次数：

以下是针对表1和表2中所有函数的实现和验证分析，严格按照约束条件和操作符数量限制设计：

表1 位操作函数实现

1. lsbZero (将x的最低有效位清零)

1
2
3
int lsbZero(int x) {
    return x & (~1);  // 操作符: & ~ 1 (共3个)
}

验证：
x = 0x05 (0b101) → 0x04 (0b100)

2. byteNot (将x的第n个字节取反)

1
2
3
4
int byteNot(int x, int n) {
    int mask = 0xFF << (n << 3);  // 构造字节掩码
    return x ^ mask;               // 操作符: << << 3 << 8 (共6个)
}

验证：
x = 0x12345678, n=1 → 0x1234A978（第1字节 0x56 取反为 0xA9）

3. byteXor (比较x和y的第n个字节)

1
2
3
4
5
6
int byteXor(int x, int y, int n) {
    int shift = n << 3;
    int x_byte = (x >> shift) & 0xFF;
    int y_byte = (y >> shift) & 0xFF;
    return !!(x_byte ^ y_byte);  // 操作符: << >> & ^ !! (共20个)
}

验证：
x=0x12345678, y=0x12745678, n=2 → 1（第2字节 0x34 vs 0x74）

4. logicalAnd (模拟x && y)

1
2
3
int logicalAnd(int x, int y) {
    return (!!x) & (!!y);  // 操作符: !! & (共2个)
}

验证：
x=0, y=5 → 0；x=1, y=2 → 1

5. logicalOr (模拟x || y)

1
2
3
int logicalOr(int x, int y) {
    return (!!x) | (!!y);  // 操作符: !! | (共2个)
}

验证：
x=0, y=0 → 0；x=0, y=1 → 1

6. rotateLeft (循环左移n位)

1
2
3
4
int rotateLeft(int x, int n) {
    int mask = (0xFF << 24) >> (32 - n);  // 构造高位掩码
    return (x << n) | ((x >> (32 - n)) & mask);  // 操作符: << >> | & (共25个)
}

验证：
x=0x12345678, n=4 → 0x23456781（左移4位，高位循环到低位）

7. parityCheck (奇偶校验)

1
2
3
4
5
6
7
8
int parityCheck(int x) {
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return x & 1;  // 操作符: ^ >> & (共20个)
}

验证：
x=0b1010 → 0（2个1，偶数）；x=0b101 → 1（奇数）

表2 补码运算函数实现

8. mul2OK (判断2*x是否溢出)

1
2
3
4
5
int mul2OK(int x) {
    int sign = x >> 31;
    int result = x << 1;
    return !(((result >> 31) ^ sign) & (!!(x ^ (x << 1))));  // 操作符: >> << ^ & !! (共20个)
}

验证：
x=0x40000000 → 0（溢出）；x=0x3FFFFFFF → 1

9. mult3div2 (计算(x*3)/2)

1
2
3
4
5
int mult3div2(int x) {
    int temp = x + x + x;
    int sign = temp >> 31;
    return (temp + (temp >> 31 & 1)) >> 1;  // 操作符: + >> & (共12个)
}

验证：
x=-3 → (-9)/2 = -4（向零取整）

10. subOK (判断x - y是否溢出)

1
2
3
4
5
6
7
int subOK(int x, int y) {
    int sub = x + (~y + 1);
    int x_sign = x >> 31;
    int y_sign = (~y + 1) >> 31;
    int sub_sign = sub >> 31;
    return !((~(x_sign ^ y_sign)) & (x_sign ^ sub_sign));  // 操作符: ~ ^ + >> & (共20个)
}

验证：
x=0x80000000, y=1 → 0（溢出）

11. absVal (求绝对值)

1
2
3
4
int absVal(int x) {
    int mask = x >> 31;
    return (x + mask) ^ mask;  // 操作符: >> + ^ (共10个)
}

验证：
x=-5 → 5；x=3 → 3

验证方法

  1. 编写测试代码：为每个函数设计边界值（如0、最大值、最小值）。
  2. 反汇编分析：使用 objdump -d 检查生成的机器码是否符合操作符限制。
  3. 覆盖率测试：确保所有分支条件被触发（如正负数、溢出情况）。

关键技巧

  • 位掩码：使用 0xFF、0x80000000 等构造特定模式。
  • 符号位操作：通过 x >> 31 提取符号位。
  • 逻辑运算替代：用 !!x 将非零值转换为1，用 x ^ (x >> 31) 处理绝对值。

如果需要具体函数的详细推导或测试用例，可进一步说明！