The Hardware / Software Interface Lab1

華盛頓大學(xué)的 CSE 351 課程 The Hardware / Software Interface https://courses.cs.washington.edu/courses/cse351/17wi/schedule.html ，該課程原來(lái)有一個(gè) Coursera 版本，后來(lái) Coursera 平臺(tái)大升級(jí)，導(dǎo)致這門課在 Coursera 看不了。不過(guò)還是可以華盛頓大學(xué)的網(wǎng)站上找得到對(duì)應(yīng)的課程視頻，地址在這里 https://courses.cs.washington.edu/courses/cse351/17wi/videos.html。
該課程的動(dòng)手操作實(shí)驗(yàn)移植于計(jì)算機(jī)經(jīng)典書籍《深入理解計(jì)算機(jī)系統(tǒng)》的實(shí)驗(yàn)。這篇文章是第一個(gè)實(shí)驗(yàn) Lab1 的解答。

規(guī)則限制

簡(jiǎn)單介紹一下代碼實(shí)現(xiàn)的規(guī)則

  1. 不允許使用 if，else，以及其他條件語(yǔ)句
  2. 不能使用宏定義
  3. 不能添加額外的函數(shù)
  4. 不能調(diào)用其他函數(shù)
  5. 能使用的操作符會(huì)在每題題目中說(shuō)明，除此之外其他的都不能使用
  6. 不能使用數(shù)據(jù)類型轉(zhuǎn)換
  7. 不能使用 int 之外的其他數(shù)據(jù)類型
  8. 使用課程實(shí)驗(yàn)提供的虛擬機(jī)

注意：文章中提到的 “位置” 都是從 int 的二進(jìn)制角度來(lái)描述的,位置是 int 的二進(jìn)制表示中某個(gè) bit 的所在排列位置。

第一題

題目：

/* 
 * bitAnd - x&y using only ~ and | 
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |Xor
 *   Max ops: 8
 *   Rating: 1
 */
int bitAnd(int x, int y) {
  return 2;
}

解題思路：

  1. x & y 的操作結(jié)果是，x 和 y 中所有對(duì)應(yīng)位置的 bit 同時(shí)為 1 的時(shí)候結(jié)果為 1，否則結(jié)果為 0
  2. 使用 ~(x) | (~y) 操作將 x 和 y 中同時(shí)為 1 的 bit 的值置為 0，其他 bit 位置的值置為 1
  3. 執(zhí)行 ((x)|(~y)) ，在 2 的結(jié)果上取反，得到解題結(jié)果

解題方案：

