Data lab(two complements arithmetic)

1.bitAnd

This is a simple function, we learnt about this in discrete math in the last term.

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

2.getByte

The purpose of this function is to get the pointed byte. You can just write as you think.

/* 
 * 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) {
  return (x>>(n<<3))&0xff;
}

3.logicalShift

First, we need to know that right shift has 2 types:logical shift & arithmetic shift. In practice, however, almost all compiler/machine combinations use arithmetic right shifts for signed data, and many programmers assume this to be the case. Here is just the same case. Thus, we can calculate a mask, say 00…0(32-n)111..1(n). Then we just & this mask to x. Through this we will get the right answer. One more thing to mention, here I use an abnormal operation:you know if we >> 32, this is UB. In order to avoid this problem, I first >>31-n then >>1.

/* 
 * logicalShift - shift x to the right by n, using a logical shift
 *   Can assume that 0 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3 
 */
int logicalShift(int x, int n) {
  //int neg_pos=(x>>31)&0x1;
  int threone_n=31+((~n)+1);
  int mask=((1<<threone_n)<<1)+(~0);
  return (x>>n)&mask;
}

4.bitCount

In this function, we can not count each bit one by one for we are only allowed to use at most 40 operations. Thus we need to find a way to count more than one bit at a time. Here we generate a mask (0000000100000010000000100000001) and move x to & this mask. At last, we just need to get the sum of bits in this four parts.

/*
 * 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) {
  int mask=1+(1<<8)+(1<<16)+(1<<24);
  int bits=0;
  bits+=(x&mask);
  bits+=((x>>1)&mask);
  bits+=((x>>2)&mask);
  bits+=((x>>3)&mask);
  bits+=((x>>4)&mask);
  bits+=((x>>5)&mask);
  bits+=((x>>6)&mask);
  bits+=((x>>7)&mask);
  return (bits&0xFF)+((bits>>8)&0xFF)+((bits>>16)&0xFF)+((bits>>24)&0xFF);
}

5.bang

I find two different ways to solve this problem. One is binary search. Compress 32 bits to 1 and give the answer.

/* 
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int bang(int x) {
  x|=(x>>16);
  x|=(x>>8);
  x|=(x>>4);
  x|=(x>>2);
  x|=(x>>1);
  return (~x)&0x1;
}

6.tmin

xd,If you don’t know this, just restart to learn c.

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

写到一半发现自己的英语水平实在捉鸡 很多想表达出来的东西都表达不出来 虽然切换输入法真的很烦 但没办法 等什么时候英语逆天了就好了 以下都更为中文

7.fitsBits

这个问题需要分正数和负数两种情况讨论，对于正数来说，如果一个数x能表示成n位的补码，那么它从最高位直到第n位一定全部为0，它的第n位一定不能为1，否则它就会变成一个负数。对于一个负数来说，如果一个数x能表示成n位的补码，那么它只需从最高位到第n位全部为1即可。
因此，我们可以先将x右移n-1位，对于满足条件的正数和负数，这将产生一个全0的数或是一个全1的数。然后我们可以根据x的符号构造一个全0或者是全1的掩码。通过将这两个数按位异或并且取逻辑非，就能得到正确的结果。reference:深入理解计算机系统DataLab实验报告

/* 
 * 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) {
/* if fitsBits then from highest bit to n bit will all become 1 - negative number or 0 - positive number
 * then can construct a mask to implement fitsBits with the help of ^ and !
 */
    return !((x >> (n + (~1) + 1)) ^ (((1 << 31) & x) >> 31));
}

8.divpwr2

这题其实就是除一个2^n向下取整，正数直接logical shift，对于负数需要加一个bias，可以用x的符号位来区分二者。生成一个11.111或者00.000的mask来判断是否要加bias，最后直接右移。

/* 
 * 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) {
  int mask=x>>31;
  int bias=(1<<n)+(~0);
  int final_x=x+(mask&bias);
  return final_x>>n;
}

8.negate

不多说，基本上-号就是用它来实现的

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

9.isPositive

直接看符号位 但需要排除0的影响

/* 
 * isPositive - return 1 if x > 0, return 0 otherwise 
 *   Example: isPositive(-1) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 3
 */
int isPositive(int x) {
  int temp=((x>>31)&0x1);
  return (!temp)&(!(!x));
}

9.isLessOrEqual

一开始想的时候觉得很难 毕竟要用大部分都是对称性的运算符表示出一个非对称的运算符，但后来发现只要用-然后判断是正数还是负数就可以了。但这里需要考虑到补码运算溢出的情况，所以需要分类讨论，测试点里也会卡你这个点。当x,y异号，可能存在溢出，就直接判断x正数还是y正数，就可以直接给出答案。如果是同号，就不会溢出，那么就直接看符号位，对于这二者的综合，可以用mask看是否overflow了，最后用|来综合答案。

/* 
 * 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 y_x=y+((~x)+1);
  int mask=!((x^y)>>31);   //x y is + -(0) or + + or - -(1)
  int res_ovrflw=((x>>31)&0x1)&(!mask);
  int res_notovrflw=(!((y_x>>31)&0x1))&mask;
  return res_notovrflw|res_ovrflw;
}

10.ilog2

这题是我在去洗澡的路上想懂的。。。其实如果没有符号限制的话可以做一个模拟器，存到了没有1但过了几位，如果有就加上然后归0，如果没有就接着加。但是这里限制符号数量，那么就可以考虑用二分查找，这种思想在bang里也有。如果在17-32位中有1，就基数加16，然后在9-16位中找如果有就基数接着加8，以此类推，就很简单了。。。

/*
 * ilog2 - return floor(log base 2 of x), where x > 0
 *   Example: ilog2(16) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 90
 *   Rating: 4
 */
int ilog2(int x) {
  int count=0;
  int bias1=!(!(x>>16));
  count+=(bias1<<4);
  int bias2=!(!(x>>(count+8)));
  count+=(bias2<<3);
  int bias3=!(!(x>>(count+4)));
  count+=(bias3<<2);
  int bias4=!(!(x>>(count+2)));
  count+=(bias4<<1);
  int bias5=!(!(x>>(count+1)));
  count+=bias5;
  return count;
}