# 課前測驗參考解答: Q2
( contributed by 吳柏儒, 安正, riversnow )
- [ ] 在 C 程式中，使用遞迴和 bit-wise operator 來實作乘法運算，請參考以下提示:
* 加法器是用於執行加法的電路元件，通常由 AND 閘、OR 閘 和 XOR 閘構成
- 也可用加法器實作減法，只要將減數轉成二補數，並注意溢位即可
* 半加器：將兩個一位二進位數相加 (input: A, B) (output: S, C)
* 全加器：將兩個一位二進位數相加 (input: A, B, Cin) (output: S, Cout)
* 波紋進位加法器：使用多個一位全加器構成 N 位加法器
* 半加器可用以下 C 程式來實作:
```c
uint32_t half_add(uint32_t a, uint32_t b) {
if (b == 0) return a;
uint32_t sum = a ^ b; /* 相加但不進位 */
uint32_t carry = (a & b) << 1; /* 進位但不相加 */
return half_add(sum, carry);
}
```
## 思路
回顧國中數學教的乘法運算：
```
123
x 456
-------
738 -> 123x6
615 -> 123x5
+ 492 -> 123x4
-------
56088
```
此法是否能套用於二進位形式？
```
1101 -> 13 in decimal
x 1001 -> 9 in decimal
---------
1101 -> 1101 & 1
0000 -> 1101 & 0 shift 1 position to the left
0000 -> 1101 & 0 shift 2 position to the left
+ 1101 -> 1101 & 1 shift 3 position to the left
---------
1110101 -> 117 in decimal = 13 x 9 !
```
可以結合位移運算、AND運算與半加器來實現乘法運算：
重複上面例子，假設A = 0b1101, B = 0b1001，重新思考如下：
```
1101 -> A
x 1001 -> B
---------
1101 -> A shift 0 & B first bit
0000 -> A shift 1 & B second bit
0000 -> A shift 2 & B third bit
+ 1101 -> A shift 3 & B fourth bit
---------
1110101
```
若與A做AND運算的bit為0時，則無須做加法，因此可以化簡為：
```
1101 -> A
x 1001 -> B
---------
1101 -> A shift 0 & B first bit
+ 1101 -> A shift 3 & B fourth bit
---------
1110101
```
以C語言來實現乘法運算如下：
```C
uint32_t mul(uint32_t a, uint32_t b) {
uint32_t product = 0;
while(b != 0) {
if(b & 0x1) { //if this bit is not 0, than continue the addition
product = add(product, a); //use the half adder
}
a = a << 1;
b = b >> 1;
}
return product;
}
```
## 全加器
首先實做全加器，函式參數增加低位進位信號:
```clike=
// full_add
uint32_t full_add(uint32_t a, uint32_t b, uint32_t c) {
if (c == 0 && b == 0) return a;
uint32_t sum = a ^ b; /* 相加但不進位 */
uint32_t carry = ((a & b) | (c & sum)) << 1; /* 進位但不相加 */
sum = sum ^ c; /* 相加但不進位 */
return full_add(sum, carry, 0);
}
```
## 波紋進位加法器
接著實做，波紋進位加法器，原本打算取bit後相加，這需要額外的空間和運算，因此就直接在變數中用mask的方式移動，進行加法運運算，接著把進位信號加到下一位並移動mask，此時就利用遞迴的方式實現:
```clike=
// ripple_add
uint32_t ripple_add(uint32_t a, uint32_t b, uint32_t c, uint32_t m) {
if (m == 0) return a;
uint32_t sum = (a ^ b) & m; /* 相加但不進位 */
uint32_t carry = ((a & b) & m | (c & sum) & m) << 1; /* 進位但不相加 */
sum = sum ^ c; /* 相加但不進位 */
a = (sum & m) ? (a | sum) : (a & ~m);
return ripple_add(a, b, carry, m << 1); /* 往下一位移動 */
}
```
## 乘法器 1
乘法器的實做，則是簡單的利用加法器，把被乘數相加到乘數的次數為止，有更快速的方式可以利用shift加速，這是第一個版本。
```clike=
// multiply
uint32_t mult(uint32_t a, uint32_t b) {
uint32_t sum = a;
if (a == 0 | b == 0) return 0;
while (b = del(b, 1), b > 0) {
sum = add(sum, a);
if (a > sum) /* Overflow!!! */
return -1;
}
return sum;
}
```
## 乘法器 2
這個版本比循環加法有效率，採用shift的方式移動被乘數的位元到高位進行相加。
做了簡單的效能測式，比純用加法快超多~
mult calc in **8.2** seconds
mult shift calc in **0.0077** seconds
效能提升100倍！
```clike=
// multiply2
uint32_t mult_shift_imp(uint32_t a, uint32_t b, uint32_t m, uint32_t sum) {
if (m == 0) {
return sum;
}
if (a == 0 | b == 0) return sum;
if (b & m) {
sum = add(sum, a);
if (a > sum) return -1;
}
mult_shift_imp(a << 1, b, m << 1, sum);
}
uint32_t mult_shift(uint32_t a, uint32_t b) {
uint32_t sum = 0;
sum = mult_shift_imp(a, b, 0x1, sum);
return sum;
}
```
減法則如題目提示，利用二補數進行加法。
```clike=
// del
uint32_t del(uint32_t a, uint32_t b) {
uint32_t ret = ripple_add(a, ~b + 1, 0, 1);
if (ret > a) return -1; // overflowed!!
}
```
## 思考 overflow
以下的程式實作了 x * y 的運算
```Clike
#include <stdio.h>
#include <stdbool.h>
int add(int result, int x);
int main(int argc, char const *argv[])
{
int x, y;
int result = 0;
bool isfalse = false;
bool isoverflow = false;
scanf("%d%d", &x, &y);
if ((x < 0) || (y < 0)) {
if ((x < 0) && (y < 0)) {
isfalse = false;
x = (-x);
y = (-y);
} else {
isfalse = true;
if (x < 0)
x = (-x);
if (y < 0)
y = (-y);
}
}
if (x == 0 || y == 0) { //如果x或y為0，可以直接說結果是0
result = 0;
} else {
/*
* 想法是每當y為奇數(LSB為1)時，進行一次加法運算
* 為何對的原因是，每當LSB為0時，我們雖然不執行加法，
* 但我們將x*2，讓每一個二進位下>的y的每一個1所對應到的都是一個加法
* 加的值是:(2^n)*x，n是從y的LSB數來的第幾位數，
* 因此我們可以說這樣的運算是正確的
*/
while (y != 0) {
if (y & 1) {
result = add(result, x);
if (result == -1) {
printf("overflow\n");
isoverflow = true;
break;
}
}
y >>= 1; // y向右推
if ((y != 0) && (x & 0x80000000)) {
printf("overflow\n");
result = -1;
isoverflow = true;
break;
}
x <<= 1; // x*2
}
}
if (isfalse) {
result = (-result);
}
if (isoverflow) {
return 0;
} else {
printf("result=%d", result);
}
return 0;
}
```
Sign in with Wallet
Connect another wallet