2018q1 Homework2 (assessment)

contributed by <chasingfar>

W1Q2

給定 B 為 2 的某次方 (power of 2)，那麼是否 A % B 等價於 (A & (B - 1))?
答：(a) 是

A %

2^{n}

相當於取 A 的右側數來前 n 位數

2^{n} - 1

的二進位表示為 n 個 1 ，如

2^{3} - 1 = 7 = (111)_{2}

跟前 n 個 1 做位元且運算即是篩出前 n 位數
故 (A %

2^{n}

) 等價於 (A & (

2^{n} - 1

))

W1Q3

在 C 程式中，表達式 1 << 2 + 3 << 4 求值後為何？
答：(a) 512

相當於 (1 << (2 + 3) )<< 4

6.5 Expressions

3 The grouping of operators and operands is indicated by the syntax.85) Except as specified later, side effects and value computations of subexpressions are unsequenced.86)

由上可知規格書的順序即優先序，而加法在前面

6.5.6 Additive operators

6.5.7 Bitwise shift operators

而位移運算的 Syntax 的遞迴關係可知左側先執行，(a<<b<<c => (a<<b)<<c)

6.5.7 Bitwise shift operators

Syntax
1

shift-expression:
       additive-expression
       shift-expression << additive-expression
       shift-expression >> additive-expression

W1Q5

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

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) ret += n << c;

這題跟我之前自己做的乘法器有87%像
所以上兩個去年的投影片

m % 2 跟 m/=2 為分別取出各個位數，即找出中圖右側籃框的數字
!(m % 2 - 1) 與 m%2==1 相同
n << c 與 c++ 為逐次位移，起到與直式乘法的位移相同的作用

因為自動飲料機而延畢的那一年心得