CSAPP Data Lab

    csapp   csapp  Comments

CSAPP Data Lab Solution

less or euqal than

isLessOrEqual - if x <= y then return 1, else return 0

Example: isLessOrEqual(4,5) = 1.

Legal ops: ! ~ & ^ | + << >>

Max ops: 24

Rating: 3

  • 判断一个数是否less or equal than 另一个数可以使用 -x + y 判断结果的符号位是否为0即可(可以涵盖x == y的情况)
  • 但是涉及到加减运算就要考虑sign bit overflow的情况。
  • $-2^{w-1} \leq x, y \leq 2^{w-1}-1$ 如果同符号的两个数做减法一定不会出现越界的情况。而不同符号做减法则大概率出现越界的情况。(位运算得到了与我们期待值不符的值一定是我们期待的结果越界了)
  • 上述分析我们可以把问题拆分为两部分判断
    • 如果是同符号则判断~x+1+y的符号位是否为0
    • 如果是不同符号的情况，我们则要屏蔽掉~x+1+y得到的结果，单纯以符号位判断结果
int isLessOrEqual(int x, int y) {
  /* 1.如果符号位相同判断 ～x+1+y符号位是否为0； 2.如果符号位不同则以符号位判断大小 */
  int res = ~x + 1 + y; // y - x 期待结果为正数或者0 两种情况符号位为都0
  int signX = x >> 31;
  int signY = y >> 31;
  //符号相同不会出现溢出的情况，结果一定在[-2^(w-1), 2^(w-1)-1]内。此时只需要判断y - x符号位是否为0即可
  res = (!(res >> 31)) & (~(signX^signY));// 如果符号位不同 &(~(signX^signY))会把res结果屏蔽掉
  //符号位不同的情况下只需要看x的符号位是否为0即可
  int signRes = (signX ^ signY)&(!~signX);
  return  res| signRes;
}

logicalNeg

logicalNeg - implement the ! operator, using all of

the legal operators except !

Examples: logicalNeg(3) = 0, logicalNeg(0) = 1

Legal ops: ~ & ^ | + « »

Max ops: 12

Rating: 4

  • 实现逻辑！
    • int x只要bit位上存在1取!值即为0，所以只保留住1个1就可以代表整个数值
    • x&(~x+1)可以保留最右一位1(Tmin也适用)；对于0来说 x&(~x+1) 仍然是0
    • 保留最右位1后对整个数再取反加1，非0的数一定不会出现最高位进位的现象，而~0的最高位一定会进位
    • 将数值»31判断最高位的值即可
int logicalNeg(int x) {
  /*只保留右侧第一个1； 取反+1； 取最高位的符号*/
  x = x & (~x + 1); 
  x = ~x + 1;
  x = ~x >> 31 & 0x01;
  return x;
}

Mark ZhangSoftware Engineer

Hi there ~