CS:APP LAB1: data lab

啟用方式

将壓縮包解壓，使用指令行進入目錄，輸入

make

,然後輸入

./btest

即可開始測試

int注意事項

Each "Expr" is an expression using ONLY the following:

1. Integer constants 0 through 255 (0xFF), inclusive. You are

   not allowed to use big constants such as 0xffffffff.

2. Function arguments and local variables (no global variables).
3. Unary integer operations ! ~
4. Binary integer operations & ^ | + << >>

Some of the problems restrict the set of allowed operators even further.

Each "Expr" may consist of multiple operators. You are not restricted to

one operator per line.

You are expressly forbidden to:

1. Use any control constructs such as if, do, while, for, switch, etc.
2. Define or use any macros.
3. Define any additional functions in this file.
4. Call any functions.
5. Use any other operations, such as &&, ||, -, or ?:
6. Use any form of casting.

7. Use any data type other than int. This implies that you

   cannot use arrays, structs, or unions.

You may assume that your machine:

1. Uses 2s complement, 32-bit representations of integers.
2. Performs right shifts arithmetically.

3. Has unpredictable behavior when shifting if the shift amount

   is less than 0 or greater than 31.

簡單來說，就是不能用控制語句，函數，宏

運算符隻能用+以及一些位運算，邏輯符号隻能用!(具體看每道題目的要求)

bitXor

簡單的異或

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

int bitXor(int x, int y) {
  /*
  0 1 = 1,其餘為0
  a&~b = 1時，當且進當 a = 1且b = 0
  b&~a = 1時，當且進當 b = 1且a = 0
  二者或在一起就是同或了
而 a | b = ~~(a|b) = ~(~a&~b)
  */
    return ~(~(x&~y)&~(y&~x));
  }
           

tmin

隻需要記住補碼的範圍是-2n-1~2n-1-1即可

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

  int t = 1<<31;
  return  t;

}
           

isTmax

最大值即2n-1-1，或者說是01111..1

這裡方法挺多的，就隻用一個簡單的表示把

/*
 * 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) {
  /*
  當且僅當x為最大數時，x+1 = 10000..00,此時按位加1000.0000等于0
  */
   int t = ~x + ~x;
    t = t|!(x+1);
    return !t;
}
           

allOddBits

構造出一個奇數位上全為1，其他位置全為0的數，然後将這個數與檢測數進行

&

，如果待檢測的數有若幹個奇數位為0，則結果将在構造的數的基礎上，損失一些1，在利用當且僅當a=b時,有a^b=0的性質，來檢驗計算出來的值是否有損失1，如果損失了，則說明并不滿足田間，否則奇數位全是1.

/* 
 * 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 a = 0xa;
  a = (a<< 4) + a;
  a = (a<<8) + a;
  a = (a <<16) + a;
  return !((x   &a)^a);
}
           

negate

究極基礎題，但我還是忍不住提一嘴補碼的一些東西.

由于計算機存儲有限，是以整型資料有一種叫做“模”的東西限制了資料的範圍，将模記作mod

則對于滿足x = y + mod*a(0<=y<mod)的x和y來說,在計算機存儲的内容均為y，這也就意味着，在整形資料計算過程中，任意的加入模進行加減運算其實都是不影響結果的。

是以，我們考慮兩個資料a,b的做差，即 a - b的計算，我們可以在計算前，在中間加入一個mod，即

a-b = a + (mod - b)，由于計算過程是在計算機中進行的整形計算，是以b肯定是要小于mod的，故(mod-b)必然為正數，這樣就可以将減法運算轉化為加法運算。

同時，我們知道計算機的資料全是由01，也就是二進制表示的，是以我們可以将mod = 1 000...000寫成,1111...111+1的形式

而1111...111 - b，左邊的每一位都有1，而b用二進制表示為01串，每一位都可以和左邊的對應位置的位對應上，而1-0=1,1-1=0，是以結果相當于b上的每一位都進行了取反。

别忘了前面還漏掉了一個1，是以負數也就是(0-b) = (mod-b) = ~b+1

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

isAsciiDigit

這道題我主要是将0x3m(0<=m<9)拆分成了0003和m分别檢驗

首先是将資料右移，将m占用的位移出去，就可以不考慮m的影響。然後就像是上面提到的結論一樣，隻有當這個數是0x3時，他異或上0x3才為0.

接着就是檢驗m了，考慮到需要的範圍時0~9，而在這個範圍内的數字，在加上6以後最大為0xf，是不會産生進位的，而0xa ~ 0xf得資料卻會産生進位，是以将資料加上一個6，再用上面的方式檢驗0x3是否改變即可

/* 
 * 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) {
  /*
  當且僅當倆個數一模一樣的時候，按位加才為0,是以先檢測前面是否為3,在然後排除0x3a等情況，加上6之後，a以及之後的數會産生進位
  */
  // return !((x^0x30)>>4)|(((x+0x6)^0x30)>>4); 括号沒打好
  int t1 = (x>>4)^3;
  int t2 = ((x+6)>>4)^3;
  return !(t1|t2);
}
/* 
           

conditional

這個主要是利用了0和111111(即-1）互相取反的關系，而任何數&0則會将資料完全清空，而&11111則會保持不變，對倆個數分别&上0和111再|在一起，就可以實作保留一個資料而清空一個資料，而任何數|0仍然得到這個數，進而可以得到保留特定挑選的數，也就是選擇性的挑出一個資料的效果。

/* 
 * 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) {
  /*
  将0轉化為0,非0值轉化為1111111
  */
  int flag = !x;
  flag =  flag + ~0;
  return (y&flag )| (~flag&z);
}
           

