csapp-datalab

文件任务可以参考https://shimo.im/docs/8pKdVCQVXTXyTY3W/

前置知识：

~ ：非运算符 如 ~0010 = 1101
& ：与运算符 如 0010 & 1110 = 0010
| ：或运算符 如 0010 | 1110 = 1110
^ ：异或运算符 如 1001 ^ 0110 = 1111
! ：逻辑非运算符 如 !0 = 1 !1 = 0
&&:逻辑与运算符 如 1 && 1 = 1 1 && 0 =0
||：逻辑或运算符 如 1 || 0 = 1 
>>: 右移运算符 逻辑右移(不考虑符号位) 如0100 >> 2 = 0001
<<: 左移运算符 如 1001 1001 << = 0110 0100

1.位运算

1.bitXor

将^运算用~和&表示

 int bitXor(int x, int y) {
 return ~(x&y)&~(~x&~y);
  /*
  0101 0011 x    
  1110 0110 y
  0100 0010 x&y
  1011 1101 ~(x&y)
  
  1010 1100 ~x
  0001 1001 ~y
  0000 1000 ~x&~y
  1111 0111 ~(~x&~y)
  
  1011 0101 x^y  ~(x&y)&~(~x&~y)
  */
}

比较简单。

2.tmin

返回最小int值

1
2
3

int tmin(void) {
  return 1<<31;
}

3.isTmax

通过位运算计算是否是补码最大值，int范围-2147483648——2147483647即~0x7fffffff——0x7fffffff

0x7fffffff + 1 = ~ 0x7fffffff,特例是-1.

1
2
3

int isTmax(int x) {
  return !((x+1)^(~x))&!(!(x^-1));
}

4.allOddBits

所有奇数位为1返回1。例子allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1.

思路：获取输入x值的奇数位，其他位清零（0xAAAAAAAA&x），然后与0xAAAAAAAA进行异或操作，若相同则最终结果为0，然后返回其值的逻辑非

int allOddBits(int x) {
  int mask = 0xAA+(0xAA<<8);
  mask=mask+(mask<<16);//0xAAAAAAAA
  return !((mask&x)^mask);
}

5.negate

求-x不用-号。

1
2
3

int negate(int x) {
  return ~x+1;
}

6.isAsciiDigit

判断输入的x是否满足0x30 <= x <= 0x39，满足返回1.

先判断0x30（!(x>>4^3)），再判断0x0——0x9（!(x>>3&1)|!(x>>1&1|x>>2&1)）

1
2
3

int isAsciiDigit(int x) {
  return !(x>>4^3)&(!(x>>3&1)|!(x>>1&1|x>>2&1));
}

7.conditional

使用位级运算实现C语言中的 x?y:z三目运算符

int conditional(int x, int y, int z) {
  x = !!x;
  x = ~x+1;   //求补码（0的补码是本身，位表示全0；1的补码是-1，位表示全1）
  return (x&y)|(~x&z);
}

8.isLessOrEqual

使用位级运算符实现<=

int isLessOrEqual(int x, int y) {
  int addX=~x+1+y;//y-x
  int checkSign = addX>>31&1; //y-x的符号
  int xLeft = x>>31&1;//x的符号
  int yLeft = y>>31&1;//y的符号
  int bitXor = xLeft ^ yLeft;//x和y符号相同标志位，相同为0不同为1
  bitXor = (bitXor>>31)&1;//符号相同标志位格式化为0或1
  return ((!bitXor)&(!checkSign))|(bitXor&(xLeft>>31));//返回1有两种情况：符号相同标志位为0（相同）位与 y-x 的符号为0（y-x>=0）结果为1；符号相同标志位为1（不同）位与x的符号位为1（x<0）
}

9.logicalNeg

使用位级运算求逻辑非！

逻辑非就是非0为1，非非0为0。利用其补码（取反加一）的性质，除了0和最小数（符号位为1，其余为0），外其他数都是互为相反数关系（符号位取位或为1）。0和最小数的补码是本身，不过0的符号位与其补码符号位位或为0，最小数的为1

1
2
3

int logicalNeg(int x) {
  return ((x|(~x+1))>>31)+1;
}