int bitAnd(int x, int y) {
  return ~((~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 2;
}

解題思路：

  1. (x&y) 操作將 x 和 y 中 對(duì)應(yīng)位置的 bit 值同時(shí)為 1 的 位置置
    1 保留下來(lái)，其余位置置 0
  2. (x)&(y) 操作將 x 和 y 中 對(duì)應(yīng)位置的 bit 值中同時(shí)為 0 的位置置 1 保留下來(lái),其余位置置0
  3. (~(x&y)) 把 1 步驟的結(jié)果做 ~ 操作，將 x 和 y 中 對(duì)應(yīng)位置的 bit 值中同時(shí)為 1 的位置置0，其余位置置1，保留下來(lái)
  4. (((x)&(~y))) 把 2 步驟的結(jié)果做 ~ 操作，將 x 和 y 中 對(duì)應(yīng)位置的 bit 值中同時(shí)為 0 的位置置 0 ,其余位置置 1，保留下來(lái)
  5. ((x&y))&(((x)&(y))) 將 3 步驟和 4 步驟的結(jié)果做 & 操作，將 x 和 y 中對(duì)應(yīng)位置同時(shí)為 0 和同時(shí)為 1 的位置置為 0 ，其他位置置為 1，得到解題結(jié)果

解題方案：

int bitXor(int x, int y) {
  return (~(x&y))&(~((~x)&(~y)));
}

第三題

題目：

/* 
 * thirdBits - return word with every third bit (starting from the LSB) set to 1
 * and the rest set to 0
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 1
 */
int thirdBits(void) {
    return 2;
}

解題思路：
題目是要讓我們構(gòu)造一個(gè)這樣的數(shù)據(jù) 0100 1001 0010 0100 1001 0010 0100 1001 。

  1. 我們?cè)O(shè)定一個(gè)初始數(shù)據(jù) 0100 1001，轉(zhuǎn)成 16 進(jìn)制表示 int x = 0x49
  2. 在 1 步驟上做 x << 9 操作得到數(shù)據(jù) 1001 0010 0000 0000，int y = x << 9
  3. 在 1 步驟和 2 步驟的基礎(chǔ)上執(zhí)行 (x + y) << 18 操作得到數(shù)據(jù) 0100 1001 0010 0100
  4. 在 3 步驟的基礎(chǔ)上執(zhí)行 ((x + y) << 18) + (x + y) 操作得到數(shù)據(jù) 0100 1001 0010 0100 1001 0010 0100 1001，得到解題結(jié)果

解題方案：

int thirdBits(void) {
    int x = 0x49;
    int y = x << 9;
    return ((x + y) << 18) + (x + y);
}

第四題

題目：

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

解題思路：
這個(gè)題目是要判斷一個(gè)數(shù)字能否被 n 個(gè) bit 位表示

  1. 假定一個(gè)數(shù)字可以被 n 個(gè) bit 位表示，那么也可以認(rèn)為左邊的 (32-n) 位是沒(méi)用的位置，所以做 ((x << (32 - n)) 操作
  2. 在 1 步驟的基礎(chǔ)上做 ((x << (32 - n)) >> (32 - n)) 操作，假定一個(gè)數(shù)字可以被 n 個(gè) bit 位表示，那么在經(jīng)過(guò)這個(gè)操作之后，這個(gè)數(shù)字還是不變的
  3. 在 2 步驟的基礎(chǔ)上做 !(((x << (32 - n)) >> (32 - n)) ^ x ) 操作，判斷 ((x << (32 - n)) >> (32 - n)) 和 x 是否是同一個(gè)數(shù)字，得到解題結(jié)果

解題方案:

int fitsBits(int x, int n) {
  return (!(((x << (32 - n)) >> (32 - n)) ^ x ));
}

第五題

題目：

/* 
 * sign - return 1 if positive, 0 if zero, and -1 if negative
 *  Examples: sign(130) = 1
 *            sign(-23) = -1
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 10
 *  Rating: 2
 */
int sign(int x) {
  return 2;
}

解題思路：

  1. 取出 x 的符號(hào)位 (x >> 31) x為負(fù)數(shù)結(jié)果為 0x11111111 x為正數(shù)結(jié)果為 0x00000000 x為零結(jié)果為 0x00000000
  2. 取出 -x 的符號(hào)位 ((~x +1) >> 31) x為負(fù)數(shù)結(jié)果為 0x00000000 x為正數(shù)結(jié)果為 0x11111111 x為零結(jié)果為 0x00000000
  3. 在 2 步驟 的基礎(chǔ)上進(jìn)行 & 0x01 操作 (((~x +1) >> 31) & 0x01)) ，取出最后一位 x為負(fù)數(shù)結(jié)果為 0 x為正數(shù)結(jié)果為 1 x為零結(jié)果為 0
  4. 在 1步驟 和 3步驟 的基礎(chǔ)上做 | 操作，x為負(fù)數(shù)結(jié)果為 0x11111111 ，x為正數(shù)結(jié)果為 0x00000001 , x為零結(jié)果為 0x00000000，得到解題結(jié)果

解題方案:

int sign(int x) {
  return ((x >> 31) | (((~x +1) >> 31) & 0x01));
}

第六題

題目：

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

解題思路：
1.一個(gè) byte 等于 8（2的3次方) 個(gè) bit，將 n 乘以 8 也就是 n = n << 3 得到想要取出的 byte 在 x 的二進(jìn)制表示的開始位置

  1. x = x >> n，將想要取出的 byte 移動(dòng)到最低 8 位
  2. (x & 0xff)，將 x 與 0xff 進(jìn)行 & 操作，取出最低 8 位，得到解題結(jié)果

