changed 4 years ago  
Linked with GitHub

CS:APP Data Lab 解題筆記

tags: cs:app

Data Lab 是 CS:APP 的第一個實驗，主要是訓練學員對於位元操作、整數和浮點數的相關概念。

bitXor

題目需求：對兩個整數輸入 x & y, 僅使用 ~, & 完成 XOR 函數操作
題解：

  1. 先利用 XOR = (x & ~y) | (~x & y) 的特性，那接下來的問題就是要如何用 ~, & 來表示 |
  2. 利用集合的概念， A|B = ~ (~A & ~B)
/* 
 * 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)) & ~(y & (~x)));
}

tmin

題目需求：回傳最小二補數整數值
題解：將 1 左移 31 即可

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

istmax

題目需求: 判斷輸入有號整數 x 是否為 Tmax
題解:

  1. 利用 Tmax + 1 會溢出成 Tmin 的特性， ((Tmax + 1) = Tmin) ^ Tmax + 1 = 0，對 0 做 ! 操作為 1，寫成 bit operation 為 !(((x+1)^x) + 1)
  2. 承 1.，由於 -1 為另一個符合上述條件的數字，需要額外判斷
  3. 承 2.，利用 !!(Tmax + 1) = !!Tmin = 1，!!(-1 + 1) = !! 0 = 0
  4. 將 1. & 3. 用 & 結合得到最終輸出
/*
 * 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) + 1) & (!!(x+1));
}

allOddBits

題目要求: 判斷是否有號整數 x 的所有奇數位元都為 1
題解:

  1. 先利用奇數位元遮罩 ~evenmask = 0xAAAAAAAA 將 x 所有的奇數位元取出
  2. 將 1. 的結果與偶數位元的遮罩 evenmask = 0x55555555 進行 XOR 操作
  3. 承 2. 若 x 所有奇數位元都是 1，則 2. 的結果一定為 0xFFFFFFFF
  4. 將 3. 的結果 + 1，如果 x 所有奇數位元都是 1 的話，會溢出變成 0
  5. 取 ! 得到最終結果
/* 
 * 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 evenmask = 0x55;
    evenmask = evenmask | evenmask << 4;
    evenmask = evenmask | evenmask << 8;
    evenmask = evenmask | evenmask << 16;
    return !(((x & ~evenmask) ^ evenmask) + 1);
}

negate

題目要求: 回傳 -x
題解: 利用二補數的特性，有號整數 x 的負數為 (not x) + 1

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

isAsciiDigit

題目要求: 判斷輸入有號整數是否為 ASCII code 的數字 0~9 (0x30 ~ 0x39)
題解:

  1. 先觀察 0x30 & 0x39，將兩數表達成二進位分別是 00110000 & 00111001，高位的 4 個 bit 都是 0011
  2. 對 0x30 及輸入往右偏移 4 位將低位捨去，再取 XOR確認輸入 x 的 4~7 位 bit 是否符合 0011，若不符合則該項為 1
    int h_bit_comp = (0x30>>4) ^ (x>>4);
  3. 接著我們再觀察 0x3a ~ 0x3f，其二進位低 4 位 bit 中，第 2 或第 3 位一定其中 1 個為 1，第 4 位一定為 1
  4. 承 3.

    • 將輸入右移 1 & 2後與 0x01(001) 取 | 確認 x 第 2 或第 3 位是否有 1
      int two_bit_comp = (x >> 1) & 0x01;
      int three_bit_comp = (x >> 2) & 0x01;

    • 將輸入右移 3 後與 0x01(0001) 取 & 確認 x 第 4 位是否為 1，若為 1 則該項為 1

      int forth_bit_comp = (x >> 3) & 0x01;

  5. 對第 4. 點兩個表達式的結果先單獨取 & ，當兩個條件都符合時，代表低 4 位大於 9
  6. 對第 2. 點及第 5. 點的結果個別取 ! 後再取 & 即為答案
/* 
 * 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 h_bit_comp = (0x30>>4) ^ (x>>4);
    int two_bit_comp = (x >> 1) & 0x01;
    int three_bit_comp = (x >> 2) & 0x01;
    int forth_bit_comp = (x >> 3) & 0x01;
    return !h_bit_comp & !((two_bit_comp | three_bit_comp) & forth_bit_comp);
}

這題覺得自己有點硬解了，所以上網查了其他人的實作，以下參考[連結] ，個人認為比較符合題目設定的目的，也解得漂亮許多:

  1. 設定一個 UpperBound，讓大於 0x39 的數加上它會溢出變成負數
  2. 設定一個 LowerBound，讓小於 0x30 的數加上會為負數
  3. 將輸入 x 分別加上 UpperBound & LowerBound，右移 31 bit 後與 sign 做 & 操作判斷數值的正負
  4. 當有任何一個數為負時，代表超出範圍，!(upperBound|lowerBound) 回傳 0; 反之回傳 1
int isAsciiDigit(int x) {
  int sign = 0x1<<31;
  int upperBound = ~(sign|0x39);
  int lowerBound = ~0x30;
  upperBound = sign&(upperBound+x)>>31;
  lowerBound = sign&(lowerBound+1+x)>>31;
  return !(upperBound|lowerBound);
}

conditional

題目要求: 以位元運算達到三元運算的功能
題解:

  1. 當 x != 0 時，要回傳 y；反之要回傳 z，因此解題的邏輯為 y & z 各利用一個表達式計算回傳值，符合條件的表達式回傳原數值 (y or z)；不符條件的表達式回傳 0，再用 Or 操作回傳非 0 項
  2. 對 y 來說， x != 0 時要回傳 y，反之回傳 0，所以要設計一個表達式，x != 0 時為 0xFFFFFFFF；x = 0 時為 0x00000000 –> ~((!x<<31)>>31)
  3. 對 z 來說， x != 0 時要回傳 0，反之回傳 z，所以要設計一個表達式，x != 0 時為 0x00000000；x = 0 時為 0xFFFFFFFF –> ((!x<<31)>>31)
  4. 將兩個表達式取 Or 得到最終答案
/* 
 * 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 cond_1 = ~((!x<<31)>>31)&y;
    int cond_2 = ((!x<<31)>>31)&z;
    return cond_1 | cond_2;
}

isLessOrEqual

題目要求: 利用位元運算完成 <= 的邏輯操作
題解:

  1. 一些基本的解題方向如下

    • x <= y 等同於判斷 x - y <= 0 是否為真
    • x - y 在沒有溢出的情況下可寫成 x + ~y + 1
    • 承 2.，在 x & y 同號的情況下不會溢出，僅在不同號時有機會發生
    • 因此若 x & y 不同號則改判斷是否 x > 0 & y < 0

  2. 當 x & y 同號時，我們判斷 x - y 為正或負值，另外需考慮 = 的情況，所以多了
    | !x_minus_y

    same_sign & ((x_minus_y >> 31) | !x_minus_y)

  3. 若 x & y 不同號則判斷是否 x > 0 & y < 0
    (!(~sign_x & 0x1) & !(sign_y & 0x1))

  4. 第 2. & 3. 點有一個條件為真代表 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 sign_x = x >> 31;
  int sign_y = y >> 31;
  int same_sign = !(sign_x ^ sign_y);
  int x_minus_y = x + (~y) + 1;
  return (same_sign & ((x_minus_y >> 31) | !x_minus_y)) | (!(~sign_x & 0x1) & !(sign_y & 0x1));
}

練習題 2.66 leftmost_one

額外練習習題 2.66，給定一個 32-bit 無號數，回傳最大 bit 為 1 的遮罩，如 0xFF00 -> 0x8000，若 x = 0 則回傳 0

  1. 先將最高位(含)以下的位元全部以 1 填滿，透過 mask |= mask >> 2^n 的操作，每次填滿 2 的冪次個 1，由 n = 0 -> n = 4 即可填滿 32 位元
  2. 填滿後先右移 1 個位元 (先加 1 有可能 overflow) 再加上 1
  3. 要考慮 x 為零的情況，所以要與自身做 & 運算
int leftmost_one(unsigned x) {
    unsigned mask = x;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    return x & ((mask >> 1) + 1);
}

int main() {
    printf("Left most bit of 0xff00 is 0x%x\n", leftmost_one(0xff00));
    printf("Left most bit of 0x6600 is 0x%x\n", leftmost_one(0x6600));
    printf("Left most bit of 0x0001 is 0x%x\n", leftmost_one(0x0001));
    printf("Left most bit of 0x0000 is 0x%x\n", leftmost_one(0x0000));
}

Left most bit of 0xff00 is 0x8000
Left most bit of 0x6600 is 0x4000
Left most bit of 0x0001 is 0x1
Left most bit of 0x0000 is 0x0

logicalNeg

題目要求: 以位元操作完成 ! 運算子，注意不得使用 !
題解:

  1. 本題重點要利用 ~0 + 1 = 0 的特性
  2. ~x + 1 在二補數系統下，等於 x 取負號，除了 0 以外，其他整數與其負數的最高位 bit 必定一個為 0 一個為 1
  3. 總和 1. & 2.，x = 0 時 (~x + 1) | x 最高位一定為 0；反之一定為 1
  4. 將最高位 bit 右移 31 之後取 ~ ， x = 0 時為 0xFFFFFFFF；反之為 0x00000000
  5. 將第 4. 點之結果與 0x1 取 & 將最低位 bit 抓出來即為回傳值
/* 
 * 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 + 1) | x) >> 31) & 0x1;
}

Reference

  1. Computer Systems: A Programmer's Perspective, 3/E (CS:APP3e)
Select a repo