CSAPPLAB1——Datalab(上)

前言:本文为CSAPP3.0配套Lab的刷题笔记,这是第一个lab——Datalab的笔记

每个实验题目将采用以下格式来记录

  • 题目描述
  • 题解和思路
  • 解题代码

bitXor

题目描述

只使用按位与非逻辑实现按位异或逻辑

题解与思路

排除掉两个不能通过的逻辑,写成的代码就能通过。

即:把x与y相同的答案都否定掉

代码

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

题目描述

返回补码表示数字的最小值。

题解与思路

补码的最小值是符号位为1,其余均为0,所以返回这个数字就行了。

我的思路也很简单粗暴,直接通过移位得到

代码

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

return 0xff<<31;

}

isTmax

题目描述

判断一个数是不是补码表示的最大数字,是则返回1,否返回0

题解与思路

补码最大数字应该是符号位为0,其余位均为1,所以将它向左移1位再加1之后得到的应该是全为1的数,此时再按位取反后就得到0,再用逻辑非判断即可。

需要注意的是,补码表示的-1进行上述操作后得到的也是一样的结果,所以要把-1排除了,方法是按位取反得到0,然后用逻辑非把这个结果否定了。

代码

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

allOddBits

题目描述

判断所有奇数位是否都为1,如果都为1返回1,否则返回0

PS:这里的位置编号是从0到31

题解与思路

由于只能使用0x00到0xFF间的16进制数,故需要每8位判断1次,所以要考虑移位8、16、24位之后的数字,然后按位取反后与0xAA进行&操作,如果x的奇数位上均为1,取反后应该均为0,与0xAA进行&操作后应均为0,所以再对这个式子求一个逻辑非即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
/* 
* 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 !(~(x & (x >> 8) & (x >> 16) & (x >> 24)) & 0xAA);
}
/*

negate

题目描述

不用-操作符返回数字的负值

题解与思路

补码的正常表示,按位取反加一

代码

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

isAsciiDigit

题目描述

判断一个数是否是数字'0'到'9'的ASCII码,也即判断一个数字是否位于0x30与0x39之间

题解与思路

若要位于0x30与0x39之间,则这个数减去0x30>=0;减去0x3a<0

代码

1
2
3
4
5
6
7
8
9
10
11
12
/* 
* 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
*/
int isAsciiDigit(int x) {
return !((x+~0x30+1)>>31)&!~((x+~0X3a+1)>>31);
}

conditional

题目描述

返回操作结果与语句x ? y : z相同,也即x为1返回y,x为0返回z

题解与思路

先把x利用逻辑非!转换为0或1,保证我们需要转换的只有0或1,然后接下来就是把0或1转换之后造出一个`0x00000000或者0xffffffff再与y和z进行相应的与操作保留y/z即可。

代码

1
2
3
4
5
6
7
8
9
10
/* 
* conditional - same as x ? y : z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) {
return (~!!x+1&y)|(~!x+1&z);
}

今日体重

image-20210810004740111