2024q1 Homework5 (assessment)

contributed by < Terry7Wei7 >

測驗題改進與提問

???
紀錄問題和回顧

閱讀〈因為自動飲料機而延畢的那一年〉

一個專案的可行性以及背後的風險是需要謹慎評估的，再來是團隊的執行力，大家對這專案的熱忱以及向心力是否足夠，看完這篇文章後感觸頗深，回想到大學畢業專題時曾經也想做出一個好專案，受到 LINE 官方帳號記帳雞的啟發我也想開發一款關於熱量控制的 linebot，結合健康飲食商家以及健身房的推廣，可惜實力不夠只完成一些基本功能就畢業了，後續無人維護整個專案就消失了 xdd，回到文章內容，我覺得在製作飲料的過程茶湯用水霧式噴灑跟冰塊糖漿結合的方式蠻酷的，但不確定這樣有沒有把糖漿跟茶湯都結合再一起，感覺糖漿應該會黏在冰塊上，畢竟雪克機的目的是要充分混和糖漿跟茶湯，再來是冰塊機這一題，既然茶湯都是要更換的狀態下，也選擇了沒有製冰功能的分冰機，通常在製冰機製冰出來後會是一整片的，需要去敲他使其分散，所以通常也不會有到 3 顆以上連在一起的，但在於保溫效果，購買那台機器算是非常合理的，畢竟研發的人力和時間也是一個成本，雖然文章後續沒有一個 Happy Ending，但我想這肯定是值得的，付出的努力心力是不會白費的，過程也累積的各種經驗以及實力，且要善用身邊的資源，不要一人埋頭苦幹。

研讀第 1 到第 6 週「課程教材」和 CS:APP 3/e

5/9 討論

bitwise
IEEE 754
複習bitwise篇章，找到整數用的解法
((x >> 31) ^ x) - (x >> 31)
複習IEEE 754單精度浮點數表示法
浮點數的實際值，等於符號位（sign bit）乘以指數偏移值（exponent bias）再乘以分數值（fraction）。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

透過轉換工具，我們可以看到0.15625和-0.15625 只差在符號位元
https://www.toolhelper.cn/Digit/FractionConvert

題目是浮點數取絕對值，use bitwise, no branch

float float_abs(float x)
{
    // 將浮點數 x 轉換為32位整數
    unsigned int n = *(unsigned int*)&x;
    //符號位元不管是1或0都會輸出0
    unsigned int mask = 0x7FFFFFFF;
    
    unsigned int abs_n = n & mask;
    
    // 將 abs_n 轉回浮點數
    return *((float*)&abs_n);
}

改為更精簡的程式碼

TODO: https://csapp.cs.cmu.edu/3e/labs.html Data Lab
TODO: 參照 https://hackmd.io/@Chang-Chia-Chi/CSAPP_DataLab 並提出其他做法

誠實面對自己

CS:APP DATALAB

bitXor(x,y)

A	B	$Y = A \oplus B$
0	0	0
0	1	1
1	0	1
1	1	0

Y = A \cdot \overset{―}{B} + \overset{―}{A} \cdot B

第摩根定理互換

Y = \overset{―}{\overset{―}{A \cdot \overset{―}{B}} \cdot \overset{―}{\overset{―}{A} \cdot B}}

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
//找出X,Y中僅有一個為一的位元，假設X=1010,Y=1011
//~(x&~y) == 1010&0100 = 0000,取反=1111,
//~(~x&y) == 0101&1011 = 0001,取反=1110,
//~(~(x&~y)&~(~x&y)) == 1111&1110 = 1110,取反=0001

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

tmin()

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

int 類型是32位，即4byte。2補數最小值就是符號位為1，其餘全為0。
對 0x1 進行位移運算。

istmax

