前言：本文为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