還記得我們在 為什麼電腦是只有 0 與 1 的世界？世界上只有10種人，一種是懂二進位的 一文中和大家介紹的基礎邏輯電路畫法嗎？今天就要來和大家分享如何用 C 語言實作一個二進位加法器噢！
加法器原理複習(half adder/full adder)
另外我們又介紹了把這些邏輯電路組合起來進行運算的方法，首先是「半加法器」——能由一個 EXOR 和一個 AND 電路做出來。（註：Exclusive-OR gate 可簡稱 XOR gate 或 EXOR gate）
而一個全加法器，即由兩個半加法器做出來的。
今天就讓我們來進一步使用 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」原理，如果有更好的方式也歡迎大家與我分享噢！
