Datalab实验

实验内容

1. bitAnd

1.1实验要求

• bitAnd - x&y using only ~ and |
• Example: bitAnd(6, 5) = 4
• Legal ops: ~ |
• Max ops: 8
• Rating: 1

1.2代码

int bitAnd(int x, int y) {
  return ~((~x) | (~y));
}

1.3解题思路

根据德摩根定律，x&y <==> ₍₍x) | (~y))

2. getByte

2.1 实验要求

• 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

2.2 代码

int getByte(int x, int n) {
	n = n << 3;
	x = x >> n;
  	return x&(0xff);
}

2.3 解题思路

令x右移8*n位，使得目标为变为二进制下最低的8位，在与0xff相与，将高位清零。

3. logicalShift

3.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

3.2 代码

int logicalShift(int x, int n) {
	int y = (1 << 31) >> n;
	x = x >> n;
	y = y << 1;
	y = ~y; 
  	return x&y;
}

3.3 解题思路

先将x算术右移n位，再构造低n位为1，其余位均为0的y，返回x&y的值即为所求

4. bitCount

4.1 实验要求

• bitCount - returns count of number of 1's in word
• Examples: bitCount(5) = 2, bitCount(7) = 3
• Legal ops: ! ~ & ^ | + << >>
• Max ops: 40
• Rating: 4

4.2 代码

int bitCount(int x) {
	int count,tmp1,tmp2,tmp3,tmp4,tmp5;
	count = 0;
	tmp1 = (0x55) | (0x55 << 8);
	tmp1 = tmp1 | (tmp1 << 16);
	tmp2 = (0x33) | (0x33 << 8);
	tmp2 = tmp2 | (tmp2 << 16);
	tmp3 = (0x0f) | (0x0f << 8);
	tmp3 = tmp3 | (tmp3 << 16);
	tmp4 = (0xff) | (0xff << 16);
	tmp5 = (0xff) | (0xff << 8);
	count = (x & tmp1) + ((x >> 1) & tmp1);
	count = (count & tmp2) + ((count >> 2) & tmp2);
	count = (count & tmp3) + ((count >> 4) & tmp3);
	count = (count & tmp4) + ((count >> 8) & tmp4);
	count = (count & tmp5) + ((count >> 16) & tmp5); 
 	return count;
}

4.3 解题思路

本题难点在于只允许使用40个操作符，考虑采用二分法。先将相邻两位相加，再对上一步所得结果的每两位看作一个整体，将相邻位相加......以此类推。最终使用36个操作符。

5. bang

5.1 实验要求

• bang - Compute !x without using !
• Examples: bang(3) = 0, bang(0) = 1
• Legal ops: ~ & ^ | + << >>
• Max ops: 12
• Rating: 4

5.2 代码

int bang(int x) {
	int tmp = (~x) + 1;
	tmp = tmp | x;
	tmp = tmp >> 31;
  return tmp+1;
}

5.3 解题思路

如果x非0，则x或-x必有一个最高为为1，将x|(-x)算术右移31位可得到所有位全为1的数，再+1即可得到0.

如果x为0，则x和-x最高为均为0，将x|(-x)算术右移31位得到的还是0，再+1即可得到1.

6. tmin

6.1 实验要求

• tmin - return minimum two's complement integer
• Legal ops: ! ~ & ^ | + << >>
• Max ops: 4
• Rating: 1

6.2 代码

int tmin(void) {
  return (1 << 31);
}

6.3 解题思路

最小的二进制补码整数最高位为1，其余全为0.

7. fitsBits

7.1 实验要求

• 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

7.2 代码

int fitsBits(int x, int n) { 
	int shift = 33 + (~n);
	return !(((x << shift) >> shift) ^ x);
}

7.3 解题思路

假设n=3只有当0x11111...[1xx]或0x00000...[0xx]我们才能用n个二进制位来表式x.

先将x左移32-n位，再算术右移32-n位，然后与x异或，接着取“！”即可

8. divpwr2

8.1 实验要求

• 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

8.2 代码

int divpwr2(int x, int n) {
	int sign,tmp;
	sign = x >> 31;//判断符号 
	tmp = sign & ((1 << n) + (~0)); 
    return (x+tmp) >> n;
}

8.3 解题思路

如果x是正数，直接算术右移n位即可。

如果x是负数，算术右移n位后需要向上取整。

• 向上取整方法：

  在算术右移之前加上一个低n位全为1，其余为全为0的数。

9. negate

9.1 实验要求

• negate - return -x
• Example: negate(1) = -1.
• Legal ops: ! ~ & ^ | + << >>
• Max ops: 5
• Rating: 2

9.2 代码

int negate(int x) {
  return (~x)+1;
}

9.3 解题思路

二进制补码求负数，直接取反加1即可

10. isPositive

10.1 实验要求

• isPositive - return 1 if x > 0, return 0 otherwise
• Example: isPositive(-1) = 0.
• Legal ops: ! ~ & ^ | + << >>
• Max ops: 8
• Rating: 3

