# 2018q1 Homework2 (assessment)

contributed by <`nashi5566`>

## 第1週

## 第2週

## 第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;
}

### I. 想法

1. 先搞懂 logical shift right 和 arithmetic shift right 的差異

* logical shift [1]
bitwise operation ，直接將 digits 右移或左移，MSB 或 LSB 補 0

    >>> 3 >> 1  # 0011 shift right 1 bit
    >>> 1       # 0001

* arithmetic shift
bitwise operation ，而且為了不改變原來數值的正負，將 digits 右移或左移之後，sign bit 維持原來的數值

    >>> -5 >> 1  # 1111 1011 arithmetic shift right 1 bit
    >>> -3       # 1111 1101

2. 然而在 C 裡面 shift right operator 指的是對 unsigned integer 進行 logical shift right ，許多 C 語言文章都有提及不要對 negative operand 作 shift operation (或者一說不要對 negative operand 做 bitwise operation) [2]，探究他的原因就是==因為 C standard 僅規範 unsigned 的狀況，而對 unsigned integer 而言， arithmetic 或 logical shift 結果是一樣的 (沒有正負號的差別)==，而對 positive integer 也是一樣

因此作 negative operand 的 shift operation 則是一個 undefined behavior

> The standard integer promotions are first performed on the operands, each of which has an integer type. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.
> [name=INT34-C]

* 然後寫個程式實驗一下對負整數 shift right 1 bit 會有什麼結果，可以看到的是這個結果是 arithmetic shift 的結果而不是 logical shift

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

int main(){
    char get[60];
    int number;
    while(fgets(get, 60, stdin)){
        number = atoi(get);

        printf("The result is : %d", number >> 1);
    }

    return 0;
}


3. 因此從題目的第二個程式碼可以得知，一個 byte = 8 bits， `sizeof(int)` = 4 bytes ， w = 32 bit ，也符合我們在計組學到的資料的基本單位是一個 word = 32 bits，因此要對其 shift left 3 digits (* $2^{3}$)
4. 而 k 是 shift 的 offset ，而 w-k 代表的意義是在 logical shift 之後數值保持不變的位數
5. 向左 shift w-k 位之後， mask 則會從 LSB 開始變成 w-k 個 0，和直接用 shift operation 做的 xsrl 相比，數值保持不變的 bits 數值相反，因此經過 xor 運算之後即可得到真正的 logical shift right result

[1] [logical shift](https://henrybear327.gitbooks.io/gitbook_tutorial/content/Assembly/ARM-Instruction/LSL-LSR/index.html)
[2] [Rule 04 - Integer : INT34-C](https://wiki.sei.cmu.edu/confluence/display/c/INT34-C.+Do+not+shift+an+expression+by+a+negative+number+of+bits+or+by+greater+than+or+equal+to+the+number+of+bits+that+exist+in+the+operand)