CSAPP DataLab学习笔记

1. bitXor

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {

  return 2;
}

思路

将异或的真值表写出来，再用 & | ~ 表示，最后化简

代码

int bitXor(int x, int y) {
  /*
  int exp1 = ~(x & ~y);
  int exp2 = ~(~x & y);
  int res = ~(exp1 & exp2);
  */

  return ~((~x)&(~y))&(~(x&y));
}

2.tmin

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 2;
}

思路

返回二进制补码的最小值，即0x80000000，使用左移操作即可

代码

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

3.isTmax

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) {
  return 2;
}

思路

如果x是二进制补码的最大值0x7fffffff，返回1,否则返回0.
我的思路是将x进行运算，如果是0x7fffffff，运算结果会是一个特殊值，比如全0，而其他数进行运算则不是全0,最后取非。
想到了0x7fffffff + 0x7fffffff + 1 = 0xffffffff，按位取反后为0x0.
但一直有bug调试不出来，调试结果如下：

printf("%x %x %d %d\n", x, x + x + 1, (!(~(x + x + 1))), ~(x + x + 1));

输出：
7fffffff ffffffff 0 0
取了非和没取非的值居然相同
最后参考了这篇博客

代码

int isTmax(int x) {
  //printf("%x\n", !(~(0x7fffffff + 0x7fffffff + 1)));
  //printf("%x %x %x\n", x, 0x7fffffff, !!~(x+x+1));
  //printf("%x %x %d %d\n", x, x + x + 1, (!(~(x + x + 1))), ~(x + x + 1));
  int i = x + 1;
  int j = x ^ i;
  int k = ~j;
  return !(k + !i);
}

4. allOddBits

/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {                                                      
  return 2;
} 

思路

如果x的所有奇数位都为1则返回1,否则返回0
先构造一个A8 = 0xAAAAAAAA作为掩模，再和x进行与运算，将无关的偶数位置0
将结果和A8异或，若奇数位全为1，结果将为全0，取个非即答案

代码

/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
  int AA = 0xAA;                                                               
  int A4 = (AA << 8) + AA;                                                       
  int A8 = (A4 << 16) + A4;                                                         
  return !((x & A8) ^ A8);                                                          
} 

5. negate

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return 2;
}

思路

返回相反数，即返回-x的补码，取反加一即可

代码

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return ~x + 1;
}