isLessOrEqual

這個還蠻麻煩的

首先就是将x,y的符号給提取出來。(這裡姑且将0看作正數)

然後可以分為3種情況，分别将結果作為條件碼儲存

1.x正，y負,必然是x大，傳回0

2.x負,y正，x小，傳回1

3.x,y符号相同，直接采用做差的方式，判斷結果的符号位是正是負來判斷大小關系，由于x,y同号，是以作差時也就不需要考慮溢出問題。

最後将這三個條件碼合理的用邏輯符号組合在一起就行

值得一提的是，雖然題目不讓用 &&和||，但是由于前面三個條件碼隻會為0或者1，是以采用&和|其實取到的效果是一樣的。

/* 
 * 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) {
  /*
當x > 0的,y小于0,傳回false,x<0,y大于0,傳回true,t1則是根據符号位來判斷是否是
  */
  int sigx = x>>31,sigy = y>>31;
  int t1 = sigx&(!sigy);
  int t2 = sigy&(!sigx);
   int t3 = y + ~x + 1;
  t2 = !t2;
  t3 = t3 >>31;
  t3 = !t3;

  return t1|(t2&t3);
}
           

logicalNeg

這個的話呢還是困擾了我蠻久的

方法一：自己想的

判斷一個數是不是非0的方法很簡單，直接給他加一個離模差1的數，看他溢不溢出就完事了，但是C語言的溢出了的話，我也看不到條件碼，就不能采取這麼直接的方法了。

于是可以考慮人為的将資料縮短一點，即将資料的後16位|上前16位，因為資料非0的話，那麼前面和後面16位至少有一個處非全0，二者|在一起得到的16位肯定是非0的，同時我們将這個得到的資料除了得到的16位，前面的16位清空。

那麼，隻要原本的數非0，我們就可以得到一個非0的16位的串。

這時候，我們以216次方為模，給這個串加上一個216-1，若資料非0，那麼第16位上肯定有一個溢出的1，否者仍然為0.

方法二：知乎上看來的

在補碼的範圍中，除去0和最小的數比較特殊，每一個數都有對應的相反數，通過取反加一可以得到一個符号相反的相反數，二者的符号或在一起便是1，而0通過取反加一得到的仍然為0，或在一起為0，而最小數取反加一得到的也是自己，但是符号位都是1，或在一起結果也是1.

也就是說，非0數與自己的相反數（或者說取反加一得到的數）|在一起，符号位均為1，而0通過這樣的操作符号位為0.

通過以上倆種操作，我們就可以區分0和非0數了，剩下就很簡單了~

/* 位
 * 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) {
  /*  
  
  */
  int  y =x>>16;
  int n = ((1<<16)+ ~1 + 1);
  y = y&n;
  x = x & n;
  x = x|y;
  x = x + n;
  x = x>> 16;
  x = 2 + ~x ;
  return x;
}
           

howManyBits

想要用一個最短的串來表示一個數

首先我們肯定需要一個0或者1來表示符号

然後對于正數而言，除了符号位的0以外的前導0都是沒有什麼特别實質的意義的，是以都可以删去，也就是說僅需要保留從左往右，第一個1前面的0作為符号位即可。

