CA1_Datalab记录

写在前面

其实一开始是没有写博客的打算的,所以没有详细记录过程

一些题目参考了知乎大佬的文章

1

// 1
/*
 * bitXor - x^y using only ~ and &
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y)
{
  return (~(x & y)) & (~(~x & ~y));
}

2

/*
 * tmin - return minimum two's complement integer
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void)
{

  return 0x80 << 24;
}

3

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x)
{
  return !(~x ^ (x + 1)) & (!!~x);
}

4

/*
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x)
{
  int mask = 0xaa << 8 | 0xaa;
  mask = mask << 16 | mask;
  return !((mask & x) ^ mask);
}

5

/*
 * negate - return -x
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x)
{
  return ~x + 1;
}

6

/*
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x)
{
  int MaskB = 0xf;
  return (!(((x & MaskB) + 6) >> 4)) & (!((x >> 4) ^ 0x3)) & !!x;
}

7

/*
 * conditional - same as x ? y : z
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z)
{
  x = !!x;
  x = (x << 1) + x;
  x = (x << 2) + x;
  x = (x << 4) + x;
  x = (x << 8) + x;
  x = (x << 16) + x;
  return (x & y) | ((~x) & z);
}

8

/*
 * 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 flagx = (x >> 31 & 1);
  int flagy = (y >> 31 & 1);
  int notZero = !!(flagx ^ flagy);
  int flag = ~notZero + 1;
  int less = ((x + (~y + 1)) >> 31 & 1);
  return (!(x ^ y)) | ((flag & flagx) | (~flag & less));
}

9

/*
 * logicalNeg - implement the ! operator, using all of
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
 */
int logicalNeg(int x)
{ /*超过了操作数
   x = x << 1 | x >> 1 | x;
   x = x << 2 | x >> 2 | x;
   x = x << 4 | x >> 4 | x;
   x = x << 8 | x >> 8 | x;
   x = x << 16 | x >> 16 | x;
   return x + 1;
   */
  return ((x | (~x + 1)) >> 31) + 1;
}

10

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x)
{
  int b16, b8, b4, b2, b1, b0;
  int sign = x >> 31;
  x = (sign & ~x) | (~sign & x);
  b16 = !!(x >> 16) << 4;
  x = x >> b16;
  b8 = !!(x >> 8) << 3;
  x = x >> b8;
  b4 = !!(x >> 4) << 2;
  x = x >> b4;
  b2 = !!(x >> 2) << 1;
  x = x >> b2;
  b1 = !!(x >> 1);
  x = x >> b1;
  b0 = x;
  return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}

11

/*
 * 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.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf)
{
  unsigned s = uf & (1 << 31);
  unsigned exp = (uf & 0x7f800000) >> 23;
  unsigned frac = uf & (~0xff800000);

  if (exp == 0)
    return frac << 1 | s;
  if (exp == 255)
    return uf;
  exp++;
  if (exp == 255)
    return 0x7f800000 | s;
  return s | (exp << 23) | frac;
}

12

/*
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf)
{
  unsigned s = uf & (1 << 31);
  unsigned exp = (uf & 0x7f800000) >> 23;
  unsigned frac = uf & (~0xff800000);

  int E = exp - 127; // 阶数
  if (exp == 0Xff || E > 31)
    return 0x80000000u;
  if (E < 0)
    return 0;
  int Ori = frac | (0x800000);
  unsigned ret = (E > 23 ? Ori << (E - 23) : Ori >> (23 - E));
  if (s)
    ret *= -1;

  return ret;
}

13

/*
 * 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: Any integer/unsigned operations incl. ||, &&. Also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatPower2(int x)
{
  int frac, exp;
  if (x >= 128)
    return 0x7f800000;
  if (x >= -126)
  {
    return ((x + 127) << 23);
  }
  if (x >= -149)
  {
    return (1 << (x + 149));
  }
  return 0;
}