10.2 代码

int isPositive(int x) {
  	return !!((~(x >> 31))&x);
}

10.3 解题思路

如果符号位为1，~(x >> 31)可得到0x00000000。将0x00000000&x后可得到0，在取两次！！后依旧为0.

如果符号位为0，~(x >> 31)可得到0xffffffff。如果x为0，将0xffffffff&x后可得到0在取两次！！后依旧为0. 如果x>0，将0xffffffff&x后可得到x,在取两次！！后即可得到1.

11. isLessOrEqual

11.1 实验要求

• isLessOrEqual - if x <= y then return 1, else return 0
• Example: isLessOrEqual(4,5) = 1.
• Legal ops: ! ~ & ^ | + << >>
• Max ops: 24
• Rating: 3

11.2 代码

int isLessOrEqual(int x, int y) {
	int sign,ret1,ret2;
	sign = (x^y) >> 31;
	ret1 = ((~x+1+y)>>31)&(~sign);//如果x和y同号 
	ret2 = (y>>31) & sign;
  	return !(ret1|ret2);
}

11.3 解题思路

本题难点在于如果直接用y-x>=0来判断，存在y-x溢出的情况。

但我们很容易发现，只有在y和x异号时才会出现溢出的情况，所以只需先判断y和x的符号，如果符号相同，则通过y-x是否非负来判断结果；如果符号不同，则直接判断符号位即可比较大小。

12. ilog2

12.1 实验要求

• ilog2 - return floor(log base 2 of x), where x > 0
• Example: ilog2(16) = 4
• Legal ops: ! ~ & ^ | + << >>
• Max ops: 90
• Rating: 4

12.2 代码

int ilog2(int x) {
	int ret = 0;
	ret = (!!(x >> 16)) << 4;
	ret = ret + ((!!(x >> (ret + 8))) << 3);
	ret = ret + ((!!(x >> (ret + 4))) << 2);
	ret = ret + ((!!(x >> (ret + 2))) << 1);
	ret = ret + (!!(x >> (ret + 1)));
  	return ret;
}

12.3 解题思路

本题可以转化为寻找最高位的1在哪个位置的问题，很容易可以想到采用二分查找难点在于如何在不使用循环体的情况下实现二分。维护一个ret，先将32位二进制数x右移16位，判断移位后的结果是否为0来判断高16位是否含1.如果含1，最终结果必然在16~31之间则令ret+=16，然后再用同样方法以此类推。最终找到最高为1的位置。

13. float_neg

13.1 实验要求

• float_neg - Return bit-level equivalent of expression -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 representations of
• single-precision floating point values.
• When argument is NaN, return argument.
• Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
• Max ops: 10
• Rating: 2

13.2 代码

unsigned float_neg(unsigned uf) {
	unsigned tmp;
	tmp = uf & (0x7fffffff);
	if (tmp > 0x7f800000)
		return uf;
 	return uf ^ (0x80000000);
}

13.3 解题思路

如果uf 为nan，直接返回uf。否则直接将符号位取反即可。

14. float_i2f

14.1 实验要求

• 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: Any integer/unsigned operations incl. ||, &&. also if, while
• Max ops: 30
• Rating: 4

14.2 代码

unsigned float_i2f(int x) {
    unsigned shiftLeft=0;
    unsigned afterShift, tmp, flag;
    unsigned absX=x;
    unsigned sign=0;
    if (x==0) return 0;
    //if x < 0, sign = 1000...,abs_x = -x
    if (x<0)
    {
        sign=0x80000000;
        absX=-x;
    }
    afterShift=absX;
    //count shift_left and after_shift
    while (1)
    {
        tmp=afterShift;
        afterShift<<=1;
        shiftLeft++;
        if (tmp & 0x80000000) break;
    }
    if ((afterShift & 0x01ff)>0x0100)
        flag=1;
    else if ((afterShift & 0x03ff)==0x0300)
        flag=1;
    else
        flag=0;
    return sign + (afterShift>>9) + ((159-shiftLeft)<<23) + flag;
}

14.3 解题思路

整数转浮点数经典题。

如果x为0，直接return 0.

如果x为负数，记录符号，然后把x变为正数。

一直左移，直到溢出，并记录移位次数。

afterShift记录尾数部分，159-shiftleft表示阶码

如果大于一半进一，少于一半则舍弃，等于一半则向偶数舍入

15. float_twice

15.1 实验要求

• float_twice - 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

15.2 代码

unsigned float_twice(unsigned uf) {
    unsigned f = uf;
    if ((f & 0x7F800000) == 0) 
        f = ((f & 0x007FFFFF) << 1) | (0x80000000 & f);
    else if ((f & 0x7F800000) != 0x7F800000)
        f =f + 0x00800000;
    return f;
}

15.3 解题思路

如果阶码为0，则直接将尾数左移一位，如果尾数溢出则恰好移入阶码，再加上符号位即可。

如果阶码全为1，则直接返回f。

如果阶码不为0且不全为1，则直接给阶码+1。

实验结果