CSAPP

CASPP Lab 第一章题解(1)

Data Lab

bitXor

1
2
3
4
5
6
7
8
9
10
11
//1
/* 
 * 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 (x&~y)|(~x&y);
}

蛮简单的，直接异或

有无更简便的写法呢？

tmin

关于tmin

我的想法就是

  • 对0x00逻辑取反，得到111…111
  • 然后右移一位，得到011…111
  • 再加1，即可得到100…000这种形式

有个要注意的，就是逻辑取反必须是对无符号数，因此我们首先要写上unsigned

这个地方还不确定，究竟什么时候需要加unsigned

1
2
3
4
5
6
7
8
9
10
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return ( ( ~(unsigned)0x00 ) >> 1 ) + 1;

}

isTmax

1
2
3
4
5
6
7
8
//2
/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */

不能用if之类的控制语句，==这类也不能用，因此需要好好思考思考
我们可以先得出最大的数，其实最大数也知道，就是01111…111这样的，我们用一个mask应该可以
如果和mask进行异或，得到0，说明是相同的，那就取反好了，反之就不是0；如何对于0输出1，对于其他数输出0？

1
2
3
4
5

int isTmax(int x){
	unsigned mask = ~(unsigned)0x00 >> 1;//得到0111..11
  	return 1 - (bool)( x ^ mask);//异或的话，如果位相同则返回0， 位不同则返回1 
}

但是，bool类型不能用，这是c…

好吧，忘记了一个重要的事情，那就是——没有bool我可以用!啊…

那么!怎么实现呢？（这就是第9题的事情了）

下面是正确代码

1
2
3
4
int isTmax(int x){
	unsigned mask = ~(unsigned)0x00 >> 1;//得到0111..11
  	return ! ( x ^ mask);//异或的话，如果位相同则返回0， 位不同则返回1 
}

看了一个讲解，还有一个思路：

目前我们能用的一个确定的数就是0，因此如果需要执行比较判断，我们可以试着从当前数通过一系列操作映射到目标数0
现在就有一个问题，执行操作的时候，可能会同时将其他一些数也映射到0，这个过程大概率不是一一对应的，当然也有可能hhh，可以想一想
总之，对于那些多出来的数，我们需要设计一些方法将它们排除掉

allOddBits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* 
 * 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
 */
//直接告诉你了，一共32位，确实得告诉，不过假如不知道上限的话，怎么去做呢？或者怎么用这些写出循环判断呢？
//所有奇数位为1，mask一下？先做一个奇数位的mask,然后进行&的操作，我们就取出了奇数位，1，3，

int allOddBits(int x) {
  return !(0xAAAAAAAA ^ (x & 0xAAAAAAAA));
}
//通过了，可以可以
//如果不知道上限位数呢？那么这个mask就需要我们自己去获取
//其实很容易，我们可以构建从mask到0的映射，然后去掉杂项即可
//映射为：x + x >> 1 = -1 = 1111...1111
//这个好理解，因为101010...1010这种，加上自己右移一位的结果，恰好就是全1
//那么倒推呢，还有谁可以通过这个映射计算出全1？
//稍微推导一下就知道，没有别的了，因为最低位相加为1，每一位对应相加为1，因此必然是0101的，而首位直接等于1（过程无进位），就推出x必然为1010...1010的形式
int allOddBits(int x){
  return !(-1 ^ (x + x >> 1));
}
//其实自己想错了，构建映射然后去掉杂项，只能应用于判断条件，而非求值
//可是这个映射下只有1010...1010可以映射到0，能否映射回去呢？看看这个过程是不是双射，感觉就是吧，一个x对应一个结果，而结果为0的情况下只有x可以满足，就是双射
//尝试构建逆运算
//没搞出来，也许可以直接从Tmax下手，直接搞算数运算，之后想到了再试试吧

//其实有个问题，即实验要求只能使用两位16进制，即0x00这种，因此0xAAAAAAAA需要通过0xAA来构造，倒是不麻烦

negate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
//要求负数，我加个负号？
//好好好，还真能过，有点懵逼，真的
int negate(int x) {
  return -x;
}
//其实不对，没有满足要求
int negate(int x) {
  return ~x + 1;
}

isAsciiDigit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//3
/* 
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
//0x30 = 0011 0000
//0x39 = 0011 1001
//判断最高位是否为第6位且第5第6位是否为1，构建一个mask，0011 0000，然后结果右移4位，要是非0就说明不是，用一个flag记录一下
//然后若4为1则mask一下23，若4不为1则直接输出1
//看看咋写
int isAsciiDigit(int x) {
  int flag_1 = !( (0x30 ^ x) >> 4 );
  int a = (0x08 & x) >> 3, b = (0x04 & x) >> 2, c = (0x02 & x) >> 1;//取出后4位的前3位
  int flag_2 = !( (a & b) | (a & c) );
  return flag_1 & flag_2;
}
//通过了，还蛮容易，不过运算符刚好用了15个，试试能不能再简化简化

//看到了一个思路，说是根据上下界来判断，可以之后思考一下

conditional

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
//判定逻辑就是，x是否非0，如果非0，输出y；如果是0，输出z。
//想到了一个，我们只需要最后输出统一格式：mut + y
//然后中途修改mut即可
//mut满足：当x=0时，mut=z-y；当x!=0时，mut=0
//下面就是这个逻辑的实现，还蛮有意思的，通过0和非0的映射
//其实思路就是，我们直接用0作为选择器来生成mut变量，反正mut变量要么是z-y要么是0
//怎么选择呢？用或呗：00000和11111，就可以实现选择了
//比如，当x=0时，我们将门设为111...111，当x!=0时，我们将门设为000...000；
//然后将门与z-y或一下就行
//怎么从0和非0生成111...111和000...000，这个更简单了，000...000和111...111之间其实就差1，0和1也差1，你懂我意思吧
//看代码：
int conditional(int x, int y, int z) {
  int mut = ( ( ( ! ! (unsigned)x ) + ~1 + 1 ) ) & (z + ~y + 1);
	return mut + y;
}
//通过了~

isLessOrEqual

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
//相减，按照符号位进行判断输出，可以用上一题的结论
int isLessOrEqual(int x, int y) {
	return ( ( ( ! ! ((y + ~x + 1) >> 31) ) + ~0) ) & 1;//稍微化简一下
}
//事实上通过不了，我们没考虑溢出
//那咋办，考虑一下呗
//思考一下，溢出有两种情况：x正y负，x负y正，前者溢出结果为正，后者溢出结果为负
//那么我们直接对于所有x负y正输出1，x正y负输出0？其余的正常判断
//那么需要两次判断，可以通过&和|实现01的优先条件判断
//比如，flag_np标记x负y正，flag_pn反之
//那么，当flag_np=1时，我们直接输出1；flag_pn=1时，直接输出0
//flag_np=0和flag_pn=0时我们就不管了
//假设原输出为output
//修正后的输出为：(2 + ~flag_pn) & (flag_np | output)
//逻辑是这样的：
//如果flag_pn=1，那么前面就爆0，直接输出0；如果flag_pn=0，进入后面的判断条件
//如果flag_np=1，那么直接输出1，否则输出output
int isLessOrEqual(int x, int y) {
  int xh = ((unsigned)x) >> 31;
	int yh = ((unsigned)y) >> 31;
	int flag_pn = !xh & yh;
	int flag_np = !yh & xh;
	return  (2 + ~flag_pn) & (flag_np |  ( ( ( ( ! ! ((y + ~x + 1) >> 31) ) + ~0) ) & 1 ) );
}
//然后终于通过了...好耶！