CSAPP — DataLab

CSAPP實驗記錄

Data Lab

??實驗的內容是關于計算機資訊的表示，主要包括位操作、整型及浮點型相關知識，

題目串列

題目及思路

bitXor(x, y)

使用取反(~)和與(&)兩種位運算實作異或操作(^)，

• 代碼

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

• 方法
  ?異或操作 ^ ：參與運算的位相同時回傳0，不同時回傳1，通過 ~ 和 & 計算同時為0 ~(~x&~y)和同時為1~(x&y)，此時回傳0，而不相同時回傳1，

tmin()

使用位運算獲取補碼的最小值 0x80000000即-2147483648，

• 代碼

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

• 方法
  ?int資料型別4位元組，在X86系統中占32位，補碼的最小值為符號位為1，其余全為零，即0x80000000,簡單的方法就是對1進行左移操作，

isTmax(int x)

通過位運算判斷輸入數值是否是補碼最大值，即0x7FFFFFFF，

• 代碼

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 2
 */
int isTmax(int x) {
  return (!(x+1+x+1))&(!!(x+1));
}

• 方法
  ?int資料型別的補碼最大值是符號位為0，其他位全為1，即0x7FFFFFFF，這里的思路是將Tmax轉換為0，同時排除特殊情況，由位運算規則可知，Tmax+1 = tmin，并且Tmax+tmin+1 = 0，特殊情況x = 0xFFFFFFFF時經上述操作時也會為0，但是x=-1時加1為零，可通過這種方法進行排除，

allOddBits(int x)

判斷所有奇數位是否都為1

• 代碼

/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x){
  return !((x&0xAAAAAAAA)^0xAAAAAAAA);
}

• 方法
  ?采用掩碼方式解決，構造奇數位全為1的數0xAAAAAAAA，首先通過與& 操作 獲取x的奇數位，其他位清零，然后再與0xAAAAAAAA進行異或^ 操作，若相同回傳為0，然后回傳其邏輯非，

negate(int x)

回傳輸入的相反數，這里主要考察補碼的知識，

• 代碼

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

• 方法
  ?根據補碼的定義，一個補碼的表示的數其相反數可用~x+1表示，這里不用考慮 tmin，

isAsciiDigit(int x)

計算輸入是否在0x30~0x39之間，

• 代碼

/* 
 * 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) {
	int a = (x >> 4) ^ 0x3; //判斷輸入是否為0x3x
	int c0 = (x>>3)&0x1; //第四位是否為1
	int c1 = (x>>2)&0x1; //第三位是否為1
	int c2 = (x>>1)&0x1; //第二位是否為1
			
  return (!a) & ((!c0) | (c0&(!c1)&(!c2)));
}

• 方法
  ?x的范圍0011 0000 ~ 0011 1001，可以看出若x在范圍內時，其第5 6位一定為1，高位全為0，此時若第4位為0，或者第4位為1，第2 3位都為0時，x在范圍內，因此通過 & 和 | 組合判斷，

conditional(int x, int y, int z)

通過位運算實作三目運算子x ? y : z，x不為0時回傳y，只有當x=0時回傳z，

• 代碼

/* 
 * 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) {
        x=!!x;
        x=~x+1; //轉換為全0或全1
  return (x&y) | (~x&z);
}

• 方法
  ?當x==0時表示為全0，x!=0時表示為全1，因此0的補碼是其本身，位表示全0；1的補碼是-1，位表示全1，所以第一步先通過邏輯非操作獲得布林值0或1，然后求其補碼，最后通過 位運算回傳最終值，

isLessOrEqual(int x, int y)

通過位運算實作x<=y操作，

• 代碼

/* 
 * 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 xSign = x>>31;
	int ySign = y>>31;
	
	int sameSign = !(xSign^ySign); //正負相同
	// 若同號 x-y>0, 即x-y-1>=0,即x+~y>=0
	int greaterXY = (x+~y) >> 31; 

	int xPos_yNeg = (!xSign) & ySign; //x為正數y為負數
	int isGreater = xPos_yNeg | (sameSign&!greaterXY);
	return !isGreater;
}

• 方法
  ?實作<=，可以轉換為實作>=，因此實作>=的方法為：首先獲取x,y的符號位，此時有兩種情況異號時x為正數，y為負數；同號時x大于y，異號時判斷較為簡單，比較32位的符號位即可，同號時x-y不會溢位，必有x-y>0，即x-y-1>=0，即x+(~y+1)-1>=0，然后檢查符號位就可判斷，

logicalNeg(int x)

通過位運算實作 邏輯非 !，

• 代碼

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

• 方法
  ?只有0和tmin的補碼為其本身，但是除0外，所有數和其補碼進行與操作后符號位都為1，

howManyBits(int x)

任意數用補碼表示最少需要幾位，

• 代碼

/* 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
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
	/*問題等價于求解最高位的1的位置（負數的話為找最高位0的位置）*/
    int b16,b8,b4,b2,b1,b0;
    int sign = x>>31; //判斷符號位
    x = (sign & ~x) | (~sign & x); //正數不變負數按位取反，都變為找最高位1的位置
    b16 = !!(x>>16) << 4; //若高16位存在1，則b16=16，否則b16=0
    x = x>>b16;//若高16位存在則右移16位，繼續確定位置，否則不移動
    b8 = !!(x>>8) << 3;
    x = x>>b8;
    b4 = !!(x>>4) << 2;
    x = x>>b4;
    b2 = !!(x>>2) << 1;
    x = x>>b2;
    b1 = !!(x>>1);
    x = x>>b1;
    b0 = x;

  return b16+b8+b4+b2+b1+b0+1; //+1表示加上符號位
}