解題方案:

int getByte(int x, int n) {
    n = n << 3;
    x = x >> n; 
    return (x & 0xff);
}

第七題

題目：

/* 
 * logicalShift - shift x to the right by n, using a logical shift
 *   Can assume that 0 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3 
 */
int logicalShift(int x, int n) {
    return 2;
}

解題思路：

  1. 實(shí)現(xiàn)邏輯左移操作，需要一個(gè) mask ，該 mask 可以將左到右的 n 個(gè)位置清零
  2. (0x1 << 31) 的操作結(jié)果為 0x10000000
  3. (0x1 << 31) >> n 將 2 步驟的結(jié)果右移 n 位 實(shí)現(xiàn)從左邊到右邊的 n+1 位為 1，其余位置為 0 的效果
  4. ((0x1 << 31) >> n << 1) 將 3 步驟的結(jié)果左移 1 位，實(shí)現(xiàn)從左邊到右邊的 n 位為 1，其余位置為 0 的效果
  5. (~((0x1 << 31) >> n << 1)) 的操作，實(shí)現(xiàn)從左邊到右邊的 n 位為 0，其余位置為 1 的效果
  6. (x >> n) & (~((0x1 << 31) >> n << 1)) 實(shí)現(xiàn)邏輯左移的效果，得到解題答案

解題方案:

int logicalShift(int x, int n) {
    return (x >> n) & (~((0x1 << 31) >> n << 1));
}

第八題

題目：

 * addOK - Determine if can compute x+y without overflow
 *   Example: addOK(0x80000000,0x80000000) = 0,
 *            addOK(0x80000000,0x70000000) = 1, 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int addOK(int x, int y) {
    return 2;
}

解題思路：

  1. overflow 是指數(shù)據(jù)的表示超出了整數(shù)的表示范圍，兩個(gè)正整數(shù)或者兩個(gè)負(fù)整數(shù)相加就有可能超過(guò)這個(gè)整型變量所能表示的范圍,有可能產(chǎn)生 overflow
  2. x > 0, y > 0, (x + y) < 0 ，x < 0, y < 0, (x + y) > 0 這 2 種情況都是 overflow
  3. int a = x >> 31，取出 x 的符號(hào)位
  4. int b = y >> 31, 取出 y 的符號(hào)位
  5. int c = (x + y) >> 31，取出 x + y 的符號(hào)位
  6. !((~(a ^ b)) && (a ^ c))，判斷 x,y,x+y 符號(hào)是否一致，得到解題答案

解題方案:

int addOK(int x, int y) {
    int a = x >> 31;
    int b = y >> 31;
    int c = (x + y) >> 31;
    return !((~(a ^ b)) && (a ^ c));
}

第九題

題目：

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

解題思路：

  1. 在 c 語(yǔ)言中， 0 是 False，其他非 0 的都是 True
  2. 在 int 中，只有 x = 0 的時(shí)候才存在 -x 和 +x 相等的情況
  3. (((~x +1) | x) >> 31) 可以區(qū)分出 x 是否是 0，若是 x = 0 則結(jié)果 0，若是 x != 0 則結(jié)果為 -1
  4. 在 3 步驟的基礎(chǔ)上執(zhí)行 (((~x +1) | x) >> 31) +1，得到解題結(jié)果

解題方案:

int bang(int x) {
    return (((~x +1) | x) >> 31) +1;
}

第十題

題目：

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

