/* WARNING: Do not include any other libraries here,
* otherwise you will get an error while running test.py
* 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.
*
* Using printf will interfere with our script capturing the execution results.
* At this point, you can only test correctness with ./btest.
* After confirming everything is correct in ./btest, remove the printf
* and run the complete tests with test.py.
*/
/*
* bitAnd - x & y using only ~ and |
* Example: bitAnd(4, 5) = 4
* Legal ops: ~ |
* Max ops: 7
* Difficulty: 1
*/
int bitAnd(int x, int y) {
return (~((~x)|(~y)));
}
/*
* bitXor - x ^ y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 7
* Difficulty: 1
*/
int bitXor(int x, int y) {
return ~(x & y) & ~(~x & ~y);
}
/*
* samesign - Determines if two integers have the same sign.
* 0 is not positive, nor negative
* Example: samesign(0, 1) = 0, samesign(0, 0) = 1
* samesign(-4, -5) = 1, samesign(-4, 5) = 0
* Legal ops: >> << ! ^ && if else &
* Max ops: 12
* Difficulty: 2
*
* Parameters:
* x - The first integer.
* y - The second integer.
*
* Returns:
* 1 if x and y have the same sign , 0 otherwise.
*/
int samesign(int x, int y) {
if (!x)
return !y;
if (!y)
return 0;
return !((x ^ y) >> 31);
}
/*
* logtwo - Calculate the base-2 logarithm of a positive integer using bit
* shifting. (Think about bitCount)
* Note: You may assume that v > 0
* Example: logtwo(32) = 5
* Legal ops: > < >> << |
* Max ops: 25
* Difficulty: 4
*/
int logtwo(int v) {
int r = 0;
int s;
s = (v > 0xFFFF) << 4;
v = v >> s;
r = r | s;
s = (v > 0xFF) << 3;
v = v >> s;
r = r | s;
s = (v > 0xF) << 2;
v = v >> s;
r = r | s;
s = (v > 0x3) << 1;
v = v >> s;
r = r | s;
r = r | (v >> 1);
return r;
}
/*
* byteSwap - swaps the nth byte and the mth byte
* Examples: byteSwap(0x12345678, 1, 3) = 0x56341278
* byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD
* Note: You may assume that 0 <= n <= 3, 0 <= m <= 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 17
* Difficulty: 2
*/
int byteSwap(int x, int n, int m) {
int ns = n << 3;
int ms = m << 3;
int diff = ((x >> ns) ^ (x >> ms)) & 0xFF;
return x ^ (diff << ns) ^ (diff << ms);
}
/*
* reverse - Reverse the bit order of a 32-bit unsigned integer.
* Example: reverse(0xFFFF0000) = 0x0000FFFF reverse(0x80000000)=0x1 reverse(0xA0000000)=0x5
* Note: You may assume that an unsigned integer is 32 bits long.
* Legal ops: << | & - + >> for while ! ~ (You can define unsigned in this function)
* Max ops: 30
* Difficulty: 3
*/
unsigned reverse(unsigned v) {
v = ((v >> 1) & 0x55555555) |
((v & 0x55555555) << 1);
v = ((v >> 2) & 0x33333333) |
((v & 0x33333333) << 2);
v = ((v >> 4) & 0x0F0F0F0F) |
((v & 0x0F0F0F0F) << 4);
v = ((v >> 8) & 0x00FF00FF) |
((v & 0x00FF00FF) << 8);
v = (v >> 16) | (v << 16);
return v;
}
/*
* logicalShift - shift x to the right by n, using a logical shift
* Examples: logicalShift(0x87654321,4) = 0x08765432
* Note: You can assume that 0 <= n <= 31
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Difficulty: 3
*/
int logicalShift(int x, int n) {
return (x >> n) & (~(!n + ~0) | (0x7FFFFFFF >> (n + ~0 + !n)));
}
/*
* leftBitCount - returns count of number of consective 1's in left-hand (most) end of word.
* Examples: leftBitCount(-1) = 32, leftBitCount(0xFFF0F0F0) = 12,
* leftBitCount(0xFE00FF0F) = 7
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 50
* Difficulty: 4
*/
int leftBitCount(int x) {
int y = ~x;
int t;
int count = (!(y >> 16)) << 4;
t = !(y >> (25 + ~count));
count = count + (t << 3);
t = !(y >> (29 + ~count));
count = count + (t << 2);
t = !(y >> (31 + ~count));
count = count + (t << 1);
t = !(y >> (32 + ~count));
count = count + t;
return count + !y;
}
/*
* 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: if else while for & | ~ + - >> << < > ! ==
* Max ops: 30
* Difficulty: 4
*/
unsigned float_i2f(int x) {
unsigned a;
unsigned sign;
unsigned sig;
int p;
int s;
if (!x)
return 0;
if (x < 0) {
sign = 0x80000000u;
a = ~x;
a = a + 1;
} else {
a = x;
sign = 0;
}
sig = a;
p = 0;
while (sig >> 1) {
sig = sig >> 1;
p = p + 1;
}
if (p < 24) {
sig = a << (23 - p);
} else {
s = p - 23;
sig = (a + (1u << (s - 1)) - 1u
+ ((a >> s) & 1u)) >> s;
p = p + (sig >> 24);
}
return sign | ((p + 127) << 23) | (sig & 0x7FFFFF);
}
/*
* 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.p
* When argument is NaN, return argument
* Legal ops: & >> << | if > < >= <= ! ~ else + ==
* Max ops: 30
* Difficulty: 4
*/
unsigned floatScale2(unsigned uf) {
unsigned sign;
unsigned exp;
sign = uf & 0x80000000;
exp = uf & 0x7F800000;
if (exp == 0x7F800000) {
return uf;
}
if (exp == 0) {
return sign | ((uf & 0x7FFFFFFF) << 1);
}
if (exp == 0x7F000000) {
return sign | 0x7F800000;
}
return uf + 0x00800000;
}
/*
* float64_f2i - Convert a 64-bit IEEE 754 floating-point number to a 32-bit signed integer.
* The conversion rounds towards zero.
* Note: Assumes IEEE 754 representation and standard two's complement integer format.
* Parameters:
* uf1 - The lower 32 bits of the 64-bit floating-point number.
* uf2 - The higher 32 bits of the 64-bit floating-point number.
* Returns:
* The converted integer value, or 0x80000000 on overflow, or 0 on underflow.
* Legal ops: >> << | & ~ ! + - > < >= <= if else
* Max ops: 60
* Difficulty: 3
*/
int float64_f2i(unsigned uf1, unsigned uf2) {
unsigned sign = uf2 >> 31;
unsigned exp = (uf2 >> 20) & 0x7FF;
int E;
int mant;
int mag;
int k;
if (exp < 1023){
return 0;
}
if (exp >= 1054){
return ~0x7FFFFFFF;
}
E = exp - 1023;
mant = (uf2 & 0xFFFFF) | 0x100000;
if (E <= 20) {
mag = mant >> (20 - E);
} else {
k = E - 20;
mag = (mant << k) | (uf1 >> (32 - k));
}
if (sign) {
return -mag;
}
return mag;
}
/*
* 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: < > <= >= << >> + - & | ~ ! if else &&
* Max ops: 30
* Difficulty: 4
*/
unsigned floatPower2(int x) {
if (x < -149) {
return 0;
}
if (x < -126) {
return 1 << (x + 149);
}
if (x <= 127) {
return (x + 127) << 23;
}
return 0x7F800000;
}
