实验 1：Data Lab

实验环境

Ubuntu 20.04

实验附件

Computer Systems: A Programmer's Perspective——Lab Assignments：http://csapp.cs.cmu.edu/3e/labs.html

Github下载地址：https://github.com/Xuyan-cmd/CUC_CSAPP

Gitee下载地址：https://gitee.com/rockjames/CUC_CSAPP

课件参考地址：https://bai-chuan.gitbook.io/shen-ru-li-jie-ji-suan-ji-xi-tong-shi-yan-gui-dang/

实验简介

名称	描述	难度	指令数目
bitXor(x,y)	只使用 `~` 和 `&` 实现 `^`	1	14
tmin()	返回最小补码	1	4
isTmax(x)	判断是否是补码最大值	1	10
allOddBits(x)	判断补码所有奇数位是否都是 1	2	12
negate(x)	不使用负号 `-` 实现 `-x`	2	5
isAsciiDigit(x)	判断 `x` 是否是 `ASCII` 码	3	15
conditional(x, y, z)	类似于 C 语言中的 `x?y:z`	3	16
isLessOrEqual(x,y)	`x<=y`	3	24
logicalNeg(x)	计算 `!x` 而不用 `!` 运算符	4	12
howManyBits(x)	计算表达 `x` 所需的最少位数	4	90
floatScale2(uf)	计算 `2.0*uf`	4	30
floatFloat2Int(uf)	计算 `(int) f`	4	30
floatPower2(x)	计算 2.0x	4	30

我们只需要更改bits.c文件，里面有13道题（13个函数）

通过修改代码实现简单的逻辑函数、二进制补码和浮点函数，但必须使用 C 语言的一个高度受限的子集。例如，可能会要求仅用位级运算和直线代码（straightline code）来计算一个数的绝对值。学会理解C 语言数据类型的位级表示和数据操作的位级行为。

参考链接

CSAPP 之 DataLab详解

CSAPP DataLab 题解

【读厚 CSAPP】I Data Lab | 小土刀 2.0

实验注意事项

明确禁止：

使用任何控制结构，例如 if、do、while、for、switch 等。

定义或使用任何宏。

在此文件中定义任何附加函数。

整数常量只能在0 到 255 (0xFF)之间，不允许使用大常量，例如 0xffffffff。

调用任何函数。

使用任何其他操作，例如 &&、||、或 ?：

使用任何形式的铸造。

使用除 int 以外的任何数据类型。这意味着你

不能使用数组、结构或联合。

实验内容

BitXor(x,y)

只使用两种位运算实现异或操作。这个算是一个比较简单的问题了，难度系数1。


//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 2;
}

解析：

根据布尔代数，可以通过 ~ 和 & ，即非和与操作实现异或操作。所谓异或就是当参与运算的两个二进制数不同时结果才为 1，其他情况为 0。C 语言中的位操作对基本类型变量进行运算就是对类型中的每一位进行位操作。所以结果可以使用 “非” 和 “与” 计算不是同时为 0 情况和不是同时为 1 的情况进行位与 。

这道题是手动实现异或操作，只能要求使用按位取反和按位取与操作来实现，在此给出真值表：

x	y	x^y
0	0	0
0	1	1
1	0	1
1	1	0

然后根据真值表写出异或逻辑的表达式：

已知对两个位进行异或操作，同0得0，同1得0，不同得1，所以，我们先求出x和y同为0的位：


(~x & ~y)

x与y同为1的位：


(x & y)

使用德摩根定律进行逻辑推导，反复使用德摩根定律进行变换

相同得0，所以要对上面的位进行取反，整个函数就一句话：


int bitXor(int x, int y) {
    return ~(~x & ~y) & ~(x & y);
}

tmin()


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

  return 2;

}

解析：

C 语言中 int 类型是 32 位，即 4 字节数。补码最小值就是符号位为 1，其余全为 0。

二进制无符号数的值其实可以看作每一位的数（1或0）乘上2的x次方（从第0位开始）的总和，这个x就是第0位到第31位。

而补码的话就是从第0位加到第30位，最后一位则是负的1或者0乘以2的31次方，所以只要第31位是1，0-30位为0，即可得到补码最小值。


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

isTmax(x)