解題思路：

  1. 解題的核心點(diǎn)在于如何利用 x 構(gòu)造 False，如何利用 x 構(gòu)造 True
  2. int a =(((!x) << 31) >> 31),利用結(jié)果來(lái)表示 x 等于 False 的情況
  3. 在 2步驟的基礎(chǔ)上，int b = (~a)， 利用結(jié)果來(lái)表示 x 等于 True 的情況
  4. (b&y) + (a&z)，得到解題答案

解題方案:

int conditional(int x, int y, int z) {
    int a =(((!x) << 31) >> 31);
    int b = (~a);
  return (b&y) + (a&z);
}

第十一題

題目：

/*
 * 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: 20
 *   Rating: 4
 */
int isPower2(int x) {
    return 2;
}

解題思路：

  1. 2的次冪數(shù)對(duì)應(yīng)二進(jìn)制表示應(yīng)該只有 1 位 1，其余位置全部都是0，重點(diǎn)是如何判斷一個(gè)數(shù)的二進(jìn)制表示只有一個(gè) 1,然后再處理好負(fù)數(shù)和 0 的情況
  2. x 的二進(jìn)制表示只有一個(gè) 1 那么會(huì)有這個(gè)規(guī)律 x &（x-1） = 0x0，由于題目不能使用 - 號(hào)，所以轉(zhuǎn)換成 !(x & (x + (~0) ))
  3. 在 2 步驟的基礎(chǔ)上，!(x &（x-1)) 的結(jié)果可以判斷 x 是否為 2 的冪
  4. (!(x >> 31)) 可以判斷 x 是否為負(fù)數(shù)
  5. 在 4 步驟的基礎(chǔ)上執(zhí)行 (!(x >> 31)) & (~(!x))) 可以判斷 x 是否為 0
  6. ( !! ( x ^ 0x0 ) ) 可以判斷 x 是否 0
  7. (!(x & (x + (~0))) & (!(x >> 31)) & (!!(x ^ 0x0))) ，將 x 是否為 2 的冪，判斷 x 是否為負(fù)數(shù) 和 x 是否 0 ，3個(gè)判斷進(jìn)行 & 操作，得到解題答案

解題方案:

int isPower2(int x) {
    return (!(x & (x + (~0))) & (!(x >> 31)) & (!!(x ^ 0x0)));
}

參考

  1. 華盛頓大學(xué)的 CSE 351 課程 The Hardware / Software Interface
    https://courses.cs.washington.edu/courses/cse351/17wi/videos.html
最后編輯于 ：
?著作權(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)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

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

  • 一、實(shí)驗(yàn)?zāi)康?學(xué)習(xí)使用 weka 中的常用分類器，完成數(shù)據(jù)分類任務(wù)。 二、實(shí)驗(yàn)內(nèi)容 了解 weka 中 explo...
    yigoh閱讀 8,832評(píng)論 5贊 4
  • TF API數(shù)學(xué)計(jì)算tf...... ：math（1）剛開始先給一個(gè)運(yùn)行實(shí)例。tf是基于圖（Graph）的計(jì)算系統(tǒng)...
    MachineLP閱讀 4,033評(píng)論 0贊 1
  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問(wèn)題, 分享了一些自己做題目的經(jīng)驗(yàn)。 張土汪：刷leetcod...
    土汪閱讀 12,890評(píng)論 0贊 33
  • 有這樣一種需求，給文字畫上刪除線，從簡(jiǎn)單點(diǎn)來(lái)講，一句代碼的事情: 但是這貨有缺陷，就是只同文字的長(zhǎng)度相關(guān)聯(lián)，文字多...
    Axiba閱讀 727評(píng)論 0贊 0
  • 八六年十二月十八日下午，曹奇來(lái)找我：“車間里反映，最近來(lái)的薄膜片基中個(gè)別卷又有些厚薄不勻的現(xiàn)象?！蔽伊⒓唇涌冢骸安?..
    陳家老爺爺閱讀 331評(píng)論 0贊 0

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