CSAPP - Data Lab
Computer Systems A Programmer's Perspective 书籍课程配套实验
用有限的C语言运算符实现整数和浮点数的部分运算。实验环境要求是Linux（实验文件目录中的可执行文件dlc需要在linux环境下执行）。Makefile中的CFLAG指定了-m32的选项，所以在普通的64位linux操作系统中直接 $make btest 会产生如下错误输出：
gcc -O -Wall -m32 -lm -o btest bits.c btest.c decl.c tests.c
In file included from btest.c:16:0:
/usr/include/stdio.h:27:10: fatal error: bits/libc-header-start.h: No such file or directory
#include <bits/libc-header-start.h>
^~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.
在stackoverflow中找到了解释，在64位机上编译32位程序需要32位的库支持，安装相关依赖
$ sudo apt-get update
$ sudo apt-get install gcc-multilib
之后可以正常使用btest来检验写好的函数bitXor：
~/CSAPPLab/datalab-handout$ ./btest -f bitXor -1 4 -2 5
Score Rating Errors Function
1 1 0 bitXor
Total points: 1/1
最后运行btest测试floatPower2函数发现总是超时，但是单独测试又没有问题，所以更改了btest.c的源代码，把对于函数floatPower2的测试用例数改为了3000000（原来默认是6000004...)，更改之后才能在10秒之内完成测试。
btest.c line371
if (strcmp(t->name, "floatPower2") == 0) {
test_counts[0] = 300000;
}
最终通过了btest的测试
Score Rating Errors Function
1 1 0 bitXor
1 1 0 tmin
1 1 0 isTmax
2 2 0 allOddBits
2 2 0 negate
3 3 0 isAsciiDigit
3 3 0 conditional
3 3 0 isLessOrEqual
4 4 0 logicalNeg
4 4 0 howManyBits
4 4 0 floatScale2
4 4 0 floatFloat2Int
4 4 0 floatPower2
Total points: 36/36
实验代码如下，howmanybits的写法参照了这篇博客，感觉最难就是howmanybits了。
//bits.c
/*
* 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 - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 1 << 31;
}
//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 !(~(1 << 31) ^ x); // 0xffffffff 特例无法判断
int i = ~x; // if x == 0xffffffff, i = 0
return !!i & !(~(x+1) ^ x); // !!i 使得i在不等于0时取1
}
/*
* 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) {
int odd = (0xaa << 24) + (0xaa << 16) + (0xaa << 8) + 0xaa;
return !((odd & x) ^ odd);
}
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 1;
}
//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
*/
int isAsciiDigit(int x) {
int negLowbound = ~0x30 + 1;
int upbound = 0x39;
int sign = 1 << 31;
// int left = negLowbound + x; // left = x - low
// return !(left & sign) & !(left | !((upbound + x) & sign)); // 0x2f -- failed
// x - low >= 0 && high - x >= 0
return !((x + negLowbound) & sign) & !((~x + 1 + upbound) & sign);
}
/*
* 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) {
int zero = !x;
int mask = ((0xff << 24) + (0xff << 16) + (0xff << 8) + 0xff) + zero;
return (mask & y) + ((~mask) & z);
}
/*
* 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) {
// y - x >= 0
// isLessOrEqual(-2147483648[0x80000000],2147483647[0x7fffffff]) failed...
// return !((y + ~x + 1) & (1 << 31));
// Test isLessOrEqual(2147483647[0x7fffffff],-2147483648[0x80000000]) failed...
// return !(x ^ (1 << 31)) | !((y + ~x + 1) & (1 << 31));
int sign = 1 << 31;
int signx = !(x & sign); // positive or zero is 1, negetive is 0
int signy = !(y & sign);
int diff = y + ~x + 1; // diff = y - x
int sameSign = !(signx ^ signy);
int lessEq = sameSign & !(diff & sign); // 符号相等 且 y-x >= 0
// 同符号的补码加法 才可能产生溢出，同符号补码减法 不产生溢出
// x < 0 && y > 0
return (!signx & signy) | lessEq;
}
//4
/*
* 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) {
// x有一位是1，则此位之后的位全部变为1
x = x | (x >> 1); // 低两位
x = x | (x >> 2); // 低四位
x = x | (x >> 4); // 低八位
x = x | (x >> 8);
x = x | (x >> 16);
// return ~(x >> 31) & 0x1; // 符号位(dlc failed, ops number excess)
return ~x & 0x1; // 最低位
// 方法2, 除0 和 0x80000000 外，一个数与其相反数符号相反；0x80000000的相反数是0x80000000；
// x = (x | (~x + 1)) >> 31; // 获取符号位
// return ~x & 1
}
/* 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) {
// 对于正数，第一个非零位+1所在位置
// 对于负数，第一个零位+1的位置
int n = 0; // 从最低位到第一个非零位的位数
// 对负数取反
x = x ^ (x >> 31); // 如果x为负，转为非负数，但值不等；非负数不变。之后就可以按照正数的查找方式来找第一个非零位
n = n + ((!!(x >> 16)) << 4); // 如果x右移16位后是0，说明x的高16位是0。如果不是，n累加 1<<4 = 16
n = n + ((!!(x >> (8 + n))) << 3); // 再右移8位
n = n + ((!!(x >> (4 + n))) << 2); // 4
n = n + ((!!(x >> (2 + n))) << 1); // 2
n = n + ((!!(x >> (1 + n)))); // 1
n = n + (x >> n); // 看看
return n + 1;
}
//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) {
int sign = uf & 0x80000000;
int exp = uf & 0x7f800000;
int frag = uf & 0x007fffff;
if (exp == 0) {
//非规格化的数
return sign | frag << 1;
}
if (exp == 0x7f800000) { // inf or NaN
return uf;
}
// 规格化的数
exp += 0x0800000; // 指数加1，相当于 乘二
if (exp == 0x7f800000) {
// inf
frag = 0;
}
return sign | exp | frag;
}
/*
* 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) {
int sign = uf & 0x80000000;
int exp = ((uf & 0x7f800000) >> 23) - 127; // 规格化数的指数的真值（非规格化数一律返回0）
int frag = (uf & 0x007fffff) | 0x00800000; // 补上前导1
int absval;
if (exp < 0) {
return 0;
}
if (exp > 30) {
return 0x80000000;
}
if (exp < 23) {
// 需要截断部分尾数
absval = frag >> (23 - exp);
} else {
absval = frag << (exp - 23);
}
return sign == 0x80000000 ? -absval : absval;
}
/*
* 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) {
if (x < -149) {
return 0;
}
// 非规格化的数
if (x < -126) {
return 0x800000 >> (-126 - x);
}
// 规格化的数
if (x <= 127) {
return (x + 127) << 23;
} else {
// +INF
return 0xff << 23;
}
}
ps: gdb好难用😅