CSAPP–Data Lab实验记录
[TOC]
前言
Students implement simple logical, two’s complement, and floating point functions, but using a highly restricted subset of C. For example, they might be asked to compute the absolute value of a number using only bit-level operations and straightline code. This lab helps students understand the bit-level representations of C data types and the bit-level behavior of the operations on data.
实验要求
/*
* Instructions to Students:
*
* STEP 1: Read the following instructions carefully.
*/
You will provide your solution to the Data Lab by
editing the collection of functions in this source file.
INTEGER CODING RULES:
Replace the "return" statement in each function with one
or more lines of C code that implements the function. Your code
must conform to the following style:
int Funct(arg1, arg2, ...) {
/* brief description of how your implementation works */
int var1 = Expr1;
...
int varM = ExprM;
varJ = ExprJ;
...
varN = ExprN;
return ExprR;
}
Each "Expr" is an expression using ONLY the following:
1. Integer constants 0 through 255 (0xFF), inclusive. You are
not allowed to use big constants such as 0xffffffff.
2. Function arguments and local variables (no global variables).
3. Unary integer operations ! ~
4. Binary integer operations & ^ | + << >>
Some of the problems restrict the set of allowed operators even further.
Each "Expr" may consist of multiple operators. You are not restricted to
one operator per line.
You are expressly forbidden to:
1. Use any control constructs such as if, do, while, for, switch, etc.
2. Define or use any macros.
3. Define any additional functions in this file.
4. Call any functions.
5. Use any other operations, such as &&, ||, -, or ?:
6. Use any form of casting.
7. Use any data type other than int. This implies that you
cannot use arrays, structs, or unions.
You may assume that your machine:
1. Uses 2s complement, 32-bit representations of integers.
2. Performs right shifts arithmetically.
3. Has unpredictable behavior when shifting an integer by more
than the word size.
EXAMPLES OF ACCEPTABLE CODING STYLE:
/*
* pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
*/
int pow2plus1(int x) {
/* exploit ability of shifts to compute powers of 2 */
return (1 << x) + 1;
}
/*
* pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
*/
int pow2plus4(int x) {
/* exploit ability of shifts to compute powers of 2 */
int result = (1 << x);
result += 4;
return result;
}
FLOATING POINT CODING RULES
For the problems that require you to implent floating-point operations,
the coding rules are less strict. You are allowed to use looping and
conditional control. You are allowed to use both ints and unsigneds.
You can use arbitrary integer and unsigned constants.
You are expressly forbidden to:
1. Define or use any macros.
2. Define any additional functions in this file.
3. Call any functions.
4. Use any form of casting.
5. Use any data type other than int or unsigned. This means that you
cannot use arrays, structs, or unions.
6. Use any floating point data types, operations, or constants.
NOTES:
1. Use the dlc (data lab checker) compiler (described in the handout) to
check the legality of your solutions.
2. Each function has a maximum number of operators (! ~ & ^ | + << >>)
that you are allowed to use for your implementation of the function.
The max operator count is checked by dlc. Note that '=' is not
counted; you may use as many of these as you want without penalty.
3. Use the btest test harness to check your functions for correctness.
4. Use the BDD checker to formally verify your functions
5. The maximum number of ops for each function is given in the
header comment for each function. If there are any inconsistencies
between the maximum ops in the writeup and in this file, consider
this file the authoritative source.
/*
* STEP 2: Modify the following functions according the coding rules.
*
* IMPORTANT. TO AVOID GRADING SURPRISES:
* 1. Use the dlc compiler to check that your solutions conform
* to the coding rules.
* 2. Use the BDD checker to formally verify that your solutions produce
* the correct answers.
*/
实验内容
1. bitAnd
题目要求只能使用 ~ 与 | 进行解答。可以想想摩尔运算 A&B = ~（（~A) | (~B) )
/*
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
int bitAnd(int x, int y) {
return ~((~x)|(~y));
}
2 .getByte
获取第 （n+1） 字节。一个字节8 bit，n字节 为 8*n bit = (n«3) bit 。所以可以将x 右移 n«3 bit，然后与 0xff 做与运算，得到结果。
/*
* getByte - Extract byte n from word x
* Bytes numbered from 0 (LSB) to 3 (MSB)
* Examples: getByte(0x12345678,1) = 0x56
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int getByte(int x, int n) {
int mask=0xff;
return (x>>(n<<3))&mask;
}
3. logicalShift
在c语言中 >>运算为算术右移，当x<0 时，右移最高位会补1，x>0，右移最高位补0。而逻辑右移，最高位都是补0。
所以解题思路，可以先做 x»n 然后再与mask=0xfffffff移位后的结果做&运算。 ((0x1<<(32+~n))+~0)|(0x1<<(32+~n)) 这个就是构造mask的方法。
~0=-，这个式子就类似 (m-1)|(m) ,例如 7|8 == 0111 | 1000 =1111就是让最高位与后面的位都置1.
/*
* logicalShift - shift x to the right by n, using a logical shift
* Can assume that 0 <= n <= 31
* Examples: logicalShift(0x87654321,4) = 0x08765432
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int logicalShift(int x, int n) {
int mask=((0x1<<(32+~n))+~0)|(0x1<<(32+~n));
return (x>>n)&mask;
}
4. bitCount
这个题目要求算出 x 的二进制 中 1的个数。
/*
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
int bitCount(int x) {
int mk1, mk2, mk3, mk4, mk5, result;
mk5 = 0xff | (0xff << 8);
mk4 = 0xff | (0xff << 16);
mk3 = 0x0f | (0x0f << 8);
mk3 = mk3 | (mk3 << 16);
mk2 = 0x33 | (0x33 << 8);
mk2 = mk2 | (mk2 << 16);
mk1 = 0x55 | (0x55 << 8);
mk1 = mk1 | (mk1 << 16);
// 先把16个相邻两位有几个1，并用这两位表示，然后以此类推，
// 即： 32->16， 16->8， 8->4， 4->2， 2->1
result = (mk1 & x) + (mk1 & (x >> 1));
result = (mk2 & result) + (mk2 & (result >> 2));
result = mk3 & (result + (result >> 4));
result = mk4 & (result + (result >> 8));
result = mk5 & (result + (result >> 16));
return result;
}
5. bang
不能使用!计算 !x。这道题的思路是找x 的二进制数是否存在 1，那么可以利用二分查找的思想，先找高16位。若高16位为0，则找低16位。否则在高16位找。
然后又折半，找八位……以此类推，最后得到 x，0 ->1,1->0。
思路2 一个非0的数与其相反数做 |运算，则最高位为1， x |((~x)+1。当x=0时，结果依然为0。所以可以通过判断最高位的值然后做 ~运算 再&1得到结果。
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x) {
x=(x>>16)|x;
x=(x>>8)|x;
x=(x>>4)|x;
x=(x>>2)|x;
x=(x>>1)|x;
return ~x&0x1;
}
/*
*题解2
*/
int bang(int x) {
x=(x>>16)|x;
x=(x>>8)|x;
x=(x>>4)|x;
x=(x>>2)|x;
x=(x>>1)|x;
return ~x&0x1;
}
6. tmin
二进制补码最小值
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 0x1<<31;
}
7. fitsBits
只给出n个二进制位，能否表示x。
可以先将x 右移 n-1 位，然后，比较这时是否全1或全0，若是，则可以表示，若不是，则不能表示。
/*
* fitsBits - return 1 if x can be represented as an
* n-bit, two's complement integer.
* 1 <= n <= 32
* Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int fitsBits(int x, int n) {
int bit = ~(~n+1);
int temp = x>>bit;
return !temp|!(temp+1);
}
8. divpwr2
计算 x/(2^n) 但结果需要向0 靠近。
主要考虑负数的情况，因为 -33/16 = -3，向更小的方向靠近了。所以可以构造一个数 bias （偏置）使得在 x >= 0时，bias = 0；在 x < 0 时，bias = (1 « n) - 1;
/*
* divpwr2 - Compute x/(2^n), for 0 <= n <= 30
* Round toward zero
* Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int divpwr2(int x, int n) {
int bias=(x>>31)&((0x1<<n)+~0);
return (x+bias)>>n;
}
9. negate
相反数
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return (~x+1);
}
10. isPositive
判断是否为正数
/*
* isPositive - return 1 if x > 0, return 0 otherwise
* Example: isPositive(-1) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 3
*/
int isPositive(int x) {
int tmp=(x>>31)&0x1;
int ans = !(!tmp|x);
return ans;
}
11. isLessOrEqual
x <= y 是否成立。可以用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) {
int val=!!((x+~y)>>31);
x=x>>31;
y=y>>31;
return (!!x|!y)&((!!x&!y)|(val));
}
12. ilog2
思路有点像第五题，这道题主要是想找出最高位的1是第几位。
/*
* ilog2 - return floor(log base 2 of x), where x > 0
* Example: ilog2(16) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int ilog2(int x) {
int ans=0;
ans=(!!(x>>(16)))<<4;
ans=ans+((!!(x>>(8+ans)))<<3);
ans=ans+((!!(x>>(4+ans)))<<2);
ans=ans+((!!(x>>(2+ans)))<<1);
ans=ans+((!!(x>>(1+ans)))<<0);
return ans;
}
13. float_neg
计算浮点数x的负数。。浮点数是由s(1位)E(8位)M(23位)(-1)^s * M * 2^E组成的浮点数。判断是否为NAN
/*
* float_neg - Return bit-level equivalent of expression -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 representations of
* single-precision floating point values.
* When argument is NaN, return argument.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 10
* Rating: 2
*/
unsigned float_neg(unsigned uf) {
int c=0x00ffffff;
if(((uf<<1)^(0xffffffff))<c){
return uf;
}else{
return uf^(0x80000000);
}
}
14. float_i2f
将int转换为float
/*
* float_i2f - Return bit-level equivalent of expression (float) x
* Result is returned as unsigned int, but
* it is to be interpreted as the bit-level representation of a
* single-precision floating point values.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned float_i2f(int x) {
unsigned ans;
int tmpx=x;
int f=0;
int delta=0;
int tail=0;
int E=0;
if(x == 0) return x;
if(x == 0x80000000) return 0xcf000000;
ans=x&0x80000000;
if(ans) tmpx = -x;
while( (tmpx>>E)) E++;
E = E -1;
tmpx = tmpx<<(31-E);
tail = (tmpx >> 8) & 0x007FFFFF;
f = tmpx & 0xff;
delta =(f>128) || ( (f == 128) && (tail & 1) );
tail+=delta;
E=E+127;
if(tail >> 23)
{
tail = tail &0x007FFFFF;
E+=1;
}
ans=ans | E << 23 | tail;
return ans;
}
15. float_twice
/*
* float_twice - 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 float_twice(unsigned uf) {
unsigned S=uf&0x80000000;
unsigned E=uf&0x7F800000;
unsigned M=uf&0x007FFFFF;
unsigned wu = 0xFF000000;
unsigned tmp = uf << 1;
unsigned ans = uf;
if( ( wu & tmp ) == wu)
{
return uf;
}
if(E != 0)
{
ans=S+(E+0x00800000)+M;
}
else if( M!=0 )
{
ans=S+E+(M << 1);
}
return ans;
}