2022q1 Homework2 (quiz 2)

contributed by < void110916 >

測驗 1

EXP1

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (EXP1);
}

(a >> 1) + (b >> 1) 在 a, b 均為偶數時滿足平均的結果，因此須考慮的 EXP1 為在 a, b 在均為奇數時的進位情況，因此 EXP1 為：

a & b & 1

EXP2, EXP3

uint32_t average(uint32_t a, uint32_t b)
{
    return (EXP2) + ((EXP3) >> 1);
}

當 a, b 在 \(n^{th}\) bit 同時為 1 時，會先經過進位( << 1)，再除以2( >> 1)，因此該動作會互相抵銷，則 EXP2 為:

a & b

而在其他情況時，因為不會進位，只會有除以2( >> 1)的動作，因此 EXP3 為:

a ^ b

以 Intel® 64 and IA-32 Architectures Optimization Reference Manual Table D-17. General Purpose Instructions 為例，MOV ADD 所需 Latency & Throughput 在同架構下均一樣，而 SHR Throughput 略多 0.5 至 1 倍，

測驗 2

#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((EXP4) & -(EXP5));
}

XOR 真值表：

X\Y	1	0
1	0	1
0	1	0

可以視為 XOR 表示該位元是否一樣，因此以下為 XOR 的特性：

• a^a=0：所有位元都一樣，所以均為0
• a^b=b^a：對調不影響不一樣的位元位置
• a^b^a=a^a^b=b

-1 以二進制表示為 0xffff_ffff ，為全開遮罩；0 以二進制表示為 0x0000_0000 ，為全關遮罩，因此 EXP4 為:

a ^ b

EXP5 為:

a < b

當 \(a < b\) 時， a ^ b 通過遮罩後的結果為 a ^ b ，因此回傳結果為 a ^ b ^ a = b
當 \(a \geq b\) 時， a ^ b 通過遮罩後的結果為 0 ，因此回傳結果為 a ^ 0 = a

測驗 3

COND:

v

RET:

u << shift

測驗 4

EXP6:

測驗 5

M:

_h

X:

0