課前測驗參考解答: 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 程式來實作:

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語言來實現乘法運算如下：

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

全加器

首先實做全加器，函式參數增加低位進位信號:

// 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，此時就利用遞迴的方式實現:

// 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加速，這是第一個版本。

// 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倍！

// 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;
}

減法則如題目提示，利用二補數進行加法。

// 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 的運算

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