//2
/*
 * 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;
}

解析：

这道题是判断这个数是否为最大的数（2^31 - 1），我习惯使用异或来判断是否相等。

首先求这个最大的数0x7FFFFFFF，可以通过


~(1 << 31)

来得到这个数，与其本身异或，求逻辑非的值，即为结果：


int isTmax(int x) {
    return !(x ^ (~(1 << 31)));
}

allOddBits(x)


/*
 * 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;
}

解析：

这道题是求一个数所有的奇数位是否为1，满足则返回1，否则为0。

Easy，先求出所有奇数位都为1，偶数位为0的数，8位则是0xAA，通过左移可以得到0xAAAAAAAA：


int val1 = 0xAA;
val1 = val1 + (val1 << 8) + (val1 << 16) + (val1 << 24);

将x与0xAAAAAAAA进行位与运算，过滤掉所有偶数位的数据，得到所有奇数位的数据。

再将val1与进行位与运算后得到的值进行异或，一样的话会得到0，取逻辑非则为1，不一样的话会得到一个数，取逻辑非为0。


int allOddBits(int x) {
	int val1 = 0xAA;
	val1 = val1 + (val1 << 8) + (val1 << 16) + (val1 << 24);
  	return !(val1 ^ (x & val1));
}

negate(x)


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

解析：

补码实际上是一个阿贝尔群，对于 x，-x 是其补码，所以 -x 可以通过对 x 取反加 1 得到。

这道题只是求负数，所有位取反加1即可。


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

isAsciDigit(x)


/*
 * 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 2;
}

解析：

判断一个数是否是ASCII码里面的数字

首先取0x30的负数val1，此时如果把这个数与val1相加，则如果这个数大于等于0x30，则结果大于等于0，而小于0x30的话则结果小于0。已知负数符号位为1，0和正数符号位为0，因此可得到这个数是否大于等于0x30。


int val1 = ~0x30 + 1;

类似的方法，取val2为0x80000000减去0x3a，此时val2符号位为1。将这个数与val2相加，如果这个数大于0x39，则结果会大于或等于0x80000000，即符号位为1，而如果小于0x39，结果会小于0x80000000，符号位为0，取反即可得到想要的结果。


int val2 = (1 << 31) + ~0x3a + 1;

将两个结果都进行逻辑非运算，然后位与运算，即为返回值


int isAsciiDigit(int x) {
  int val1 = ~0x30 + 1;
  int val2 = (1 << 31) + ~0x3a + 1;
  return (!((val1 + x) >> 31)) & (!((val2 + x) >> 31));
}

conditional(x, y, z)


/*
 * 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 2;
}

解析：

这道题是实现：？运算符，首先，先把x取布尔值，然后取反加一，如果x布尔值为0，则所有位为0，如果布尔值为1，则所有位为1：


int val = ~(!!x) + 1;

然后使用位或运算，左边放val & y，右边放~val & z，这样如果val为全1，则返回y的值，如果为全0，则返回z的值：


int conditional(int x, int y, int z) {
  int val = ~(!!x) + 1;
  return (val & y) | (~val & z);
}

isLessOrEqual(x, y)


/*
 * 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 2;
}

解析：

这道题是实现<=运算符，要分情况讨论

1、符号位一样，判断x - y的符号位即可。

2、符号位不一样，x符号位为0则返回1，符号位为1则返回0。

取两个数符号位相加，0 + 0 = 0； 1 + 1 = 2；第一位都是0，如果两个数符号位相加后第一位为0，则符合相同：


int val1 = (x >> 31) + (y >> 31);

求x - y的符号位，这里加逻辑非是为了结果统一：


int val2 = !((y + (~x) + 1) >> 31);

用上一题位与运算类似的办法来进行结果的选择：


int isLessOrEqual(int x, int y) {
	int val1 = (x >> 31) + (y >> 31);
  int val2 = !((y + (~x) + 1) >> 31);
  int val3 = x >> 31 & 1;
  return (val1 & val3) | ((~val1) & val2);
}

logicalNeg(x)


/*
 * logicalNeg - implement the ! operator, using all of
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
 */
int logicalNeg(int x) {
  return 2;
}

解析：

这道题是实现逻辑非，一个数，取反加一，再与原来的数字进行位或运算，如果是0，那结果还是0，如果不是0，则符号位必为1。将结果右移31位，如果符号位为0，则结果为0，如果符号位为1，则结果为全1。

把上一个结果再加1，0 + 1为1，0xFFFFFFFF + 1 = 0，即为返回值。


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

howManyBits(x)


/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  return 0;
}

解析：

首先是0和-1两个特殊情况，都是一位，-1的二进制补码是全1，也就是说，取反之后跟0是一样的，只需要一个符号位就可以表示。而一般的数，取反之后跟取反之前都可以用一样的位数来表示，这道题的方法来自

因此，对传入的数x，如果是正数，就不用动，如果是负数，就取反。可以通过把x右移31位后的值与x进行异或运算，这样如果符号位为0，0和任何数异或不变，如果符号位为1，补码右移的规则是在右移之后的空位补上符号位，即如果符号位为1，则右移31位后的值为0xFFFFFFFF。x与0xFFFFFFFF异或的效果即为取反。


int op = x ^ (x >> 31);

这里设3个变量，

如果x == 0，val1 = 1;

如果x == -1，val2 = 1;

如果x != 0 && x != -1，val3 = 0xFFFFFFFF;

然后就是0和-1之外的情况的操作，这里的方法很巧妙：

取op右移16位后的布尔值，这样可以判断高16位是否为0；

将刚刚得到的布尔值左移4位，存放在bit_16，如果布尔值为0，bit_16 = 0，如果布尔值为1，则bit_16 = 1；

将op右移bit_16位，如果op多于16位，则之后只剩下高16位，否则不变。

这时候这个数就只剩下16位要处理了，用同样的方法：

