CSAPP之詳解DataLab

實(shí)驗(yàn)1—DataLab

實(shí)驗(yàn)材料

  1. 一個(gè)能夠運(yùn)行的Linux系統(tǒng)或Unix
  2. 下載好make
  3. 能夠運(yùn)行32位程序的gcc
  4. 官網(wǎng)的實(shí)習(xí)手冊(cè)

實(shí)驗(yàn)要求

整數(shù)編碼規(guī)則:

將每個(gè)函數(shù)中的“return”語(yǔ)句替換為一個(gè)或?qū)崿F(xiàn)該函數(shù)的多行C代碼。你的代碼必須符合以下風(fēng)格:

int Funct(arg1, arg2，…){
        /*簡(jiǎn)單描述你的實(shí)現(xiàn)如何工作*/
        int var1 = Expr1;
        …
        int varM = ExprM;
        varJ = ExprJ;
        …
        varN = ExprN;
        return ExprR;
}

每個(gè)"Expr"都是只使用以下語(yǔ)句的表達(dá)式:

  1. 整數(shù)常量0到255 (0xFF)，包括。你是不允許使用像0xffffffff這樣的大常量。

  2. 函數(shù)參數(shù)和局部變量(沒(méi)有全局變量)。

3.一元整型運(yùn)算 !~

  1. 二進(jìn)制整數(shù)運(yùn)算& ^ | + << >>

有些問(wèn)題進(jìn)一步限制了允許的運(yùn)算符的集合。每個(gè)“Expr”可以包含多個(gè)運(yùn)算符。你不不會(huì)被限制每行一個(gè)操作符。您被明確禁止:

  1. 使用任何控件結(jié)構(gòu)，如if、do、while、for、switch等。

  2. 定義或使用任何宏。

  3. 在此文件中定義任何附加函數(shù)。

  4. 調(diào)用任何函數(shù)。

  5. 使用任何其他操作，如 &&，||，-，或 ?：。

  6. 使用任何形式的對(duì)象轉(zhuǎn)換。

  7. 使用除int以外的任何數(shù)據(jù)類(lèi)型，這意味著你不能使用數(shù)組、結(jié)構(gòu)體或聯(lián)合。

你可以假設(shè)你的機(jī)器:

  1. 使用二進(jìn)制補(bǔ)碼，int類(lèi)型為32位表示。

  2. 使用算術(shù)右移。

3.在轉(zhuǎn)換時(shí)可能會(huì)發(fā)生溢出

浮點(diǎn)編碼規(guī)則對(duì)于需要實(shí)現(xiàn)浮點(diǎn)運(yùn)算的問(wèn)題，編碼規(guī)則不那么嚴(yán)格。你可以使用循環(huán)和有條件的控制。你可以同時(shí)使用整數(shù)和無(wú)符號(hào)。您可以使用任意整數(shù)和無(wú)符號(hào)常量。你可以使用任何算法，對(duì)int或unsigned數(shù)據(jù)進(jìn)行邏輯或比較操作。

但您被明確禁止:

  1. 定義或使用任何宏。

  2. 在此文件中定義任何附加函數(shù)。

  3. 調(diào)用任何函數(shù)。

  4. 使用任何形式的對(duì)象轉(zhuǎn)換。

  5. 使用除int或unsigned以外的任何數(shù)據(jù)類(lèi)型。這意味著你不能使用數(shù)組、結(jié)構(gòu)體或聯(lián)合。

  6. 使用任何浮點(diǎn)數(shù)據(jù)類(lèi)型、操作或常量。

實(shí)驗(yàn)規(guī)則

你需要通過(guò)修改bits.c中的函數(shù)來(lái)完成實(shí)驗(yàn)。每次修改后，你都需要鍵入下面兩條指令來(lái)檢查正確性，這意味著你需要安裝好make。

make clean
make btest

然后，你可以鍵入下面這條指令來(lái)輸出結(jié)果

./btest

2.62 DataLab

image.png

題目一：只使用 ~ 和 & 實(shí)現(xiàn) ^

題目代碼與解答：