為了避免分類，同時注意到，正負數情況時的高度相反性，可以對負數直接取反，這樣就可以直接進行正數的操作。

到這一步，目标就很明确了，就是求出數中從左往右第一個1所在的位置，再加上1即可。

這裡主要是采取了二分的方法，将左半邊的數單獨取出來，如果非0的話，說明左邊一定有1，是以第一個1一定在左邊，否則在右邊。

/* 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
 *            -5 = 1011
 *            howManyBits(0)  = 1
 *             0 = 0
 *            howManyBits(-1) = 1
 *             -1 = 111111 = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  /*
  從左往右，找到第一個不等于符号位的，位數+1
    現将負的轉化為正的
    然後就是找到第一個1的位置
  */
        int mask = x>>31;
    x = x^mask;
    int  a =  1;
   
    int t = !(x>>16);    
    t = t + ~1+1;
    t = 16&t;
    a = t+a;
    x = x>>t;
    // printf("%x\n",x);

    t = !(x>>8);   
     t = t + ~1+1;
    t = 8&t;
    a = t+a;
    x = x>>t;
    // printf("%x\n",x);
    
    t = !(x>>4);   
    t = t + ~1+1;
    t = 4&t;
    a = t+a;
    x = x>>t;
    // printf("%x\n",x);
    
    t = !(x>>2);   
    t = t + ~1+1;
    t = 2&t;
    a = t+a;
    x = x>>t;
    // printf("%x\n",x);
    
    t = !(x>>1);   
    t = t + ~1+1;
    t = 1&t;
    a = t+a;
    x = x>>t;
    // printf("%x\n",x);

    t = !x;   
    t = t + ~1+1;
    t = 1&t;
    a = t+a;
    // printf("%x\n",x);
    return a;
}
           

float的注意事項

FLOATING POINT CODING RULES

For the problems that require you to implement floating-point operations,
the coding rules are less strict.  You are allowed to use looping and
conditional control.  You are allowed to use both ints and unsigneds.
You can use arbitrary integer and unsigned constants. You can use any arithmetic,
logical, or comparison operations on int or unsigned data.

You are expressly forbidden to:
  1. Define or use any macros.
  2. Define any additional functions in this file.
  3. Call any functions.
  4. Use any form of casting.
  5. Use any data type other than int or unsigned.  This means that you
     cannot use arrays, structs, or unions.
  6. Use any floating point data types, operations, or constants.


NOTES:
  1. Use the dlc (data lab checker) compiler (described in the handout) to 
     check the legality of your solutions.
  2. Each function has a maximum number of operations (integer, logical,
     or comparison) that you are allowed to use for your implementation
     of the function.  The max operator count is checked by dlc.
     Note that assignment ('=') is not counted; you may use as many of
     these as you want without penalty.operatorsRPRISES:
 *   1. Use the dlc compiler to check that your solutions conform
 *      to the coding rules.
 *   2. Use the BDD checker to formally verify that your solutions produce 
 *      the correct answers.
 */
           

float

/* 
 * 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 int s = uf>>31;
  unsigned int e = uf<<1;
  e = e >>24;
  unsigned int m = uf<<9;
  m = m>>9;

  if(e==255){
    return uf;
  }
  if(e == 254){
    return (s<<31)+(255<<23);
  }
  if(e>0){
    return (s<<31)+((e+1)<<23)+m;
  }
    return (s<<31)+(m<<1);
}
/* 
 * 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 int s = uf>>31;
  unsigned int e = uf<<1;
  e = e >>24;
  unsigned int m = uf<<9;
  m = m>>9;
//   printf("s = %x e = %x,m = %x\n",s,e,m);
  if(e<127){
    return 0;
  }
  if(e-127>=31){
    return 1<<31;
  }
  m = (1<<23)+m;
//   printf("%x\n",m);
  int p = e-127 + 1;
//   printf("%d\n",p);
  p = 24 - p;
//   printf("%d\n",p);
  m = m>>p;
//   printf("%d\n",m);
  m = s?-m:m;
  return m;
}
/* 
 * 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 INF = 255<<23;
    if(x>127)return INF;
    if(x<-149)return 0;
    if(x>-127)return (x+127)<<23;
    int t = -126 - x;
    t = 23 - t;
    t = 1<<t;
    return t;
}