ICS的第一个lab,现在想起来当时真是好认真,每个函数都是想了很久,自己一点点写出来的。其实第一个lab的难度挺高的,主要体现在数学方面= =高数期中挂科表示数学无力,这个lab记得DL是两周,真的是花了整整一周的时间在做,题目常常需要的操作有减法,考虑正负等等问题。

代码

我的代码在这里,仅供参考哦

第一个问题

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

第一个问题,是模拟!操作,非零输出0,零输出1。我的做法是取他的相反数,然后根据相反数跟其原来的数字的符号做操作,想法很直观。

##第二个问题

/*Q2 
* 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 m1=0x11 | (0x11<<8);  
    int mask=m1 | (m1<<16);  
    int s = x&mask;  
    s+=x>>1&mask;  
    s+=x>>2&mask;  
    s+=x>>3&mask;  
    s=s+(s>>16);  
    mask=0xf | (0xf<<8);  
    s=(s&mask)+((s>>4)&mask);//this is the things what the teacher said in class  
    return (s+(s>>8))&0x3f;  
}

第二个问题,题目意思是计算二进制中1的个数。其实不会做,但是老师上课给了这道题的答案= =好烦,不看了。

##第三个问题

/* Q3 
* 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) {  
    x = x & 0x1;  
    x = (x << 31);  
    x = (x >> 31);//watch the MSB  
    return x;  
}

第三个问题,是要求把所有bit置成跟最后一个bit一样,看分值就知道很简单,取出最后一位,左右移动31位就成了。

##第四个问题

/* Q4 
* 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) {  
    return (x+(((x>>31)&0x1)<<n)+~((x>>31)&0x1)+0x1)>>n;  
}

第四个问题,是计算除以2的N次幂,这个显然会想到用移位操作,除以2的N次方基本就是向哪边移动N位,但是考虑到要支持负数,会麻烦一点。

##第五个问题

/* Q5
* evenBits - return word with all even-numbered bits set to 1
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 8
*   Rating: 2
*/
int evenBits(void) {
    int x=0x55;
    return x+(x<<8)+(x<<16)+(x<<24);//0x55555555
}

第五个问题,偶数位全为1。很简单,但是值得注意的是直接return 0x55555555是不符合pdf里的要求的,嗯。

##第六个问题

/* Q6
* 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) {
    n = (x>>(n+~1+1));
    return !(n)^!(~n);//>>can do it
}

第六个问题,如果可以在n位内表示出x,那就返回1,否则为0。先把x右移n-1位,再检查是否全0或者全1就OK了。

##第七个问题

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

第七个问题,得到第n个byte的内容,纯粹移位就成。

##第八个问题

/* Q8 
 * 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) {  
    int sx = (x>>31)&0x1;  
    int sy = (y>>31)&0x1;  
    int sa = (x+(~y)+1);  
    return (((sx^sy)&sy)|((!(sx^sy))&(!!sa)&!((sa>>31)&0x1)));//cause if by "|"  
}

第八个问题,判断大小,先符号,再做减法。

##第九个问题

/* Q9 
 * 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) {  
    return !(x&(0x1<<31));  
}

第九个问题,返回正负,很简单。

##第十个问题

/* Q10 
 * 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) {  
  return !!(x+(~y)+0x1);  
}

第十个问题,判断是否相等,做减法就好。

##第十一个问题

/*Q11 
 * isPower2 - returns 1 if x is a power of 2, and 0 otherwise 
 *   Examples: isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0 
 *   Note that no negative number is a power of 2. 
 *   Legal ops: ! ~ & ^ | + << >> 
 *   Max ops: 60 
 *   Rating: 4 
 */  
int isPower2(int x) {  
  int m1=0x11 | (0x11<<8);  
  int mask=m1 | (m1<<16);  
  int s = x&mask;  
  s+=x>>1&mask;  
  s+=x>>2&mask;  
  s+=x>>3&mask;  
  s=s+(s>>16);  
  mask=0xf | (0xf<<8);  
  s=(s&mask)+((s>>4)&mask);  
  s=s+(~1)+1;//use the bitCount to achieve it  
  return !(s);  
} 

第十一个问题,判断是否是2的幂,可以用第二题破之。

##第十二个问题

/*Q12
 * 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) {  
  return x&(~x+1);  
}  

第十二个问题,4分的原因可能是题目比较长吧,找出最低的等于1的有效位= =利用数字与他的相反数除了最后一位一样其他相反的性质可破

##第十三个问题

/* Q13
 * 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) {  
    int temp0 = x>>n;  
    int temp1 = ((0x1<<31)+(~1)+1)>>n;  
    int temp2 = ((x>>31)&0x1)<<(31+(~n)+1);  
    return (temp0&temp1)+(temp2);//use overflow make the mask,then we can achieve it  
}

第十三个问题,逻辑移位,不改0的那种,temp1是关键。

##第十四个问题

/*Q14 
 * satAdd - adds two numbers but when positive overflow occurs, returns 
 *          maximum possible value, and when negative overflow occurs, 
 *          it returns minimum positive value. 
 *   Examples: satAdd(0x40000000,0x40000000) = 0x7fffffff 
 *             satAdd(0x80000000,0xffffffff) = 0x80000000 
 *   Legal ops: ! ~ & ^ | + << >> 
 *   Max ops: 30 
 *   Rating: 4 
 */  
int satAdd(int x, int y) {  
    int sx = (x>>31)&0x1;  
    int sy = (y>>31)&0x1;  
    int sxay = ((x+y)>>31)&0x1;  
    int answer1 = ((((sx^sy)+(!((sx^sy)|(sxay^sx))))<<31)>>31)&(x+y);  
    int answer2 = ((((!(sx^sy))&(sx^sxay))<<31)>>31)&(((0x1<<31)+(~1)+1)+sx);  
    return answer1|answer2;//use "|" to get if   
}

第十四个问题,加法,溢出返回可能的最大值。主要是用操作模拟if。

##第十五个问题

/*Q15
 * tc2sm - Convert from two's complement to sign-magnitude  
 *   where the MSB is the sign bit 
 *   You can assume that x > TMin 
 *   Example: tc2sm(-5) = 0x80000005. 
 *   Legal ops: ! ~ & ^ | + << >> 
 *   Max ops: 15 
 *   Rating: 4 
 */  
int tc2sm(int x) {  
    int temp = (x>>31);  
    int sign = temp&0x1;  
    return (sign<<31)+((x^temp)+sign);//signs don't change  
}

最后一个问题,补码转符号型表示(术语是啥忘了,就是用正数的第一个bit变成1来表示他的相反数),不难。

评论