Du kannst nicht mehr als 25 Themen auswählen
Themen müssen entweder mit einem Buchstaben oder einer Ziffer beginnen. Sie können Bindestriche („-“) enthalten und bis zu 35 Zeichen lang sein.
456 Zeilen
12 KiB
456 Zeilen
12 KiB
/*
|
|
* CS:APP Data Lab
|
|
*
|
|
* <Please put your name and userid here>
|
|
*
|
|
* bits.c - Source file with your solutions to the Lab.
|
|
* This is the file you will hand in to your instructor.
|
|
*
|
|
* WARNING: Do not include the <stdio.h> header; it confuses the dlc
|
|
* compiler. You can still use printf for debugging without including
|
|
* <stdio.h>, although you might get a compiler warning. In general,
|
|
* it's not good practice to ignore compiler warnings, but in this
|
|
* case it's OK.
|
|
*/
|
|
|
|
#if 0
|
|
/*
|
|
* 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.
|
|
*/
|
|
|
|
|
|
#endif
|
|
/*
|
|
* bitAnd - x&y using only ~ and |
|
|
* Example: bitAnd(6, 5) = 4
|
|
* Legal ops: ~ |
|
|
* Max ops: 8
|
|
* Rating: 1
|
|
*/
|
|
int bitAnd(int x, int y) {
|
|
int temp1;
|
|
int temp2;
|
|
int temp3;
|
|
int res;
|
|
|
|
temp1=~x;
|
|
temp2=~y;
|
|
temp3=temp1|temp2;
|
|
res=~temp3;
|
|
// use (a AND b) == Not((Not a) or (Not b))
|
|
return res;
|
|
}
|
|
/*
|
|
* 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;
|
|
int temp;
|
|
int res;
|
|
|
|
mask = (0xff);
|
|
temp = x >> (n * 8);
|
|
res=mask&temp;
|
|
//get the mask 11111111 fit the wanted bit
|
|
return res;
|
|
}
|
|
/*
|
|
* 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 temp1;
|
|
int temp2;
|
|
int res;
|
|
|
|
//temp1=(x|-1)<<(32-n);
|
|
//temp2=x>>n;
|
|
//res=temp1^temp2;
|
|
temp1 = ~(1<<31); //n=0,>>-1 wrong! temp1:011111......1 (32)
|
|
temp2 = ((temp1 >> n) << 1)+1; //a trick to erase the top n 1s created by the arithmetic shift.
|
|
res = temp2 & (x >> n);
|
|
return res;
|
|
}
|
|
/*
|
|
* 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 count;
|
|
int temp1;
|
|
int temp2;
|
|
int temp3;
|
|
int mask1;
|
|
int mask2;
|
|
int mask3;
|
|
int mask4;
|
|
int mask5;
|
|
|
|
temp1 = (0x55) + (0x55 << 8);
|
|
temp2 = (0x33) + (0x33 << 8);
|
|
temp3 = (0x0f) + (0x0f << 8);
|
|
mask1 = (temp1) + (temp1 << 16);
|
|
mask2 = (temp2) + (temp2 << 16);
|
|
mask3 = (temp3) + (temp3 << 16);
|
|
mask4 = (0xff) + (0xff << 16);
|
|
mask5 = (0xff) + (0xff << 8);
|
|
|
|
count = (x & mask1) + ((x >> 1) & mask1);
|
|
count = (count & mask2) + ((count >> 2) & mask2);
|
|
count = (count & mask3) + ((count >> 4) & mask3);
|
|
count = (count & mask4) + ((count >> 8) & mask4);
|
|
count = (count & mask5) + ((count >> 16) & mask5);
|
|
|
|
return count;
|
|
}
|
|
/*
|
|
* bang - Compute !x without using !
|
|
* Examples: bang(3) = 0, bang(0) = 1
|
|
* Legal ops: ~ & ^ | + << >>
|
|
* Max ops: 12
|
|
* Rating: 4
|
|
*/
|
|
int bang(int x) {
|
|
int temp1;
|
|
int temp2;
|
|
int res;
|
|
|
|
temp1=(~x)+1; //0x00000000 0x80000000 compute (-x)
|
|
temp2=(x>>31)&1;
|
|
res=1^((((temp1^x)>>31)&1)|temp2);
|
|
//???A nice trick???
|
|
return res;
|
|
}
|
|
/*
|
|
* tmin - return minimum two's complement integer
|
|
* Legal ops: ! ~ & ^ | + << >>
|
|
* Max ops: 4
|
|
* Rating: 1
|
|
*/
|
|
int tmin(void) {
|
|
int res;
|
|
|
|
res=(-1)<<31;
|
|
return res;
|
|
}
|
|
/*
|
|
* 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 temp1;
|
|
int temp2;
|
|
int res;
|
|
|
|
temp1=x>>(n-1);
|
|
temp2=x>>31;
|
|
res=temp1^temp2;
|
|
return !res;
|
|
}
|
|
/*
|
|
* 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 temp1=x>>31;
|
|
int temp2=(1<<n)+(~0); //2^n-1
|
|
|
|
x=x+(temp1&temp2);
|
|
return x>>n;
|
|
}
|
|
/*
|
|
* negate - return -x
|
|
* Example: negate(1) = -1.
|
|
* Legal ops: ! ~ & ^ | + << >>
|
|
* Max ops: 5
|
|
* Rating: 2
|
|
*/
|
|
int negate(int x) {
|
|
int res;
|
|
|
|
res=(~x)+1;;
|
|
return res;
|
|
}
|
|
/*
|
|
* 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 temp1;
|
|
int temp2;
|
|
int res;
|
|
|
|
temp1=x>>31;
|
|
temp2=temp1&1;
|
|
res=(!temp2)&(!!x);
|
|
return res;
|
|
}
|
|
/*
|
|
* 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 s1,s2,valid,res;
|
|
//first judge two nums are both + or -, if not,easily judge.
|
|
//if it does,try x-y or y-x
|
|
s1=(x>>31)&1;
|
|
s2=(y>>31)&1;
|
|
valid=s1^s2; //equal?
|
|
res=y+(~x)+1;
|
|
return (((!(res>>31))&1)&(!valid))|(valid&(s1)&(!s2));
|
|
}
|
|
/*
|
|
* 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 count;
|
|
int temp1;
|
|
int temp2;
|
|
int temp3;
|
|
int temp4;
|
|
|
|
count=(!!(x>>16))<<4;
|
|
temp1=(x>>(count+8));
|
|
count=((!!temp1)<<3)+count;
|
|
temp2=(x>>(count+4));
|
|
count=((!!temp2)<<2)+count;
|
|
temp3=(x>>(count+2));
|
|
count=((!!temp3)<<1)+count;
|
|
temp4=(x>>(count+1));
|
|
count=(!!temp4)+count;
|
|
return count;
|
|
}
|
|
/*
|
|
* 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) {
|
|
unsigned temp,res;
|
|
|
|
temp = uf & 0x7fffffff;
|
|
res = uf ^ 0x80000000;
|
|
|
|
if(temp>0x7f800000)
|
|
res=uf; //NaN
|
|
return res;
|
|
}
|
|
/*
|
|
* 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 shiftleft,aftershift,tmp,flag,absx,sign;
|
|
|
|
shiftleft=0;
|
|
absx=x;
|
|
sign=0;
|
|
|
|
if(!x) return 0;
|
|
if(x<0){
|
|
sign=0x80000000;
|
|
absx=(~x)+1;
|
|
}
|
|
aftershift=absx;
|
|
|
|
for(;;){
|
|
tmp=aftershift;
|
|
aftershift=aftershift<<1;
|
|
shiftleft++;
|
|
if(tmp&0x80000000) break;
|
|
}
|
|
|
|
if((aftershift&0x01ff)>0x0100)
|
|
flag=1;
|
|
else if((aftershift&0x03ff)==0x0300)
|
|
flag=1;
|
|
else
|
|
flag=0;
|
|
|
|
return sign+(aftershift>>9)+((159-shiftleft)<<23)+flag;
|
|
//according to the design of float value, devide into 3 parts
|
|
//aftershift: last part, shiftleft: second part,count the multiples of 2, sign: first part, decide if x is + or -
|
|
}
|
|
/*
|
|
* 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 sign,normalized,special,itsign,doutem;
|
|
|
|
sign=1<<31;
|
|
itsign=uf&sign;
|
|
normalized=(uf<<1)>>24;
|
|
if(normalized==0xff)
|
|
special=1;
|
|
else
|
|
special=0;
|
|
//special number: NaN etc.
|
|
doutem=uf<<1;
|
|
if(special || (!uf) || uf==sign) //0 -0 special
|
|
return uf;
|
|
else if(normalized) //normalize
|
|
return uf + (1<<23);
|
|
else
|
|
return doutem | itsign; //second and last part are both multipled by 2.
|
|
}
|