# 課前測驗參考解答: Q2 ( contributed by 吳柏儒, 安正, riversnow ) - [ ] 在 C 程式中,使用遞迴和 bit-wise operator 來實作乘法運算,請參考以下提示: * 加法器是用於執行加法的電路元件,通常由 AND 閘、OR 閘 和 XOR 閘構成 - 也可用加法器實作減法,只要將減數轉成二補數,並注意溢位即可 * 半加器:將兩個一位二進位數相加 (input: A, B) (output: S, C) ![](https://i.imgur.com/HRN0c1D.png) * 全加器:將兩個一位二進位數相加 (input: A, B, Cin) (output: S, Cout) ![](https://i.imgur.com/cypKq1H.png) * 波紋進位加法器:使用多個一位全加器構成 N 位加法器 ![](https://i.imgur.com/X5fQcYn.png) * 半加器可用以下 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; } ```