2018q1 Homework3 (c-review)

contributed by < TingL7 >

第 4 週測驗題測驗 `1`

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

分析以下程式碼，推敲 FuncA, FuncB, FuncC 的作用，並且推測程式執行結果。

假設條件：

malloc 總是成功而且返回的記憶體空間可讀寫


































































#include <stdlib.h>
#include <stdio.h>
struct node { int data; struct node *next, *prev; };

void FuncA(struct node **start, int value) {
    if (!*start) {
        struct node *new_node = malloc(sizeof(struct node));
        new_node->data = value;
        new_node->next = new_node->prev = new_node;
        *start = new_node;
        return;
    }
    struct node *last = (*start)->prev;
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = *start;
    (*start)->prev = new_node;
    new_node->prev = last;
    last->next = new_node;
}

void FuncB(struct node **start, int value) {
    struct node *last = (*start)->prev;
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = *start;
    new_node->prev = last;
    last->next = (*start)->prev = new_node;
    *start = new_node;
}

void FuncC(struct node **start, int value1, int value2) {
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = value1;
    struct node *temp = *start;
    while (temp->data != value2)
        temp = temp->next;
    struct node *next = temp->next;
    temp->next = new_node;
    new_node->prev = temp;
    new_node->next = next;
    next->prev = new_node;
}

void display(struct node *start) {
    struct node *temp = start;
    printf("Traversal in forward direction \n");
    for (; temp->next != start; temp = temp->next)
	    printf("%d ", temp->data);
    printf("%d ", temp->data);
    printf("\nTraversal in reverse direction \n");
    struct node *last = start->prev;
    for (temp = last; temp->prev != last; temp = temp->prev)
	printf("%d ", temp->data);
    printf("%d ", temp->data);
    printf("\n");
}

int main() {
    struct node *start = NULL;
    FuncA(&start, 51); FuncB(&start, 48);
    FuncA(&start, 72); FuncA(&start, 86);
    FuncC(&start, 63, 51);
    display(start);
    return 0;
}

解題想法 & 思考

FuncA 的作用是
- 由開頭的 if 與第 14 行的可以發現，這個函式主要的功能是在建立新節點
- 新節點的 next 是 *start ， prev 是 last ，且 *start 沒有變動，因此新節點是安插在結尾。
- FuncA ：建立新節點，內容是 value，並安插在結尾
FuncB 的作用是
- 基本架構與 FuncA 差不多
- 關鍵在於第 29 行 *start = new_node; 改變了開頭為新節點，也就是說，新節點是安插在開頭
- FuncB :建立新節點，內容是 value，並安插在開頭
FuncC 的作用是
- 第 33~34 行在建立內容為 value1 的新節點
- 第 35~38 行在尋找內容為 value2 的節點
- 第 39~42 行在找到的節點後面插入新節點
- 因此， FuncC :找到節點內容為 value2 的節點，並在之後插入新節點，內容為 value1
在程式輸出中，訊息 Traversal in forward direction 後依序印出哪幾個數字呢？
- main 中，依序建立：
  - 51
  - 48 51
  - 48 51 72
  - 48 51 72 86
  - 48 51 63 72 86
- 由 start 不斷印出 next 的結果：
  48 51 63 72 86
在程式輸出中，訊息 Traversal in reverse direction 後依序印出哪幾個數字呢？
- 由 last 不斷印出 prev 的結果：
  86 72 63 51 48

第 4 週測驗題測驗 `2`

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

考慮以下程式碼，推敲程式作用並分析輸出。
假設條件：

malloc 總是成功而且返回的記憶體空間可讀寫
malloc() 得到的地址成嚴格單調遞增函數

#include <stdio.h>
#include <stdlib.h>

/* Link list node */
struct node { int data; struct node *next; };

int FuncX(struct node *head, int *data) {
    struct node *node;
    for (node = head->next; node && node != head; node = node->next)
        data++;
    return node - head;
}

struct node *node_new(int data) {
    struct node *temp = malloc(sizeof(struct node));
    temp->data = data; temp->next = NULL;
    return temp;
}