/*
 * 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) {
    int y = x + 1;              // y = x + 1 = 1000
    x = x + y;                  // x = x + y = 1111
    x = ~x;                     // 0000
    y = !y;                     // 0 ,y is 0 only if x was Tmax
    x = x | y;                  // 0 ,combine both conditions
    return !x;                  // return 1 if x is Tmax, 0 otherwise
}

以4bits 2補數表示法演示

十進制	2補數
7	0111
6	0110
5	0101
4	0100
3	0011
2	0010
1	0001
0	0000
-1	1111
-2	1110
-3	1101
-4	1100
-5	1011
-6	1010
-7	1001
-8	1000

可以看出0111(7)為最大值，1000(-8)為最小值
利用0111 + 1 會溢出成為 1000的特性

如果是最大值0111與最小值1000 相加，會等於1111(-1)

allOddBits

/* 
 * 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) {
    // 0xAAAAAAAA is a constant where all odd-numbered bits are 1
    int mask = 0xAAAAAAAA;

    // Perform bitwise AND with the mask and compare with the mask
    return !((x & mask) ^ mask);
}

判斷是否有號數 x 的所有奇數位元都為 1
先利用奇數位元遮罩 0xAAAAAAAA 做 & 運算，留下奇數位元，將偶數位元變0
接著做位元運算xor，如果奇數位元都是1的話會與奇數位元遮罩相等，所以會是0
如果不是0，代表奇數位元不全都是1

negate(x)

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

2補數，對x取反向+1
ex:0001(1)取反=1110，加1= 1111(-1)
1111(-1)取反=0000，加1=0001(1)

isAsciiDigit(x)

/* 
 * 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 mask = 0x30; //filter out ASCII codes for characters '0' to 'f'
  int high_mask = 0x39;
  int num = !((mask>>4) ^ (x>>4)); // if x = '0' to 'f' return 0
  int dis = !((x) +(~ (high_mask))); // if x < 'a' return 0
  return !(num & dis);
}

原本想先篩選掉 x 不是0x3開頭的，ru, 接著透過x減去9，看是否>0
但第二段還沒想出怎麼做

看了其他人的解法
設定一個 UpperBound，讓大於 0x39 的數加上它會溢出變成負數
設定一個 LowerBound，讓小於 0x30 的數加上會為負數
將輸入 x 分別加上 UpperBound & LowerBound，右移 31 bit 後與 sign 做 & 操作判斷數值的正負
當有任何一個數為負時，代表超出範圍，!(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(x, y, z)

/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(3,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
  x = !!x;
  x = ~x+1;
  return (x&y)|(~x&z);
}

題意為若X為真(即非0)，則輸出Y，反之輸出Z
這邊用兩層反向邏輯判斷X，如果輸入是非0，最後x會是0xFFFFFFFFE + 1 = 0xFFFFFFFFF，如果輸入是0，最後x會是0xFFFFFFFFF + 1 = 溢位0x00000000，再跟Y,Z做位元運算

isLessOrEqual(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) {
   // Compute the sign bits of x and y
    int signX = x >> 31 & 1;
    int signY = y >> 31 & 1;

    // Case 1: x is negative, y is positive (x <= y is true)
    int xNegYPos = signX & ~signY;

    // Case 2: Both have the same sign
    int sameSign = !(signX ^ signY);

    // Calculate y - x
    int diff = y + (~x + 1);  
    int diffSign = diff >> 31 & 1;

    // If sameSign is 1, we check the sign of the difference
    int lessOrEqualSameSign = sameSign & ~diffSign;

    // Combine the cases
    return xNegYPos | lessOrEqualSameSign;
}

這題要比較x是否小於等於y
我的想法是先比較x,y的符號位元
若x是負數signx為1,y是正數signy為0，result = 1
若符號位元相同，則再進行減法比較，若y-x為正，result = 1

logicalNeg(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;
}

透過與自身2補述相加會產生溢位得到0的特性完成
除了0和最小數的補數是自身，但一樣能透過篩選符號位元完成

howManyBits(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) {
  int b16,b8,b4,b2,b1,b0;
  int sign=x>>31;
  x = (sign&~x)|(~sign&x);
    
  b16 = !!(x>>16)<<4;
  x = x>>b16;
  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;
}

b16 = !!(x >> 16) << 4; 檢查高16位是否有1，如果有，b16 為16。
x = x >> b16; 如果 b16 為16，則右移16位，否則不變。
重複這個過程對 b8、b4、b2、b1 進行檢查和位移。
b0 = x; 獲取剩餘的最低位
將所有計算出的位數加起來，並加上1表示符號位，得到最終的位數。

floatScale2(f)

/* 
 * 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 sign = uf >> 0x80000000;
    unsigned exp = (uf & 0x7F800000) >> 23;
    unsigned frac = uf & 0x007FFFFF;
    // 如果指數位為255（即全為1），則是無窮大或NaN，直接返回uf
    if (exp == 255) {
        return uf;
    }
    if (exp == 0) {
        // 將尾數左移一位，相當於乘以2
        frac <<= 1;
        // 保留符號位，並重組結果返回
        return sign | frac;
    }
    exp += 1;
    // 如果指數加1後變成255，說明達到無窮大，返回無窮大
    if (exp == 255) {
        return sign | 0x7F800000;
    }
    // 保留符號位和新的指數位、尾數位
    return sign | (exp << 23) | frac;
}

先提取出指數位的部分，觀察後可發現指數位加1，就等於乘法*2
並且透過指數位篩選掉0, NaN,無窮大,無窮小

floatFloat2Int(f)

/* 
 * 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 sign = uf >> 31;
    int exp = ((uf >> 23) & 0xFF) - 127;
    unsigned frac = (uf & 0x7FFFFF) | 0x800000; 
    if ((uf & 0x7F800000) == 0x7F800000) {
        return 0x80000000u;
    }
    if (exp < 0) {
        return 0;
    }
    if (exp > 31) {
        return 0x80000000u;
    }
    if (exp > 23) {
        frac <<= (exp - 23);
    } else {
        frac >>= (23 - exp);
    }
    if (sign) {
        frac = -frac;
    }
    return frac;
}

過濾出符號位、指數位、尾數位，再去做特殊況處理
如果指數位全為1，返回 0x80000000u。
若全為0直接返回0。

單精度浮點數的偏置值是127，因此實際指數為 exp - 127。

如果實際指數小於0，則浮點數的小數部分在整數為0
若大於31，則超出32位有號整數的範圍，返回 0x80000000u。

尾數部分加上隱含的1位（即 1.xxxxx 變成 1xxxxx），如果指數大於等於23，則將尾數左移，否則右移。
如果符號位为1，取負值。

floatPower2(x)

/* 
 * 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: 31 
 *   Rating: 4
 */
unsigned floatPower2(int x) {

    int exp = x + 127;
    if (exp <= 0) {
        return 0;
    }
    if (exp >= 255) {
        return 0x7f800000;
    }
    return exp << 23;
}

單精度浮點數的指數偏置值是 127。
2 的 x 次方的指數表示為 x + 127。

如果 x + 127 小於 0，則結果太小，返回 0。
如果 x + 127 大於 255，則結果太大，返回正無窮大（+INF）。

指數位設置為 x + 127。
尾數位設置為 0，因為 2 的 x 次方的尾數部分為 1.0（隱含位）。

簡述想投入的專案

參照 2023 年期末專題，簡述你想投入的專案 (亦可建立新專案)，至少選出 (或訂出) 二個。

### 打造 Linux 虛擬攝影機裝置驅動程式因實驗室專案有接觸到生態監測，且個人想要增加多角度攝影機畫面，想透過這題目來學習並完善
高效網頁伺服器

~~網頁伺服器也是我想學習的部分，目前接觸 nodejs dashboard 來呈現我感測器的畫面，希望透過這題目來學習並完善~~