CSC373/406: Integers: Datalab hints [4/9]

For next Tuesday: bitNor bitXor isNotEqual getByte copyLSB logicalShift bitCount bang leastBitPos tmax

/* 
 * bitNor - ~(x|y) using only ~ and & 
 *   Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
 *   Legal ops: ~ &
 *   Max ops: 8
 *   Rating: 1
 */
int bitNor(int x, int y) {
  //HINT: deMorgan's law
}
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 2
 */
int bitXor(int x, int y) {
  //HINT: alternative characterization of xor in notes
}
/* 
 * isNotEqual - return 0 if x == y, and 1 otherwise 
 *   Examples: isNotEqual(5,5) = 0, isNotEqual(4,5) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int isNotEqual(int x, int y) {
}
/* 
 * 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) {
}
/* 
 * copyLSB - set all bits of result to least significant bit of x
 *   Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int copyLSB(int x) {
}
/* 
 * logicalShift - shift x to the right by n, using a logical shift
 *   Can assume that 1 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ~ & ^ | + << >> !
 *   Max ops: 16
 *   Rating: 3 
 */
int logicalShift(int x, int n) {
  // HINT: return ((n==0) ? x : mysolution)
  // To compute mysolution, you can assume that n!=0
  //   Use arithmetic shift, then mask off the top n bits to 0
}
/*
 * 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) {
  //SOLUTION #1: one bit at a time
  // int m1 = 0x1;
  // int s1 = (x&m1) + ((x>>1)&m1) + ((x>>2)&m1) + ((x>>3)&m1)
  //   + ((x>>4)&m1) + ((x>>5)&m1) + ((x>>6)&m1) + ((x>>7)&m1)
  //   + ((x>>8)&m1) + ((x>>9)&m1) + ((x>>10)&m1) + ((x>>11)&m1)
  //   + ((x>>12)&m1) + ((x>>13)&m1) + ((x>>14)&m1) + ((x>>15)&m1)
  //   + ((x>>16)&m1) + ((x>>17)&m1) + ((x>>18)&m1) + ((x>>19)&m1)
  //   + ((x>>20)&m1) + ((x>>21)&m1) + ((x>>22)&m1) + ((x>>23)&m1)
  //   + ((x>>24)&m1) + ((x>>25)&m1) + ((x>>26)&m1) + ((x>>27)&m1)
  //   + ((x>>28)&m1) + ((x>>29)&m1) + ((x>>30)&m1) + ((x>>31)&m1);
  // return s1;
  // HINT: to do it faster, add the bits in each BYTE in parallel, 
  //       then add the four sums together.
}
/* 
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int bang(int x) {
  // TRICK: x and -x are nonnegative only at 0
}
/* 
 * leastBitPos - return a mask that marks the position of the
 *               least significant 1 bit. If x == 0, return 0
 *   Example: leastBitPos(96) = 0x20
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 4 
 */
int leastBitPos(int x) {
  // TRICK: the only bit set in both x and -x will be the least significant one 
  // +0x02 = 00000010
  // -0x02 = 11111110 = 11111101+1
  // +0x3C = 00111100
  // -0x3C = 11000100 = 11000011+1
}
/* 
 * TMax - return maximum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmax(void) {
}
/* 
 * isNonNegative - return 1 if x >= 0, return 0 otherwise 
 *   Example: isNonNegative(-1) = 0.  isNonNegative(0) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 3
 */
int isNonNegative(int x) {
}
/* 
 * isGreater - if x > y  then return 1, else return 0 
 *   Example: isGreater(4,5) = 0, isGreater(5,4) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isGreater(int x, int y) {
}
/* 
 * 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) {
  // HINT: 
  // int bias = x>0 ? 0 : ((1<<n)-1);
  // add in the bias and then shift right
}
/* 
 * absVal - absolute value of x (except returns TMin for TMin)
 *   Example: abs(-1) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 4
 */
int absVal(int x) {
  //HINT: return (x>=0)?x:-x;
}
/* 
 * 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) {
}