|
I was working on a project all night for my computer architecure course. Finally done though.  It was damn frustrating though, here are some examples of function I had to implement with these restrictions:
| quote: |
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.
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.
|
and the (incomoplete) functions ...
| quote: |
/*
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
int bitAnd(int x, int y) {
/* x AND y = NOT (NOT x OR NOT y) (we get this by applying DeMorgans*/
return ~(~x | ~y);
}
/*
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 2
*/
int bitXor(int x, int y) {
/* x XOR y = (x AND (NOT y)) OR ((NOT y) AND y) (we get this form the truth table)
* it expands to the formula below to comply with the legal op requirement
*/
return ~(~(x & ~y) & ~(~x & y));
}
/*
* isEqual - return 1 if x == y, and 0 otherwise
* Examples: isEqual(5,5) = 1, isEqual(4,5) = 0
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int isEqual(int x, int y) {
/* x EQUIV y = ((NOT x) AND (NOT y)) OR (x AND y) (we get this from the truth table
* (NOT x) AND (NOT y) = NOT (x OR y)
*/
return ~(x | y) | (x & y);
}
/*
* evenBits - return word with all even-numbered bits set to 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 2
*/
int evenBits(void) {
/* x is originaly 1010(bin)
* we left shit it by 4 bits, then add eMask
* this process is repeated 2 more times to get the desired word
*/
int x = 0x55;
// the bit-mak eMask is a byte mask for the even bits,
int eMask = 0x55;
x = (x << 4) + eMask;
x = (x << 4) + eMask;
x = (x << 4) + eMask;
return x;
}
/*
* 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 negMask = 1 << 31;
int minus1 = (~1 + 1);
int n1 = n + minus1;
int nMask = ~(1 << n1) + 1;
int nMaskX = (nMask & x);
//int y = ~x + 1;
int isPos = !(x & negMask);
int all1s = ~0;
int pos = (all1s + !isPos) & !nMaskX);
// int neg = (all1s + isPos) & !(((nMaskX >> n) + (~nMask & x)));
int neg = (all1s + isPos) & !(((((!(!(nMaskX)) + !(!(~nMask & x)))) + minus1) >> 1));
return pos | neg;
}
/*
* bitMask - Generate a mask consisting of all 1's
* lowbit and highbit
* Examples: bitMask(5,3) = 0x38
* Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
* If lowbit > highbit, then mask should be all 0's
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int bitMask(int highbit, int lowbit) {
/* we use two temporary ints high and low
* high = 1 << (high + 1) - 1
* high in bit representation is 0 all the way to bit highbit + 1 and 1 afterwards
* low = 1 << lowbit - 1
* low in bit representation is 1 all the way to bit lowbit
* we return x which is high anded (bitwise) with low (x = high & low)
*/
int neg1 = ((~1) + 1);
int high = (1 << (hightbit + 1)) + neg1;
int low = ~((1 << lowbit) + neg1);
int x = hight & low;
return x;
}
/*
* conditional - same as x ? y : z --> if x != 0, then y, else z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) {
/* if ( x == 0) return z;
* else return y;
*/
int xZero = !x;
int all1s = ~0;
return ((all1s + xZero) & (y)) | ((all1s +!xZero) & (z));
}
/*
* reverseBytes - reverse the bytes of x
* Example: reverseBytes(0x01020304) = 0x04030201
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 25
* Rating: 3
*/
int reverseBytes(int x) {
return 2;
}
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x) {
return 2;
}
/*
* 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) {
/*couldn't figure this one out under 40 ops
*/
int i = 0;
i += 1 & x;
i += ( 1 & (x >> 1));
i += ( 1 & (x >> 2));
i += ( 1 & (x >> 3));
i += ( 1 & (x >> 4));
i += ( 1 & (x >> 5));
i += ( 1 & (x >> 6));
i += ( 1 & (x >> 7));
i += ( 1 & (x >> 8));
i += ( 1 & (x >> 9));
i += ( 1 & (x >> 10));
i += ( 1 & (x >> 11));
i += ( 1 & (x >> 12));
i += ( 1 & (x >> 13));
i += ( 1 & (x >> 14));
i += ( 1 & (x >> 15));
i += ( 1 & (x >> 16));
i += ( 1 & (x >> 17));
i += ( 1 & (x >> 18));
i += ( 1 & (x >> 19));
i += ( 1 & (x >> 21));
i += ( 1 & (x >> 22));
i += ( 1 & (x >> 23));
i += ( 1 & (x >> 24));
i += ( 1 & (x >> 25));
i += ( 1 & (x >> 26));
i += ( 1 & (x >> 27));
i += ( 1 & (x >> 28));
i += ( 1 & (x >> 29));
i += ( 1 & (x >> 30));
i += ( 1 & (x >> 31));
return i;
}
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
/* all we need to do is right shift 1 by 31 to get -(2^32)*/
int x = 1 << 31;
return x;
}
/*
* isNegative - return 1 if x < 0, return 0 otherwise
* Example: isNegative(-1) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 3
*/
int isNegative(int x) {
/**/
int mask = 1 << 31;
return !(!(mask & x));
}
/*
* multFiveEights - multiplies by 5/8 rounding toward 0.
* Examples: multFiveEights(77) = 48
* multFiveEights(-22) = -13
* You can assume |x| < (1 << 29)
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 3
*/
int multFiveEights(int x) {
/**/
// TOO MANY OPERATORS!!!!!!!!!!! FIIIIIIIIIIIIIIIIIIIIIIIIX ITTTTTTTTTTTTTTTTTTTTTTTTTTT!!!!!!!!!!!!!!!
int negMask = 1 << 31;
int isPos = !(x & negMask);
int all1s = ~0;
// y = x * 5;
int y = (x << 2) + x;
//y = y >> 3 if x is +ve
//y = ~(y >> 4) + 1 if x is -ve
int negY = (~(y >> 4)) + 1;
int posY = y >> 3
return ((all1s + isPos) & negY) | ((all1s + !isPos) & posY);
}
/*
* sum3 - x+y+z using only a single '+'
* Example: sum3(3, 4, 5) = 12
* Legal ops: ! ~ & ^ | << >>
* Max ops: 16
* Rating: 3
*/
/* A helper routine to perform the addition. Don't change this code */
static int sum(int x, int y) {
return x+y;
}
int sum3(int x, int y, int z) {
int word1 = sum(x, y);
int word2 = sum(z, 0);
/**************************************************************
Fill in code below that computes values for word1 and word2
without using any '+' operations
***************************************************************/
/**************************************************************
Don't change anything below here
***************************************************************/
return sum(word1,word2);
}
/*
* addOK - Determine if can compute x+y without overflow
* Example: addOK(0x80000000,0x80000000) = 0,
* addOK(0x80000000,0x70000000) = 1,
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int addOK(int x, int y) {
return 0;
}
/*
* isLess - if x < y then return 1, else return 0
* Example: isLess(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLess(int x, int y) {
/* we can divide this into 3 cases where x < y is possible
* each case is set to 1 if x < y
*/
int negMask = 1 << 31;
int xIsPos = !(x & negMask);
int yIsPos = !(y & negMask);
// case a: x is +ve
// y is +ve
int a = (x + (~y + 1)) >> 31;
// case b: x is -ve
// y is +ve
int b = (~(x + y) + 1) >> 31;
// case c: x is -ve
// y is -ve
int c = (x + (~y + 1)) >> 31;
return a | b | c;
}
/*
* abs - absolute value of x (except returns TMin for TMin)
* Example: abs(-1) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 10
* Rating: 4
*/
int abs(int x) {
int negMask = 1 << 31;
int isPos = !(x & negMask);
int all1s = ~0;
int y = (all1s + isPos) & (~x + 1);
int z = (all1s + !isPos) & x;
return y | z;
}
/*
* isNonZero - Check whether x is nonzero using
* the legal operators except !
* Examples: isNonZero(3) = 1, isNonZero(0) = 0
* Legal ops: ~ & ^ | + << >>
* Max ops: 10
* Rating: 4
*/
int isNonZero(int x) {
/* we check to see if x is negative by right shift it 31 bits
* next we see if x is positve by negating it then right shifting it by 31
* we return the OR of isNeg and isPos
*/
// if it is negative isNeg == 1
int isNeg = x >> 31;
// if it is positve isPos == 1
int isPos = (~x + 1) >> 31;
return isNeg | isPos;
}
/*
* tc2sm - Convert from two's complement to sign-magnitude
* where the MSB is the sign bit
* You can assume that x > TMin
* Example: tc2sm(-5) = 0x80000005.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 4
*/
int tc2sm(int x) {
/* first we mask it to see if x < 0
* if x > 0, return value = ~x + 1 + sign-bit (negMask);
+ else return value = x
*/
// sign-bit = 0 if +ve
int negMask = 1 << 31;
int isPos = !(x & negMask);
// the first 2 expression of y and z which are ANDed with the return value
// are used to determine which value to return
int all1s = ~0;
int y = (all1s + isPos) & (~x + 1 + negMask);
int z = (all1s + !isPos) & x;
return (y | z);
}
|
looks like fun right     
I apologize for my weird odd usage of smileys, been up all night, and not, I have another test to study for. I can't wait for the weekend and a bowl.
___________________
"The Greatest enemy of knowledge is not ignorance, it is the illusion of knowledge." -Stephen Hawking
"First they came for the communists, and I did not speak out— because I was not a communist;
Then they came for the socialists, and I did not speak out— because I was not a socialist;
Then they came for the trade unionists, and I did not speak out— because I was not a trade unionist;
Then they came for the Jews, and I did not speak out— because I was not a Jew;
Then they came for me— and there was no one left to speak out for me." -Martin Niemöller
|