int main() {
    int count = 0;
    struct node *head = node_new(0);
    head->next = node_new(1);
    head->next->next = node_new(2);
    head->next->next->next = node_new(3);
    head->next->next->next->next = node_new(4);
    printf("K1 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
    head->next->next->next->next = head;
    printf("K2 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
    head->next->next->next->next->next = head->next;
    printf("K3 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
    head->next = head->next->next->next->next->next->next->next->next;
    printf("K4 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
    printf("K5 >> %d\n", head->next->data);
    printf("count >> %d\n", count);
    return 0;
}

解題想法 & 思考

FuncX 的作用是 (涵蓋程式執行行為的正確描述最多者)
- 走 circular linked list 所有節點
  - for loop 中有走訪過所有節點，但是沒有對節點做任何事
- 判斷是否為 circular linked list
  - 最後得到的 node 是 NULL 或 head ，回傳要兩個相減，明顯可以看出兩者的差異在於是否為 circular linked list
- 計算節點數量並更新
  - 改變的是 data 所紀錄的位址，也就是更新的是 count 的位址，並沒有計算節點數量
  - 如果要計算節點數量，程式需要修改
```
int FuncX(struct node *head, int *data) {
    struct node *node;
    for (node = head->next; node && node != head; node = node->next)
    (* data)++;
    return node - head;
}
```
- 回傳最後一個節點和開頭的地址距離 (offset)
  - 若為 circular 回傳的便不是最後一個節點與開頭的距離
- 若為 circular 則回傳非零值，其他回傳 0
- 若為 circular 則回傳 0，其他非零值
  - 若為 circular 則 node 為 head ，因此回傳 head - head 0
  - 若非 circular 則回傳最後一個節點和開頭的地址距離 (offset)
- 過程中計算走訪的節點總數
  - 改變的是 data 所紀錄的位址，也就是更新的是 count 的位址，並沒有計算走訪的節點數量
- 判斷是否為 circular linked list，若為 circular 則回傳 0，其他非零值

K1 >> 後面接的輸出為何

link list

非 circular linked list ，FuncX 回傳 0
K1 >> Yes

K2 >> 後面接的輸出為何

head->next->next->next->next = head;
head 0–––>1–––>2––->3 –––> head

link list

circular linked list ，FuncX 回傳 1
K2 >> No

K3 >> 後面接的輸出為何
- head->next->next->next->next->next = head->next;
  head 0––––>1–––>2–––>3–––>0 ––-> (head->next 1)
- link list
- circular linked list ，FuncX 回傳 1
- K3 >> No
K4 >> 後面接的輸出為何
- head->next = head->next->next->next->next->next->next->next->next;
  head 0 ––––-> head 0–––->1–––>2–––>3–––>0–––>1–––>2–––>3–––>0
- link list
- circular linked list ，FuncX 回傳 1
- K4 >> No
K5 >> 後面接的輸出為何
- head->next->data
  head 指向自己，因此裡面的值是 0
- K5 >> 0
count >> 後面接的輸出為何
- count 初始值為 0
- 每次使用 FuncX 時，會傳入 count 的位址作為參數 data ，並在 FuncX 中改變 data ，但改變後的 data 不會回傳，因此實際上 count 沒有任何改變
- count >> 0

第 5 週測驗題 (上) 測驗 `1`

考慮以下程式碼，推敲其作用 (選出最符合行為的描述)

uint8_t Func32(uint32_t x) {
    return x ? Func32(x >> 1) - 1 : 32;
}

將 Func32 改寫為以下功能等價的程式碼:

uint8_t FuncI(uint32_t x)
{
    if (!x) return 32;
    int n = 1;
    if (!(x >> 16)) { n += 16; x <<= 16; }
    if (!(x >> M1)) { n +=  8; x <<=  8; }
    if (!(x >> M2)) { n +=  4; x <<=  4; }
    if (!(x >> M3)) { n +=  2; x <<=  2; }
    n = n - (x >> 31);
    return n;
}

解題想法 & 思考

Func32 = ?
- 從上方的程式碼可以發現
  - 如果 x 不為 0 的話，每次就會向右移一位，且會傳值會減一，也就是 32 減去遞迴層數。
  - 遞迴層數為從高位算來第一個 1 的位置，因此 32 減去遞迴層數即為從高位到低位開頭 0 的數量
- 從下方的程式碼可以發現， Func32 再做的事主要有兩件
  - 如果 x 為 0 就回傳 32
  - if (!(x >> 16)) { n += 16; x <<= 16; }
    測試前 16 bit 是否為 0 ，是的話 n 加 16 ，表示 n 計算 0 的數量
  - n = n - (x >> 31);
    因為 n 的初始值為 1 ，假設至少有一個 0 ，所以這邊由最高位的值來決定 0 的數量
- 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 32
M1 = ?
- 測試前 8 位是否全為 0，經過 shift 之後，留下 8 位，因此要右移 32 - 8
- M1 = 24 = 0x18
M2 = ?
- 比照 M1 留下 4 位
- M2 = 32 - 4 = 28 = 0x1C
M3 = ?
- 比照 M1 留下 2 位
- M2 = 32 - 2 = 30 = 0x1E

參考資料

重新理解數值

第 5 週測驗題 (上) 測驗 `2`

延伸測驗 1，將 Func32 應用於以下程式碼，可輸入給定 64-bit 數值的 10 進位表達方式 (類似 printf 函式的 %d 格式)，補完程式碼並推測其作用。
















































































































#include <stdint.h>
#include <stdio.h>

union u_qword {
    struct {
        uint32_t low;
        uint32_t high;
    } dwords;
    uint64_t qword;
};

struct udiv_result {
    union u_qword q;
    union u_qword r;
};

static inline int Func64(uint64_t val)
{
    uint32_t lo = (uint32_t) val;
    uint32_t hi = (uint32_t) (val >> 32);
    return hi ? Func32(hi) : 32 + Func32(lo);
}

static int do_udiv32(uint32_t dividend,
                     uint32_t divisor,
                     struct udiv_result *res)
{
    /* Ensure dividend is always greater than or equal to the divisor. */
    uint32_t mask = Func32(divisor) - Func32(dividend);

    divisor <<= mask;  /* align divisor */
    mask = 1U << mask; /* align dividend */
    do {
        if (dividend >= divisor) {
            dividend -= divisor;
            res->q.dwords.low |= mask;
        }
        divisor >>= 1;
    } while ((P1) && dividend);
    res->r.dwords.low = dividend;
    return 0;
}

int udiv64(uint64_t dividend, uint64_t divisor, struct udiv_result *res)
{
    uint64_t mask;
    uint64_t bits;

    res->q.qword = res->r.qword = 0;
    if (divisor == 0) { /* division by 0 ? */
        res->q.qword = 0xffffffffffffffffull;
        return -1;
    }
    if (divisor == dividend) {
        res->q.qword = 1;
        return 0;
    }
    if (divisor > dividend) {
        res->r.qword = dividend;
        return 0;
    }
    /* only 32 bit operands that the preconditions are fulfilled. */
    if (!(divisor >> 32) && !(dividend >> 32))
        return do_udiv32((uint32_t) dividend, (uint32_t) divisor, res);

    bits = Func64(divisor) - Func64(dividend);
    divisor <<= bits; /* align divisor and dividend */
    mask = 1ULL << bits;
    /* division loop */
    do {
        if (dividend >= divisor) {
            dividend -= divisor;
            res->q.qword |= mask;
        }
        divisor >>= 1;
        mask >>= 1;
    } while ((P2) && dividend);

    res->r.qword = dividend;
    return 0;
}

int main()
{
    char digitbuff[20];
    char *pos = digitbuff + sizeof(digitbuff);
    union u_qword v;  /* current value */
    union u_qword nv; /* next value */
    struct udiv_result d;

    int64_t value = 0xCAFEBABE; /* Java classfile magic number */
    v.qword = (unsigned long long) value;
    while (v.dwords.high != 0) { /* process 64 bit value as long as needed */
        /* determine digits from right to left */
        udiv64(v.qword, 10, &d);
        *--pos = d.r.dwords.low + P3;
        v.qword = d.q.qword;
    }

    do { /* process 32 bit (or reduced 64 bit) value */
        nv.dwords.low = v.dwords.low / P4;
        *--pos = (v.dwords.low - (10 * nv.dwords.low)) + P5;
    } while ((v.dwords.low = nv.dwords.low) != 0);

    int len = digitbuff + sizeof(digitbuff) - pos;
    char *p = pos;
    while (len--)
        putchar(*p++);
    printf("\n");

    return 0;
}

解題想法 & 思考

Func64 的作用為？
- 已知 Func32的功能為計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 32
- Func64 中先將輸入的數字切成兩個 32bit 的 unsigned int，再測試 val 的前 32 是否全為 0 ，之後呼叫 Func32 得到開頭 0 的數量
- 基本上功能和 Func32 相似，只差在若 x 為 0x0 ，輸出64
- 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 64

P1 = ?



















static int do_udiv32(uint32_t dividend,
                 uint32_t divisor,
                 struct udiv_result *res)
{
    /* Ensure dividend is always greater than or equal to the divisor. */
    uint32_t mask = Func32(divisor) - Func32(dividend);

    divisor <<= mask;  /* align divisor */
    mask = 1U << mask; /* align dividend */
    do {
        if (dividend >= divisor) {
            dividend -= divisor;
            res->q.dwords.low |= mask;
        }
        divisor >>= 1;
    } while ((P1) && dividend);
    res->r.dwords.low = dividend;
    return 0;
}

do_udiv32() 的功能：做 32 位元的除法
一開始先利用 mask 對齊除數與被除數
- 1U： unsigned value 1
- 1ULL: unsigned long long value 1
do while loop 中變是在做長除法
- 被除數比除數大的話就可以除，不然就一到下一位
- 二進位除法不用考慮倍數，可以用減法做
- 有相減的話，表示該位元的結果為1，因此商 res 與 mask 做or
- mask 應該每做完一位，就向右移
由上述可知， P1 ＝ mask >>= 1

P2 = ?
- udiv64() 與 udiv32() 在除法的方面很像，最大的不同在於多了一個變數 bits ，此變數的功能在於計算商數的位數
- 第 70 行迴圈的條件該是計算到商的最後一位，也就是 bit 為 0
- 因此， P2 = bits--

P3 = ?






while (v.dwords.high != 0) { /* process 64 bit value as long as needed */
    /* determine digits from right to left */
    udiv64(v.qword, 10, &d);
    *--pos = d.r.dwords.low + P3;
    v.qword = d.q.qword;
}

進行完一次除法後，要將結果存到 pos ， pos 是最後要以 char 印出的結果，因此為了使結果符合 ASCII 要加上 '0' 也就是 0x30
P3 = 0x30

P4 = ? P5 = ?




 do { /* process 32 bit (or reduced 64 bit) value */
    nv.dwords.low = v.dwords.low / P4;
    *--pos = (v.dwords.low - (10 * nv.dwords.low)) + P5;
} while ((v.dwords.low = nv.dwords.low) != 0);

要計算十進位，因此，迴圈內每次都除 10
P4 = 10
pos 儲存結果，如同 P3 要加上 '0'
P5 = 0x30

延伸題目：將 10 進位輸出改為 16 進位

除以 10 的地方改為除以 16

輸出 10 以上要以 ABCDEF 代替，在 ASCII 中相當於加 0x37












while (v.dwords.high != 0) { /* process 64 bit value as long as needed */
    /* determine digits from right to left */
    udiv64(v.qword, 16, &d);
    *--pos = d.r.dwords.low + ((d.r.dwords.low > 9) ? 0x37 : 0x30);
    v.qword = d.q.qword;
}

do { /* process 32 bit (or reduced 64 bit) value */
    nv.dwords.low = v.dwords.low / 16;
    *--pos = (v.dwords.low - (16 * nv.dwords.low)) + (((v.dwords.low - (16 * nv.dwords.low)) > 9) ? 0x37 : 0x30);

} while ((v.dwords.low = nv.dwords.low) != 0);

延伸題目：上方程式碼的 `0xCAFEBABE` 為 magic number，舉出在真實世界中程式的實際作用 (提示: 如 malloc)

Java class file 的前 4 byte 為 magic number CAFEBABE 主要做用在於辨認 file 是否是能被接受的 class file
參考c語言里malloc的最優實現方式是什麼？， malloc() 中也會設置 magic number，主要是因為避免 free 到沒有 malloc 的位址，藉由 magic number 設置與否就可以檢查

第 5 週測驗題 (中) 測驗 `1`

已知在 x86_64 架構，以下程式碼的執行輸出是 jserv++C:

#include <stdio.h>
int main() {
    puts((char *) &(double []){ 3823806048287157.0, 96 });
}

考慮以下程式碼，假設 puts 函式總是可正確運作，那麼程式輸出為何？

#include <stdio.h>
double m[] = { 3823806048287157.0, 96 };
void gen() {
    if (m[1]--) {
        m[0] *= 2;
        gen();
    } else
        puts((char *) m);
}
int main() { gen(); return 0; }

解題想法 & 思考

double 與 char 的轉換
- 3823806048287157.0 轉換成 double 的表示式為 0x432b2b767265736a
- 考慮到 x86_64 架構使用 little endianness ，實際上儲存的數字為 0x6a736572762b2b43
- char 大小為 1byte ，因此 8byte 的 double 可以切成 8 個 char
  根據 ASCII轉換：
  
  6a 73 65 72 76 2b 2b 43
  
  j s e r v + + C
解讀程式
- gen() 的功能為改變 m[0] ，使輸出的字串改變。實際上做的是 m[0] * 2⁹⁶
  double 要乘上 2⁹⁶ ，實際上是在 exp 部份加上 96 ，也就是 0x432 + 0x60 = 0x492
  有改變的地方只有 0x43 變成 0x49 ，也就是 C 變成 I
- 因此，答案為 jserv++I

6a	73	65	72	76	2b	2b	43
j	s	e	r	v	+	+	C

延伸題目：修改程式，允許輸出你的 GitHub 帳號名稱

GitHub 帳號名稱：TingL7
ASCII: 0x54696e674c37
符合 double 有 8byte ，補上兩個空字元： 0x54696e674c370000
little-endian: 0x0000374c676e6954
十進位： 3.003983e-310

程式碼

#include <stdio.h>
int main() {
    puts((char *) &(double []){ 3.003983e-310, 96 });
}

結果：
```
յugL7
```
結果與預期不符，推測是換算成十進位的精度不足， double 的有效位數是16位，精度應取到那

修正：

#include <stdio.h>
int main() {
    puts((char *) &(double []){ 3.0039829763669880E-310, 96 });
}

結果
```
TingL7
```

延伸題目：承上，修改 gen() 函式，透過特定的轉換，讓 m[] 的內容變為你的英文姓氏 (last name)，程式碼應該越短越好，而且不得以字串的形式存在於原始程式碼

英文姓氏： Lai
- ASCII: 0x4c6169
- 符合 double 有 8byte ，補上 5 個空字元： 0x4c61690000000000
- little endian: 0x000000000069614c
- 十進位： 3.4121102345210668E-317

目標：0x0000374c676e6954 轉換成 0x000000000069614c

差異

TingL7 00000000 00000000 00110111 01001100 01100111 01101110 01101001 01010100
Lai    00000000 00000000 00000000 00000000 00000000 01101001 01100001 01001110
diff   00000000 00000000 00110111 01001100 01100111 00000111 00001000 00011010

~~進行 bitwise 的操作？~~
exp部份都是 0 , 不用變動
兩者相差 3.0039826351559646E-310

程式碼

#include <stdio.h>
double m[] = { 3.0039829763669880E-310, 3.0039826351559646E-310 };
void gen() {
    m[0] = m[0] - m[1];
    puts((char *) m);
}
int main() { gen(); return 0; }

延伸題目：如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？

修改輸入，不需要轉換
- TingL7
  - little-endian: 0x0000374c676e6954 = 3.0039829763669880E-310
  - big-endian: 0x54696e674c370000 = 4.3456679652866146e+98
- Lai
  - little-endian: 0x000000000069614c = 3.4121102345210668E-317
  - big-endian: 0x4c61690000000000 = 8.7428257608182613e+59
- 差異
  - exp: 0x546 - 0x4c6 = 0x080 = 128
  - frac: 0x4c696e674c370000 - 0x4c61690000000000 = 4.0279445985412390e+59

程式碼

#include <stdio.h>
int main() {
    puts((char *) &(double []){ 4.3456679652866146e+98, 96 });
}

#include <stdio.h>
double m[] = { 4.3456679652866146e+98, 128, 4.0279445985412390e+59 };
void gen() {
    if (m[1]--) {
    m[0] *= 2;
    gen();
} else {
    m[0] = m[0] - m[2];
    puts((char *) m);
}
int main() { gen(); return 0; }

第 5 週測驗題 (下)

考慮某款 MIPS 實作，其 data path 如下:

上圖紅色的 1, 2, 3 對 MIPS 做了對應的修改，請考慮以下狀況，分別解釋對應的程式碼是否能運作。

測驗 `1`

Q11: 做了 1: Stuck at 0 left of cut 的修改，sw $s1, 0($s2) 能否運作？
- 可以
- sw
- sw 不需要 WB，因此做了 1: Stuck at 0 left of cut 也不影響運作
data memory 要 load 或 store 都需要兩個值， address 及 data ，為什麼圖片上的 data memory 只有一個輸入？
Q12: 承上，下方程式能否運作？
```
lw $s1, 0($s2)
add $s1,$2,$3
```
- 不可以
- lw
- add
- lw 和 add 都需要將結果存回暫存器($s1) ，因此做了這個修改後會無法運作

測驗 `2`

Q21: 做了 2: Cut here 的修改後，以下程式能否運作？
```
add $s1, $s1, $s1
add $s1, $t0, $t1
```
- 可以
- add
- 這條線的作用在於，當 exe 階段的指令會用到 mem 階段的值，才需要先丟回去運算
- e.g.
```
add $t1, $s1, $s1
sub $s1, $t0, $t1
```
  $t1 在 sub exe 階段時， add 的 $t1 還沒寫回 reg ，因此 $t1 的值是不正確的，修正方法便是將在 mem 階段的結果丟給 sub ，也就是 2: Cut here 修改前可以做到的事

測驗 `3`

Q31: 做了 3: Cut here 的修改後，以下程式能否運作？ (exit 為某個副程式)
```
cmp:
    xor $t1, $s2, $s1
    slt $t2, $zero, $t1
    sll $t2, 2
    add $ra, $ra, $t2
    jr  $ra

entry:
    addi $s2, $zero, 2
    addi $s1, $zero, 2
    jal  cmp
    j    exit
```
- 不可以
- j(參考圖片)
- 是否切掉 3 的線都無法做 jump ，因為在本題圖片的架構中，能夠改變 PC 的只有下一道指令 (PC+4) 以及 branch 的結果
參考其他同學的答案都是可以的，如果可以運作，在題目的 MIPS 實做是如何運作呢？
Q32: 承上，以下程式能否運作？
```
addi $s2, $zero, 2
addi $s1, $zero, 2
beq $s2, $s1, exit
```
- 不可以
- beq
- beq 所儲存的 exit 是指該指令與 exit 的距離，所以必須加上 PC 才會指向正確的地方，因此如果切斷 3 會無法運作

第 1 週測驗題測驗 `5`

考慮以下整數乘法的實作程式碼:

int mul(int n, int m)
{ 
    int ret = 0;
    for (int c = 0; m; c++, m /= 2)
        if (!(m % 2 - 1)) OP
    return ret;
}

上述 OP 對應到下方哪個程式敘述呢？

解題想法 & 思考

利用直式乘法的概念實作
e.g.

1011 * 101 = 110111 (11 * 5 = 55)

    1011
*    101
---------
    1011
   0000
+ 1011
---------
  110111

變數
- ret : 乘法結果
- c : 乘數位數
- n : 被乘數
- m : 乘數
for loop
- if 判斷目前 m 的最後一個 bit 為 1 或 0
- 為 1 的話執行 OP
- 之後捨棄最後一個 bit 並且提升一個位數
- 因此， OP 的內容必須包括
  - 移到適當位數的被乘數加上累積下來的結果
OP = ret += n << c;

第 3 週測驗題測驗 `2`

考慮到下方函式 shift_right_arith 和 shift_right_logical 分別表示算術右移和邏輯右移，請嘗試補完程式碼。可由 sizeof(int) * 8 得知整數型態 int 的位元數 w，而位移量 k 的有效範圍在 0 到 w - 1。

#include <stdio.h>
int shift_right_arith(int x, int k) {
    int xsrl = (unsigned) x >> k;
    int w = sizeof(int) << P1;
    int mask = (int) -1 << (P2);
    if (x < 0)
        return xsrl P3 mask;
    return xsrl;
}

unsigned shift_right_logical(unsigned x, int k) {
    unsigned xsra = (int) x >> k;
    int w = sizeof(int) << P4;
    int mask = (int) -1 << (P5);
    return xsra P6 P7;
}

解題想法 & 思考

P1 = ? P4 = ?
- sizeof() 回傳的單位是 byte 但是 w 是 int 的位元數，因此要乘上 8
- * 8 等價於 `<< 3
- 因此， P1 = P4 = 3
P2 = ? P5 = ?
- mask 是為了做 x 為負數時使用的遮罩
- 參考Arithmetic Shift Operations、C/C++ 負整數的 shift中，提到C/C++ 沒有定義 signed shift 的行為，也可以透過 compiler 加參數來改變結果。 right shift ，在 Visual studio 及 gcc 中都是在前面補上 sign bit
- mask 的目的為 shift 後，將前面缺漏的 bit 補 1
- 也就是，把前（總 bit 扣掉位移量）這麼多 bit 補1
- 因此， P2 = P5 = w - k
P3 = ? (為某種 operation)
- 前（w - k）個 bit 必定是 1， mask 符合條件， xsrl 這部份全為 0
- 後 w 個 bit 看位移結果 xsrl， mask 這部份全為 0
- 因此，使用 | 便能夠合成兩個變數取出需要的部份
- P3 = |
P6 = ? (為某種 operation) P7 = ?
- logical 無論正負前面都要補 0
- 因此，return xsra & ~mask

2018q1 Homework3 (c-review)

第 4 週測驗題 測驗 1

解題想法 & 思考

第 4 週測驗題 測驗 2

解題想法 & 思考

第 5 週測驗題 (上) 測驗 1

解題想法 & 思考

參考資料

第 5 週測驗題 (上) 測驗 2

解題想法 & 思考

延伸題目： 將 10 進位輸出改為 16 進位

延伸題目： 上方程式碼的 0xCAFEBABE 為 magic number，舉出在真實世界中程式的實際作用 (提示: 如 malloc)

第 5 週測驗題 (中) 測驗 1

解題想法 & 思考

延伸題目：修改程式，允許輸出你的 GitHub 帳號名稱

延伸題目：承上，修改 gen() 函式，透過特定的轉換，讓 m[] 的內容變為你的英文姓氏 (last name)，程式碼應該越短越好，而且不得以字串的形式存在於原始程式碼

延伸題目：如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？

第 5 週測驗題 (下)

測驗 1

測驗 2

測驗 3

第 1 週測驗題 測驗 5

解題想法 & 思考

第 3 週測驗題 測驗 2

解題想法 & 思考

第 4 週測驗題測驗 `1`

第 4 週測驗題測驗 `2`

第 5 週測驗題 (上) 測驗 `1`

第 5 週測驗題 (上) 測驗 `2`

延伸題目：將 10 進位輸出改為 16 進位

延伸題目：上方程式碼的 `0xCAFEBABE` 為 magic number，舉出在真實世界中程式的實際作用 (提示: 如 malloc)

第 5 週測驗題 (中) 測驗 `1`

測驗 `1`

測驗 `2`

測驗 `3`

第 1 週測驗題測驗 `5`

第 3 週測驗題測驗 `2`