path: root/bits.c

/* 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;
}