以 C 語言實作二進位加法 (Binary Addition)

還記得我們在 為什麼電腦是只有 0 與 1 的世界？世界上只有10種人，一種是懂二進位的 一文中和大家介紹的基礎邏輯電路畫法嗎？今天就要來和大家分享如何用 C 語言實作一個二進位加法器噢！

 

加法器原理複習(half adder/full adder)

另外我們又介紹了把這些邏輯電路組合起來進行運算的方法，首先是「半加法器」——能由一個 EXOR 和一個 AND 電路做出來。（註：Exclusive-OR gate 可簡稱 XOR gate 或 EXOR gate）

也就是說，把 EXOR 電路和 AND 電路組合在一起，便能進行一位元（一個位數）的加法！一位數加法的意思是 0+0, 0+1, 1+0, 1+1。

所以這就是具備兩個輸入（A、B）和兩個輸出（Sum加總 和 Carry進位）的半加法器！

而一個全加法器，即由兩個半加法器做出來的。

今天就讓我們來進一步使用 C++ 實作二進位加法的程式吧！

以下是一個半加法器 (Half Adder)：

sum = a xor b //XOR電路

carry = ab //AND電路

接下來，將兩個半加法器合起來，成為一個全加法器：

sum = a xor b xor c //c為carry

carry = ab+bc+ca

位元運算 (bitwise operation)

複習完二進位加法的原理後，接下來我們可以把要計算的二進位數字存入陣列 (array) 中，使用，使用 C 語言中提供的位元運算 (bitwise operation) 符號進行運算：

• & 代表 AND

• | 代表 OR

•  ^ 代表 XOR

• ! 代表 NOT

先為大家示範一下 bitwise operation 的用法：

#include <stdio.h>
 
int main(void) {
    printf("AND運算：\n");
    printf("0 AND 0\t = %d\n", 0 & 0);
    printf("0 AND 1\t = %d\n", 0 & 1);
    printf("1 AND 0\t = %d\n", 1 & 0);
    printf("1 AND 1\t = %d\n\n", 1 & 1);
 
    printf("OR運算：\n");
    printf("0 OR 0\t = %d\n", 0 | 0);
    printf("0 OR 1\t = %d\n", 0 | 1);
    printf("1 OR 0\t = %d\n", 1 | 0);
    printf("1 OR 1\t = %d\n\n", 1 | 1);
 
    printf("XOR運算：\n");
    printf("0 XOR 0\t = %d\n", 0 ^ 0);
    printf("0 XOR 1\t = %d\n", 0 ^ 1);
    printf("1 XOR 0\t = %d\n", 1 ^ 0);
    printf("1 XOR 1\t = %d\n\n", 1 ^ 1);
 
    printf("NOT運算：\n");
    printf("NOT 0\t = %d\n", !0);
    printf("NOT 1\t = %d\n\n", !1);
 
    return 0;
}

 

二進位加法 Binary Addition

利用上面的分析與 bitwise operation，就可以實作出一個二進位加法器啦！

虛擬碼

Binary_Addition(Array: A, B){
  sum = Array[A.length+1]
  carry = 0;
  for i = A.length to 1 do 
    sum[i+1] = ((A[i] ^ B[i]) ^ carry);
    carry = ((A[i] & B[i]) | (A[i] & carry)) | (B[i] & carry);
  sum[1] = carry;
  return sum;
}

 

完整程式碼與運行結果

#include <stdio.h>
 
int binary_add(int A[], int B[], int n){
  int sum[n+1];
  int i;
  int carry = 0;
	for(i = n-1; i >= 0 ; i--){
		sum[i+1] = ((A[i] ^ B[i]) ^ carry);
		carry = ((A[i] & B[i]) | (A[i] & carry)) | (B[i] & carry);
	}
  sum[0] = carry;
  for(i = 0; i <= n; i++){
    printf("%d ", sum[i]);
  }
}
 
int main(){
  int n;
  scanf("%d", &n);
  int i, j;
  int A[n];
  for(i = 0; i < n; i++){
    scanf("%d ", &A[i]);
  }
  int B[n];
  for(j = 0; j < n; j++){
    scanf("%d ", &B[j]);
  }
  binary_add(A, B, n);
  return 0;
}

也可以不用 bitwise operation、改用其他方式，來達到 XOR 和 AND 電路的效果：

虛擬碼

Binary_Addition(Array: A, B){
  sum = Array[A.length+1]
  carry = 0;
  for i = A.length to 1 do 
    sum[i+1] = (A[i] + B[i] + carry) % 2; //可達到XOR的效果 
    carry = (A[i] + B[i] + carry) / 2; //可達到AND的效果
  sum[1] = carry;
  return sum;
}

 

完整程式碼與運行結果

#include <stdio.h>

int binary_add(int A[], int B[], int n){
  int sum[n+1];
  int i;
  int carry = 0;
  for(i = n-1; i >= 0; i--){
    sum[i+1] = (A[i] + B[i] + carry) % 2;
    carry = (A[i] + B[i] + carry) / 2;
  }
  sum[0] = carry;
  for(i = 0; i < n+1; i++){
    printf("%d ", sum[i]);
  }
}

int main(){
  int n;
  scanf("%d", &n);
  int i, j;
  int A[n];
  for(i = 0; i < n; i++){
    scanf("%d ", &A[i]);
  }
  int B[n];
  for(j = 0; j < n; j++){
    scanf("%d ", &B[j]);
  }
  binary_add(A, B, n);
  return 0;
}

實作二進位加法的方式還有很多，應用「AND + XOR」原理，如果有更好的方式也歡迎大家與我分享噢！