算術演算子を使わずに2進数の加算を実装する.

はじめに

ふとこんなことを思った.”ビット演算子で論理ゲートみたいなものを作れるから,それらを組み合わあせて半加算器と全加算器も作れて,さらにこれらを組み合わせれば2進数の加算器がつくれるのでは?”

実装する

論理ゲートを作る

ビット演算子などの算術演算子以外の演算子を用いて論理ゲートを作る.
以下a,bは0もしくは1のint型の変数とする.

AND,OR,EXOR

AND,OR,EXORはそれぞれビット演算子&,|,^を用いて実装する.

int and(int a, int b){
    int s = a & b;
    return s;
}
int or(int a, int b){
    int s = a | b;
    return s;
}
int exor(int a,int b){
    int s=a^b;
    return s;
}
NOT

NOTは三項演算子を用いて実装する.

int not(int a){
    a==0? (a=1) : (a=0); 
    return a;
}
NAND,NOR

おまけ的に,これまで作ったAND,OR,NOTを用いてNAND,NORをつくる.

int nand(int a, int b){
    int s = not(a&b);
    return s;
}
int nor(int a, int b){
    int s = not(a|b);
    return s;
}

半加算器と全加算器を作る

半加算器(Half Adder)

a,bを入力すると,出力sと桁上げ出力cを返す半加算器を作る.
返したい値が2つあるので関数は戻り値をvoidとし,参照渡しを用いる.

void HA(int a,int b,int *s,int *c){
    int or1, and1,not1,and2;
    or1 = or(a,b);
    and1 = and(a,b);
    not1 = not(and1);
    and2 = and(or1,not1);

    *s = and2;
    *c = and1; 
}

a,b,さらに前の桁の桁上がり出力pre_cを入力として,出力sと桁上げ出力cを返す全加算器を作る.
半加算器と同様にして,返したい値が2つあるので関数は戻り値をvoidとし,参照渡しを用いる.

全加算器(Full Adder)
void FA(int a,int b,int pre_c,int *s,int *c){
    int HAs1,HAc1,HAs2,HAc2,or1;
    HA(a,b,&HAs1,&HAc1);
    HA(HAs1,pre_c,&HAs2,&HAc2);
    or1 = or(HAc1,HAc2);
    *s = HAs2;
    *c = or1;
}

2進数の加算器を作る

足し合わせる2進数をA,Bとして,A,Bのそれぞれの値を桁ごとに配列a,bに保存する.
A,Bの1桁目をそれぞれ半加算器に入力して,出力と桁上がり出力をそれぞれ配列c,sに保存する.
2桁目以降はA,Bのその桁の値と1つ前の桁の繰り上がり出力を全加算器に入力して,出力と桁上がり出力をそれぞれ配列c,sに保存する.
これを最後の桁まで繰り返す.

include <stdio.h>

int and(int a,int b);
int or(int a,int b);
int not(int a);
void HA(int a,int b,int *s,int *c);
void FA(int a,int b,int pre_c,int *s,int *c);

int main(void){
    int a[5],b[5]; //足し合わせる2つの2進数A,Bをそれぞれ桁ごとに格納する配列
    int c[5],s[6]; //それぞれの桁の出力と桁上がり出力

    //scanf()で2進数Aの値を指定する
    printf("a[0]=");
    scanf("%d",&a[0]);
    printf("a[1]=");
    scanf("%d",&a[1]);
    printf("a[2]=");
    scanf("%d",&a[2]);
    printf("a[3]=");
    scanf("%d",&a[3]);
    printf("a[4]=");
    scanf("%d",&a[4]);

    printf("\n");

    //指定したAの値を表示
    printf("A = ");
    printf("%d",a[4]);
    printf("%d",a[3]);
    printf("%d",a[2]);
    printf("%d",a[1]);
    printf("%d",a[0]);
    printf("\n");

    printf("\n");


    //scanf()で2進数Bの値を指定する
    printf("b[0]=");
    scanf("%d",&b[0]);
    printf("b[1]=");
    scanf("%d",&b[1]);
    printf("b[2]=");
    scanf("%d",&b[2]);
    printf("b[3]=");
    scanf("%d",&b[3]);
    printf("b[4]=");
    scanf("%d",&b[4]);
    
    printf("\n");

    //指定したBの値を表示
    printf("B = ");
    printf("%d",b[4]);
    printf("%d",b[3]);
    printf("%d",b[2]);
    printf("%d",b[1]);
    printf("%d",b[0]);
    printf("\n");

    printf("\n");

    //1桁目を半加算器で計算する
    HA(a[0],b[0],&s[0],&c[0]);
    printf("HA : s0 = %d , c0 = %d\n",s[0],c[0]);

    //2桁目以降を全加算器で計算する
    FA(a[1],b[1],c[0],&s[1],&c[1]);
    printf("FA : s%d = %d , c%d = %d\n",1,s[1],1,c[1]);
    FA(a[2],b[2],c[1],&s[2],&c[2]);
    printf("FA : s%d = %d , c%d = %d\n",2,s[2],2,c[2]);
    FA(a[3],b[3],c[2],&s[3],&c[3]);
    printf("FA : s%d = %d , c%d = %d\n",3,s[3],3,c[3]);
    FA(a[4],b[4],c[3],&s[4],&c[4]);
    printf("FA : s%d = %d , c%d = %d\n",4,s[4],4,c[4]);

    //A+Bの値を表示
    printf("\nA+B = ");

    printf("%d",s[4]);
    printf("%d",s[3]);
    printf("%d",s[2]);
    printf("%d",s[1]);
    printf("%d",s[0]);
    printf("\n");

    return 0;
}

int and(int a, int b){
    int s = a&b;
    return s;
}

int or(int a, int b){
    int s = a|b;
    return s;
}

int not(int a){
    a==0? (a=1) : (a=0); 
    return a;
}

void HA(int a,int b,int *s,int *c){
    int or1, and1,not1,and2;
    or1 = or(a,b);
    and1 = and(a,b);
    not1 = not(and1);
    and2 = and(or1,not1);

    *s = and2;
    *c = and1; 
}

void FA(int a,int b,int pre_c,int *s,int *c){
    int HAs1,HAc1,HAs2,HAc2,or1;
    HA(a,b,&HAs1,&HAc1);
    HA(HAs1,pre_c,&HAs2,&HAc2);
    or1 = or(HAc1,HAc2);
    *s = HAs2;
    *c = or1;
}

出力結果の1例を以下に示す.

a[0]=1
a[1]=1
a[2]=1
a[3]=0
a[4]=0

A = 00111

b[0]=1
b[1]=0
b[2]=1
b[3]=0
b[4]=0

B = 00101

HA : s0 = 0 , c0 = 1
FA : s1 = 0 , c1 = 1
FA : s2 = 1 , c2 = 1
FA : s3 = 1 , c3 = 0
FA : s4 = 0 , c4 = 0

A+B = 01100

算術演算子を使わずに2進数の加算を実装することができた.