/* 
 * 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);
}

解答：

根據(jù)布爾代數(shù)，代碼~(x & y)實(shí)現(xiàn)的是只要不同時(shí)為1則為1，只要我們除掉同時(shí)為0取1的情況便實(shí)現(xiàn)了異或，而代碼~x & ~y實(shí)現(xiàn)的是只有同時(shí)為0則為1，則~(~x & ~y)實(shí)現(xiàn)的是同時(shí)為0則為0，這樣就排除掉了同時(shí)為0取1的情況。

題目二：返回最小的補(bǔ)碼

題目代碼與解答：

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

解答：

0x80000000即為最小的補(bǔ)碼。

題目三：判斷是否為補(bǔ)碼的最大值

題目代碼與解答：

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

解答：

補(bǔ)碼的最大值為0x7fffffff，如果x是該值的話，那么x + x + 1應(yīng)該等于0xffffffff，按位取反則為0，邏輯運(yùn)算中，0為假，非0為真，邏輯非取邏輯反，則我們應(yīng)該返回 !(~(x+x+1))，它在x = 0x7fffffffff時(shí)返回1，而在其它時(shí)候返回0，不過(guò)請(qǐng)注意，當(dāng)x = 0xffffffff時(shí)，它仍然會(huì)返回1，所以我們需要特判這個(gè)數(shù)。

題目四：判斷補(bǔ)碼所有的奇數(shù)位是否都為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 = (0xAA << 8 ) + 0xAA;
  int b = (a << 16) + a;
  return ! ((x & b) ^ b);
}

解答：

奇數(shù)位全為1的掩碼為0xAAAAAAAA，我們需要利用移位技巧構(gòu)造這個(gè)掩碼，然后我們將x的偶數(shù)位置為0，最后再判斷它是否等于0xAAAAAAAA即可，判斷x == y可以采用!(x ^ y)來(lái)實(shí)現(xiàn)，它利用了異或的性質(zhì)。

題目五：不用負(fù)號(hào)實(shí)現(xiàn) -x

題目代碼與解答：

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

解答：

這個(gè)題目很簡(jiǎn)單，我們返回它的按位反再加一即可。因?yàn)榘次蝗》吹臄?shù)與原來(lái)數(shù)相加為0xffffffff，再加1即等于0。

題目六：判斷x是否為ASCII碼

題目代碼與解答：

/* 
 * 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 + (~0x30 + 1);
  int b = 0x39 + (~x + 1);
  int c = 0x1 << 31;
  return !(a & c) & !(b & c);
}

解答：

這個(gè)題目要求我們判斷x是否大于等于0x30且小于等于0x39，我們可以推出這樣兩個(gè)不等式，① x + (- 0x30) >= 0；2②0x39 + (- x) >= 0。我們只需要比較最終結(jié)果是否大于等于0就可以了，這等同于符號(hào)位是否為0，這可以通過(guò) & 0x80000000得出，如果符號(hào)位為0，& 0x80000000的結(jié)果一定是0，取邏輯反則為1；反之，如果符號(hào)位為1，取邏輯反的結(jié)果應(yīng)該為0。

我們要思考一下加法溢出是否會(huì)對(duì)結(jié)果造成影響，如果第一個(gè)等式發(fā)生溢出，則有 x - 0x30 < -232，那么x < -232+ 0x30，如果x = Tmin，那么-x = Tmin，則 0x39 + (-x) = 0x39 + Tmin < 0，這不滿足不等式②；如果x != Tmin，那么有 -x > 232 - 0x30，那么有0x39 + (-x) = 0x39 + 232 - 0x30 = 232 + 0x9，這發(fā)生了正溢出，因此它的結(jié)果會(huì)小于0，同樣不滿足等式②，因此第一個(gè)等式溢出并不會(huì)影響答案。第二個(gè)等式溢出可同理分析。

題目七：實(shí)現(xiàn)表達(dá)式 x ? y : 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) {
  int a = !!x;
  int b = (a << 31) >> 31;
  return (y & b) | (z & ~b);
}

解答：

分析代碼，如果x真則a = 1，b = 0xffffffff，y & b則置y為原數(shù)，z & ~b則值z(mì)為0，那么 (y & b) | (z & ~b)返回的便是y；如果x假則a = 0，b = 0，y & b則置y為0，z & ~b則值z(mì)為原數(shù)，那么 (y & b) | (z & ~b)返回的便是z

題目八：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 s = y + (~x + 1);
  int m = 1 << 31;
  int a = !!(x & m);
  int b = !!(y & m);
  int c = !!(a ^ b);
  int f = s & m;
  return (c & !b) | (!c & !f);
}

解答：

這道題可以采用y + (- x) >= 0解答，但我們必須要保證它沒(méi)有溢出。如果x與y異號(hào)，此時(shí)如果y為非負(fù)則返回1，否則返回0；如果x與y同號(hào)，我們判斷y + (-x)是否大于0即可。代碼中a,b,f計(jì)算x,y,s的符號(hào)，而c判斷x與y是否異號(hào)。

題目九：不使用 ! 實(shí)現(xiàn) !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;
}

解答：

對(duì)于x而言，除了0和Tmin之外，x 與~x + 1互為相反(符號(hào)位相反)數(shù)，這意味著肯定有一個(gè)數(shù)為負(fù)，即符號(hào)位為1，將一個(gè)符號(hào)位為1的數(shù)邏輯右移31位后會(huì)得到0xffffffff，加1則為0；對(duì)于Tmin而言，~x + 1 = Tmin，這說(shuō)明它們的符號(hào)位也為1，即答案也會(huì)是0；對(duì)于0而言，x 與~x + 1的符號(hào)位都為0，這意味著最終的結(jié)果會(huì)是1。

題目十：一個(gè)數(shù)用補(bǔ)碼表示最少需要幾位

題目代碼與解答：

/* 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) {
    int s = x >> 31;
    x = x ^ s;
    int b16 = !!(x >> 16) << 4;
    x = x >> b16;
    int b8 = !!(x >> 8) << 3;;
    x = x >> b8;
    int b4 = !!(x >> 4) << 2;
    x = x >> b4;
    int b2 = !!(x >> 2) << 1;
    x = x >> b2;
    int b1 = !!(x >> 1) << 0;
    x = x >> b1;
   return b16 + b8 + b4 + b2 + b1 + x + 1;
}

解答：

不斷縮小范圍即可，b16表示32位中，高16為是否有一，如果有b16 = 1 << 4 = 1，那么x就會(huì)右移16位，把返回縮小到高16位到高32位這個(gè)范圍，如果沒(méi)有，則把范圍縮小到0位到高16位這個(gè)范圍，如此反復(fù)，請(qǐng)不要忘了加上符號(hào)位！

題目十一：求2乘以一個(gè)浮點(diǎn)數(shù)

題目代碼與解答：

/* 
 * 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) {
    int exp = (uf >> 23) & 0xff;
    int sign = (uf & (1 << 31));
    int inf = 0x7f800000 | sign;
    if (exp == 255)     
      return uf;
    if (exp == 0)
      return (uf << 1) | sign;
    exp++;
    if (exp == 255)
      return inf;
    return (uf & 0x807fffff) | (exp << 23);
}

解答：

這個(gè)題目要求我們熟悉浮點(diǎn)數(shù)的表示，先取出uf的階碼域exp，如果這個(gè)數(shù)是一個(gè)特殊值，我們什么也不做，直接返回；如果這個(gè)數(shù)是非規(guī)格化數(shù)，得益于非規(guī)格化數(shù)到規(guī)格化數(shù)的平滑轉(zhuǎn)變，我們直接將uf左移一位即可，由于移除了符號(hào)位，請(qǐng)不要忘記添加上來(lái)；如果這個(gè)數(shù)是規(guī)格化的數(shù)，我們便將階碼加1，如果此時(shí)階碼 = 255，我們返回?zé)o窮大，否則的話，我們更新階碼并返回。

題目十二：將float轉(zhuǎn)換成int

題目代碼與解答：

/* 
 * 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 (incleuding 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) {
    int exp = (uf >> 23) & 0xff;
    int sign = uf & (1 << 31);
    if (exp == 255)
        return 0x80000000;
    if (exp == 0)
        return 0;
    int k = exp - 127;
    int f = uf & 0x00ffffff;
    if (k < 0)
        return 0;
    if (k > 31)
        return 0x80000000;
    if (k < 23)
        f >>= (23 - k);
    else
        f <<= (k - 23);
    if (sign)
        return ~f + 1;
    else
        return f;
}

解答：

先考慮特殊情況，當(dāng)exp == 255或exp == 0時(shí)，此時(shí)表示特殊值和非規(guī)格化的值，我們按要求返回。否則計(jì)算出階碼值k和小數(shù)域f，請(qǐng)注意這里f是需要多加一個(gè)1的，如果k < 0的話，我們返回0；如果k > 31的話，此時(shí)一定發(fā)生了溢出。其他情況下，我們根據(jù)k的值進(jìn)行移位，可以設(shè) f = [0000,0000,01X1X2,.......X23]，它的真實(shí)值以二進(jìn)制表示為1.X1X2,.......X23，如果k < 23的話，意味著并不是所有的小數(shù)都能移位至整數(shù)部分，則我們必須要舍去剩下的(23 - k)的小數(shù)值，所以選擇右移23-k位；如果k >= 23，說(shuō)明所有的小數(shù)都可以移動(dòng)到整數(shù)部分，如果k = 23的話，這正是[0000,0000,01X1X2,.......X23]的位表示，如果k > 23，我們?nèi)孕柘蛴乙苿?dòng)k-23位。最后，別忘了它的正負(fù)。

題目十三：計(jì)算2.0x

題目代碼與解答：

/* 
 * 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 e = x + 127;
    if (e >= 255)
        return 0x7f800000;
    if (x < 0)
        return 0;
    return e << 23; 
}

解答：

我們可以計(jì)算1.0 * 2x來(lái)達(dá)到這個(gè)目的，先排除掉幾個(gè)值之外，我們將x + Bias作為階碼域返回即可，此時(shí)規(guī)格化的值會(huì)默認(rèn)小數(shù)為1.0。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容