取op右移8位后的布尔值，这样可以判断高8位是否为0；将刚刚得到的布尔值左移3位，存放在bit_8，如果布尔值为0，bit_8 = 0，如果布尔值为1，则bit_8 = 1；将op右移bit_8位，如果op多于8位，则之后只剩下高8位，否则不变。

把下面的bit_16 , 16, 4 分别换成[bit_8, 8, 3]、[bit_4, 4, 2]、[bit_2, 2, 1]、[bit_1, 1, 0]，都运算一遍.


bit_16 = (!!(op >> 16)) << 4;
	op = op >> bit_16;

再把bit_xx的值相加，因为不为0，所以还有一位是不用判断必为1的，再有一个符号位为1，所以：


sum = 2 + bit_16 + bit_8 + bit_4 + bit_2 + bit_1;

返回值为：


return (val1) | (val2) | (val3 & sum);

完整代码：


int howManyBits(int x) {
  int val1 = !(x ^ 0);
  int val2 = !(x ^ (~0));
  int val3 = ~(~(val1 | val2) + 1);
  int bit_16, bit_8, bit_4, bit_2, bit_1;
	int sum;
	int op = x ^ (x >> 31);
	bit_16 = (!!(op >> 16)) << 4;
	op = op >> bit_16;
	bit_8 = (!!(op >> 8)) << 3;
	op = op >> bit_8;
	bit_4 = (!!(op >> 4)) << 2;
	op = op >> bit_4;
	bit_2 = (!!(op >> 2)) << 1;
	op = op >> bit_2;
	bit_1 = (!!(op >> 1));
	op = op >> bit_1;
	sum = 2 + bit_16 + bit_8 + bit_4 + bit_2 + bit_1;
  return val1 | val2 | (val3 & sum);
}

floatScale2(uf)


//float
/*
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf) {
  return 2;
}

解析：

这道题是求浮点数乘二后的结果，一般的浮点数乘二只要阶码加一即可，不过我们要考虑几种特殊情况：

0乘2

无穷大或者NaN乘2

非规格数乘2

题目对于浮点数的函数格式要求放宽了不少，可以使用选择，循环，并且常量值可以使用Int范围内的所有数。

首先对浮点数的各部分进行提取：


int exp = uf & 0x7f800000;
int frac = uf & 0x7fffff;

判断是否为无穷大或者NaN：


if (exp == 0x7f800000)
    return uf;

判断是否为0或非规格数，非规格数乘2为左移1位：


else if (exp == 0)
    frac = frac << 1;

然后就是一般的情况：


else
    exp = exp + 0x800000;

最后就是把结果合并：


ret = (uf & 0x80000000) | exp | frac;

值得一提的是，非规格数如果尾数最高位为1时，右移1位会使阶码最低位从0变为1，而这时候恰好就是正确的结果，并不需要额外的处理。这是因为乘2之后完成了进位，刚好规格数在小数点前有一个1，规格数和非规格数从而无缝衔接。

完整的函数：


unsigned floatScale2(unsigned uf) {
  int ret;
  int exp = uf & 0x7f800000;
  int frac = uf & 0x7fffff;
  if (exp == 0x7f800000)
    return uf;
  else if (exp == 0)
    frac = frac << 1;
  else
    exp = exp + 0x800000;
  ret = (uf & 0x80000000) | exp | frac;
  return ret;
}

floatFloat2Int(f)


/*
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
  return 2;
}

解析：

这道题是实现浮点型转整型，需要分情况讨论：

浮点数超过整形能表达的最大值

浮点数小于1

同上一题一样，先提取浮点数各部分出来：


int exp = 0xff & (uf >> 23);
int frac = 0x7fffff & uf;
int sign = !!(uf >> 31);

按照题目要求，超过最大值返回0x80000000u：


if (exp > 127 + 30)
    return 0x80000000u;

小于1，返回0：


if (exp < 127)
    return 0;

正常情况，特别的，如果浮点数符号位为1，在得到浮点数的绝对值之后取反加一：


tmp = ((frac >> 23) + 1) << (exp - 127);
if (sign)
  return (~tmp) + 1;
else
  return tmp;

完整函数：


int floatFloat2Int(unsigned uf) {
  int exp = 0xff & (uf >> 23);
  int frac = 0x7fffff & uf;
  int sign = !!(uf >> 31);
  int tmp;

  if (exp > 127 + 30)
    return 0x80000000u;
  if (exp < 127)
    return 0;
  tmp = ((frac >> 23) + 1) << (exp - 127);
  if (sign)
    return (~tmp) + 1;
  else
    return tmp;
}

floatPower2


/*
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *   (2.0 raised to the power x) for any 32-bit integer x.
 *
 *   The unsigned value that is returned should have the identical bit
 *   representation as the single-precision floating-point number 2.0^x.
 *   If the result is too small to be represented as a denorm, return
 *   0. If too large, return +INF.
 *
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatPower2(int x) {
    return 2;
}

解析：

三种情况：

x小于-127，结果为0

x大于128，结果为无穷大（阶码全为1，指数为0）

结果为阶码 = x + 127（阶码的偏移量）


unsigned floatPower2(int x) {
  if (x < -127) return 0;
  if (x > 128) return 0xff << 23;
  return (x + 127) << 23;
}