• 方法
  ?對于正數來說，需要找到其最高的一位是1的，再加上符號位；若是負數，則需要知道其最高的一位是0的再加上符號位（例如1101和101補碼表示的是一個值-3），先判斷高16位是否存在，若存在則繼續在高16位中尋找，不存在則尋找第16位，以此類推找到確定位置，

float_twice(unsigned uf)

計算2*f，需要了解浮點數的儲存結構，

s	exp	frac
符號位	階數	數值

例如 1011 0111 則s=1，exp=E+bias=6+7=13，frac=001001
v=(-1) ^s^ * M * 2^E^

• 代碼

/* 
 * 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
 */
unsigned float_twice(unsigned uf) {
	/*存盤方式 s exp frac (s:符號位 E=exp-bias)
	 *v = (-1)^s * M * 2^E (0<M<2)
	 * */
	unsigned exp = (uf&0x7f800000) >> 23;//取出exp，即階數，也可以<< 1 >> 24的方法取出
	unsigned sign = uf & (1<<31);   //取出符號位

	//階數為零
	if(exp==0) return uf<<1 | sign; //相當于原數乘2
	//階數為255 ，即無窮大或NaN
	if(exp==255) return uf;
	//階數正常時，乘2等價于階數加1
	exp++;
	if(exp==255) return 0x7f800000 | sign;  //溢位
	return exp<<23 | (uf&0x007fffff) | sign;
}

• 方法
  ?按浮點數定義，特殊值直接回傳；規范化浮點數，階數加1；非規范化的，左移一位保持符號位不變，

float_i2f(int x)

將一個整型數轉換為浮點數儲存，從符號位，階碼，尾數和舍入入手，

• 代碼

/* 
 * 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
 */
unsigned float_i2f(int x) {
	unsigned E = 0;  //階數
	unsigned frac=0;
  	unsigned round=0; //舍入誤差	
  	unsigned sign = x & (1<<31); //取出符號位
 
	unsigned absX = sign ? (~x+1) : x; //求絕對值
	unsigned temp = absX;
	while((temp = temp>>1)) //求階數
		++E;    //因為整型數所以E一定是大于等于0的
	frac = absX << (31-E)<<1; //因為默認第一位為1，所以舍去第一位的1
	round = frac <<23>>23; //求的被舍去部分
	frac = frac >> 9; //求的尾數
		
	if(round > 0x100) round = 1;  //大于一半 加1
	else if(round < 0x100) round =0; //小于一半 舍棄
    else round = frac & 1; //等于一半 取最近的偶數
 
    //x為0時，其浮點型以為0  || exp=E+bias (bias=127 單精度)
	return x ? (sign | ((E+0x7F)<<23) | frac) +round: 0;
}

• 方法
  ?浮點型中不用補碼方式表示，因此對于負數要轉換為正數，提取出符號位，考慮一下特殊情況和舍入誤差即可，這里用到的中間變數應該為unsigned型別，移位時為邏輯移位，

float_f2i(unsigned uf)

浮點型轉換為整型，和上一題思路差不多，

• 代碼

/* 
 * float_f2i - 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 float_f2i(unsigned uf) {
	unsigned sign = uf & (1<<31);  //取出符號位
    unsigned E = ((uf&0x7f800000)>>23)-0x7F; //階數
    unsigned frac = (uf&0x007fffff) | 0x00800000; //取出frac，將小數部分變為整數，補上默認的最高位1

    if(E < 0) return 0; //
    else if(E>31) return 0x80000000;  //NaN 回傳0x80000000
    else if(E>23)  frac = frac << (E-23); //若階數大于23，則需要將frac向右移
    else frac = frac >> (23-E); //若階數小于23 將frac向左移
	
	if(!sign) 
		return frac;  //正數 直接回傳    
	else 
		return ~frac+1;
}

• 方法
  ?首先考慮特殊情況，exp==0和exp==255，然后根據階數的大小正確移動尾數，要記得浮點型表示時舍去了默認的最高位的1，最后回傳其補碼表示，

結果及思考

• 結果
  
  在float部分，因為沒有正確理解int型和unsigned型在移位操作中方式導致一直沒出來結果，在int型中移位操作是算術移位，左移時補 ‘符號位’ ；unsigned型中移位操作是邏輯移位，左移時補 ‘0’，

• 思考
  通過實驗也暴露了自己的一些問題，在后面的一些難度較高題目時，還是習慣性從網上查找資料來解決，結果不對時，不能很快的找到問題出錯點，還是因為一些知識沒有完全掌握，希望以后可以更加獨立的完成任務，對實驗知識進行更深更全面的總結，