前置材料

一本CSAPP

CSAPP的bilibili翻译课程

实验材料
参考经验贴1

实验简介

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

讲义说明

开始先将 datalab-handout.tar 复制到一台 Linux 机器上（受保护的）目录中，您打算在该目录完成工作。然后输入命令

unix> tar xvf datalab-handout.tar这会把许多文件解压到目录中。

你唯一需要修改和提交的文件是 bits.c。

bits.c 文件包含了 13 个编程谜题的框架。你的任务是完成每个函数框架，对于整数谜题只能使用直线代码（即，没有循环或条件语句），以及有限数量的 C 语言算术和逻辑运算符，具体来说，你只能使用以下 8 个运算符：! ˜ & ˆ | + << >>，一些函数进一步限制了这个列表。此外，不允许使用任何长度超过 8 位的常量。有关详细规则和代码样式要求的讨论，请参见 bits.c 中的注释。

以下是解压得到的文件的作用（README中有英文的详细解释，非常建议看英文的，这里我也简单介绍一下）

├── bits.c 唯一需要修改的文件
├── bits.h 函数声明
├── btest.c 检查 bits.c 中函数功能的正确性。这些函数被用作参考函数来表示函数的正确行为，尽管它们不满足函数的代码规则。
├── btest.h 测试函数的函数声明
├── decl.c
├── dlc 这是一个来自 MIT CILK 小组的 ANSI C 编译器的修改版本，您可以使用它来检查每个谜题是否符合代码规则。
├── Driverhdrs.pm
├── Driverlib.pm
├── driver.pl 这是一个驱动程序，使用 btest 和 dlc 计算你解答的正确性和性能分数。
├── fshow.c 提供的 fshow 程序帮助你理解浮点数的结构，可以使用 fshow 查看任意模式表示的浮点数。
├── ishow.c 可以使用 ishow 查看任意模式表示的整数：
├── Makefile
├── README 说明文档
└── tests.c

tmin

int tmin(void) {
  return 0x1<<31;
}

求最小值，0x1向左移31位

isTmax

int isTmax(int x) {
  return !(~(x+1)^x)&!!(x+1);
}

判断x是否为补码最大值，最大值取~x+1就是自己，自己和自己异或可以得到0，由于-1也是同样满足条件的需要排除。

bitXor

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

###实现按位异或

allOddBits

int allOddBits(int x) {
  int mask = 0xAA | (0XAA << 8);
  mask = mask | (mask << 16);
  return !((mask & x) ^ mask);
}

题目要求判断奇数位是否全是1，用与运算构造一个0xAAAAAAAA这样的数据然后与元素然后获取输入 x 值的奇数位，其他位清零（mask&x），然后与 mask 进行异或操作，若相同则最终结果为0，然后返回其值的逻辑非。

negate

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

求-x，按位取反+1即可

isAsciiDigit

int isAsciiDigit(int x) {
  int sign = 0x1<<31;
  int upperBound = ~(sign|0x39);
  int lowerBound = ~0x30+1;
  return !((sign&(upperBound+x)>>31)|(sign&(lowerBound+x)>>31));
}

判断传入的x是否在0x30和0x39之间，我们可以使用两个数，一个数是加上比0x39大的数后符号由正变负，另一个数是加上比0x30小的值时是负数。这两个数是代码中初始化的 upperBound 和 lowerBound，然后加法之后获取其符号位判断即可。

conditional

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

实现x?y:z三目运算符，根据 x 的布尔值转换为全0或全1，即 x==0 时位表示是全0的， x!=0 时位表示是全1的。通过获取其布尔值0或1，然后求其补码（0的补码是本身，位表示全0；1的补码是-1，位表示全1）得到想要的结果。然后通过位运算获取最终值。

isLessOrEqual

int isLessOrEqual(int x, int y) {
  int negX = ~x + 1;//-x
  int addX = negX + y;//y-x
  int Tmin = 1<<31;
  int checkSign = addX&Tmin;//sign of y-x
  int xLeft = x&Tmin;//sign of x
  int yLeft = y&Tmin;//sign of y
  int xyXor = !!(xLeft ^ yLeft);
  return (!xyXor&!checkSign)|(xyXor&(xLeft>>31));
}

要么y-x的符号位为正且x、y符号相同，要么y和x符号位不同且x的符号为负，因为直接相减会导致溢出等因素，并不能直接判断。