論理演算(ビット演算)を使って四則演算を行う方法を解説

論理演算で四則演算を行う方法の解説ページのアイキャッチ

このページでは「+」「-」「*」「/」の算術演算子を使わずに四則演算を行う方法の解説とそのC言語プログラムの紹介を行います。

通常プログラム中で足し算・引き算・掛け算・割り算を行う場合はこれらの算術演算子を使用して計算すると思いますが、実は算術演算子を使わなくても、論理演算(ビット演算)を駆使することで計算ができてしまいます。

論理演算や論理回路についても学べますので、是非読んで見てください。

論理演算・ビット演算の基本的な使い方については下記で解説していますので、これらに自信がない方は先に下記ページを読んでいただけると、このページがより分かりやすくなると思います。

ビット演算解説ページのアイキャッチC言語のビット演算(論理演算)について解説

条件

扱う数字は符号ありの 32bit の整数とします。つまり int 型同士の演算を行う足し算・引き算・掛け算・割り算を実現することを目指します。

また、基本的に下記の論理演算のみを用いて足し算・引き算・掛け算・割り算を実現します。

  • AND演算(&)
  • OR演算(|)
  • XOR演算(^)
  • NOT演算(~)
  • 左シフト演算(<<)
  • 右シフト演算(>>)

条件分岐と繰り返し文は使用します。ただし繰り返し文で良く使う “i++” みたいなインクリメント処理は “足し算” ですので、「+」を使用せずに足し算を行う関数を作成し、その関数を用いてのみそのインクリメント処理を行うようにしています。

足し算

まずは足し算を「+」なしに行う方法について解説していきます。はっきり言ってこの足し算が一番難しいです。考え方の基本となるのは2進数の足し算です。

2進数1桁の足し算

まずは2進数の1桁の足し算について考えてみましょう。足し算を行う2つの値を “a” と “b” 、計算結果の1桁目を “a” 、桁上がりで発生する2桁目を “c” とすると、2進数2進数の1桁同士の足し算は下記の表(真理値表)で表現することができます。

abcs
0000
0101
1001
1110

c に注目すると、これは a と b のAND演算の結果と同じです。つまり桁上がり結果は下記により計算することが可能です。

c = a & b;

また s に注目すると、これは a と b のXOR演算の結果と同じです。つまり計算結果の1桁目は下記により計算することが可能です。

s = a ^ b;

論理回路で表すと下のようになり、この論理回路から構成される演算装置は「半加算器」と呼ばれます。

半加算器の回路図

つまり、2進数の1桁同士の足し算、言い換えれば「1ビットの足し算」は半加算器により行うことができ、「+」を使わなくても「AND演算」と「XOR演算」により実現可能です。

2進数の1桁同士の足し算を行う半加算器を関数として記述したものが下記になります。

/* 半加算する関数 */
/* aとbの第0ビットに対して半加算を行う */
/* 半加算で得られた「出力」をsのアドレスに
   「桁上げ出力」をcのアドレスに格納 */
void halfAdd(
  unsigned char *s,
  unsigned char *c,
  unsigned char a,
  unsigned char b
){
  unsigned char a0; /* aの第0ビットを格納 */
  unsigned char b0; /* bの第0ビットを格納 */

  /* 第0ビットを取得 */
  a0 = a & (1 << 0);
  b0 = b & (1 << 0);
  
  /* 出力と桁上げ出力を計算 */
  *s = a0 ^ b0;
  *c = a0 & b0;
}

しかし、複数桁の足し算は半加算器だけでは実現不可能です。なぜならこの半加算器では下位の桁からの桁上がり入力が考慮されていないためです。

例えば2進数「1001」と「0011」の足し算を実際に計算してみましょう。

この複数桁の2進数の足し算は下位の桁から下記のように演算することができます。

第0桁目:1 + 1 = 0 (1の桁上がり発生)
第1桁目:1 + 0 + 1 = 1 (1の桁上がり発生)
第2桁目:1 + 0 + 0 = 1
第3桁目:1 + 0 = 1

青字部分は下位からの桁上がりした数になります。ポイントは、複数桁の足し算は下位からの桁上がりを考慮しながら計算していく必要があるということです。しかし半加算器ではこの「下位からの桁上がり」を考慮(入力)することができません。

そこで登場するのが「全加算器」です。全加算器は下位からの桁上がりを考慮して2進数1桁分の足し算を行うことが可能な演算器です。

全加算器は半加算器を用いて下記の回路で表現することができます。

全加算器の回路図

半加算器では前述の通り「+」を使用していませんので、全加算器により「+」なしで下位からの桁上がりを考慮した2進数1桁の足し算を行うことができます。

全加算器を関数化したものが下記になります。

/* 全加算する関数 */
/* aとbとxの第0ビットに対して全加算を行う */
/* 全加算で得られた「出力」をsのアドレスに
   「桁上げ出力」をcのアドレスに格納 */
void fullAdd(
  unsigned char *s,
  unsigned char *c,
  unsigned char a,
  unsigned char b,
  unsigned char x
){
  unsigned char a0; /* aの第0ビットを格納 */
  unsigned char b0; /* bの第0ビットを格納 */
  unsigned char x0; /* xの第0ビットを格納 */ 
  unsigned char s1, s2; /* 半加算の出力を格納 */
  unsigned char c1, c2; /* 半加算の桁上げ出力を格納 */

  /* 第0ビットを取得 */
  a0 = a & (1 << 0);
  b0 = b & (1 << 0);
  x0 = x & (1 << 0);

  /* a0とb0の半加算結果を取得 */
  halfAdd(&s1, &c1, a0, b0);

  /* ↑で得られた出力sとxの半加算結果を取得 */
  halfAdd(&s2, &c2, s1, x0);

  /* 最終的な出力と桁上げ出力を計算 */
  *s = s2;
  *c = c1 | c2;
}

2進数複数桁の足し算

全加算器を下位の桁から上位の桁に向かって順々に実行していくことで、2進数複数桁の足し算を実行することが可能です。

例えば2進数3桁分(つまり3ビット分)の足し算を行う全加算器を用いた回路は下のように表現することができます。

全加算器を3つ接続した回路図

実際の動作を2進数「001」と「011」の足し算の例を用いて見ていきましょう。まず最初の全加算器には各々の2進数の第0桁の “1” と “1” が a と b に入力され、下位からの桁上がりである x には “0”(最下位の桁のため)が入力されます。

1つ目の全加算器への入力

計算結果 s は “0” となり、足し算結果の第0桁としてはこの “0” が確定しますので、そのままそれを結果に反映します。さらに計算結果の桁上がり結果の c は “1” となります。

1つ目の全加算器からの出力

次の全加算器の a と b には「001」と「011」の第1桁の “0” と “1” がそれぞれ入力されます。さらに x には下位からの桁上がり結果(つまり前の全加算器の出力 c)の “1” が入力されます。ここで前の加算器の出力 c  を次の全加算器の x へ入力することで、下位からの桁上がりを考慮した足し算を行うことが可能です。

2つ目の全加算器への入力

計算結果 s は “0” となります。ここで足し算結果の第1桁としてはこの “0” が確定しますので、そのままそれを結果に反映します。さらに計算結果の桁上がり結果の c は “1” となります。

2つ目の全加算器からの出力

最後の全加算器の a と b には「001」と「011」の第2桁の “0” と “1” がそれぞれ入力され、さらに x には前の全加算器の出力 c の “1” が入力されます。

3つ目の全加算器への入力

計算結果 s は “1” となります。ここで足し算結果の第2桁としてはこの “1” が確定しますので、そのままそれを結果に反映します。さらに計算結果の桁上がり結果の c は “0” となります。

3つ目の全加算器からの出力

これで2進数3桁分の足し算が行えたことになります。つまり3ビットで表現できる “-4” 〜 “3” までの数の足し算が行えるようになりました。

もっと大きい数を扱うためには、この全加算器を接続する数を増やせば良いだけです。このページでは int 型同士の足し算を行えるようにすることを目標としていますので、int 型のサイズである32ビット(4バイト)の足し算を行うために、32個の全加算器を接続することになります。

このページでは全加算器を8つ用いた8ビット分(つまり1バイト分)の足し算を行う関数を用意し、それを4回実行することで32ビットの足し算を実現しています。

8ビット単位(バイト単位)で足し算を行う関数は下記のようになります。

/* バイト単位で加算する関数 */
/* aとbとx(xは桁上げ分)に対して加算を行う */
/* 加算で得られた「出力」をsのアドレスに
   「桁上げ出力」をcのアドレスに格納 */
void byteAdd(
  unsigned char *s,
  unsigned char *c,
  unsigned char a,
  unsigned char b,
  unsigned char x
){

  unsigned char ab; /* aの特定ビットを格納 */
  unsigned char bb; /* bの特定ビットを格納 */
  unsigned char bit; /* 処理中のビット番号を格納 */
  unsigned char tmpc; /* 全加算器の桁上がり出力を格納 */
  unsigned char tmps; /* 全加算器の出力を格納 */
  unsigned char tmpx; /* 全加算器への入力桁上がり値を格納 */
 
  *s = 0;
  tmpc = x;

  /* 第0ビット */
  bit = 0;
  ab = (a & (1 << bit)) >> bit;
  bb = (b & (1 << bit)) >> bit;
  tmpx = tmpc;
  fullAdd(&tmps, &tmpc, ab, bb, tmpx);
  *s = *s | (tmps << bit);

  /* 第1ビット */
  bit = 1;
  ab = (a & (1 << bit)) >> bit;
  bb = (b & (1 << bit)) >> bit;
  tmpx = tmpc;
  fullAdd(&tmps, &tmpc, ab, bb, tmpx);
  *s = *s | (tmps << bit);

  /* 第2ビット */
  bit = 2;
  ab = (a & (1 << bit)) >> bit;
  bb = (b & (1 << bit)) >> bit;
  tmpx = tmpc;
  fullAdd(&tmps, &tmpc, ab, bb, tmpx);
  *s = *s | (tmps << bit);
  
  /* 第3ビット */
  bit = 3;
  ab = (a & (1 << bit)) >> bit;
  bb = (b & (1 << bit)) >> bit;
  tmpx = tmpc;
  fullAdd(&tmps, &tmpc, ab, bb, tmpx);
  *s = *s | (tmps << bit);

  /* 第4ビット */
  bit = 4;
  ab = (a & (1 << bit)) >> bit;
  bb = (b & (1 << bit)) >> bit;
  tmpx = tmpc;
  fullAdd(&tmps, &tmpc, ab, bb, tmpx);
  *s = *s | (tmps << bit);

  /* 第5ビット */
  bit = 5;
  ab = (a & (1 << bit)) >> bit;
  bb = (b & (1 << bit)) >> bit;
  tmpx = tmpc;
  fullAdd(&tmps, &tmpc, ab, bb, tmpx);
  *s = *s | (tmps << bit);

  /* 第6ビット */
  bit = 6;
  ab = (a & (1 << bit)) >> bit;
  bb = (b & (1 << bit)) >> bit;
  tmpx = tmpc;
  fullAdd(&tmps, &tmpc, ab, bb, tmpx);
  *s = *s | (tmps << bit);

  /* 第7ビット */
  bit = 7;
  ab = (a & (1 << bit)) >> bit;
  bb = (b & (1 << bit)) >> bit;
  tmpx = tmpc;
  fullAdd(&tmps, &tmpc, ab, bb, tmpx);
  *s = *s | (tmps << bit);

  *c = tmpc;
}

さらにこれを4バイト分つなぎ合わせて4バイト分の足し算を行うようにした関数は下記のようになります。

int add(int a, int b){
  unsigned char s; /* バイト加算の出力を格納 */
  unsigned char c; /* バイト加算の桁上がり出力を格納 */
  unsigned char x; /* バイト加算への桁上がり入力を格納 */
  unsigned char ab; /* aの特定ビットのみを格納 */
  unsigned char bb; /* bの特定ビットのみを格納 */
  unsigned char bit; /* 処理中のビット番号を格納 */
  int ans; /* 加算結果を格納 */

  c = 0;
  ans = 0;

  /* 1バイト目 */
  bit = 0;
  ab = (a & (0b11111111 << bit)) >> bit;
  bb = (b & (0b11111111 << bit)) >> bit;
  x = c;

  byteAdd(&s, &c, ab, bb, x);

  ans = ans | (s << bit);
  
  /* 2バイト目 */
  bit = 8;
  ab = (a & (0b11111111 << bit)) >> bit;
  bb = (b & (0b11111111 << bit)) >> bit;
  x = c;

  byteAdd(&s, &c, ab, bb, x);

  ans = ans | (s << bit);

  /* 3バイト目 */
  bit = 16; 
  ab = (a & (0b11111111 << bit)) >> bit;
  bb = (b & (0b11111111 << bit)) >> bit;
  x = c;
  
  byteAdd(&s, &c, ab, bb, x);
  
  ans = ans | (s << bit);

  /* 4バイト目 */
  bit = 24; 
  ab = (a & (0b11111111 << bit)) >> bit;
  bb = (b & (0b11111111 << bit)) >> bit;
  x = c;
  
  byteAdd(&s, &c, ab, bb, x);
  
  ans = ans | (s << bit);
  return ans;
}

この add 関数で4バイト分の足し算が行えますので、int 型同士の足し算が実現できたことになります。

スポンサーリンク

引き算

引き算は実は足し算さえ実現すれば簡単です。なぜなら、引き算は2の補数を用いれば足し算で実現することが可能だからです。

ある数に対して、その数の「2の補数」は、その数の符号(+・ー)を逆にした数になります。つまり「100」の2の補数は「−100」になります。

ですので、「a – b」の計算は

  1. b の2の補数を求める
  2. a + (b の2の補数)を求める

で実行することができます。

さらに b に対する2の補数は下記で求めることができます。

  1. b の全ビットの “1”・”0″ を逆転する(全ビットに対してNOT演算)
  2. 1. の結果に1を足す

C言語では全ビットに対するNOT演算は変数名の前に「~」を付加する事で実行可能ですので、引き算を実行する関数は下記のように記述する事ができます。

/* a - b を求める関数 */
int sub(int a, int b){
  /* bの2の補数をaに加算 */
  return add(a, add(~b, 1));
}

足し算で作成した算術演算子「+」を使用しない add 関数で足し算を行なっていますので、この引き算を行う sub 関数も算術演算子なしで実現できていることになります。

掛け算

掛け算も足し算が実現できていれば簡単です。

まず最初に思い出していただきたいのが2進数 → 10進数変換です。例えば2進数「1101」を10進数に変換するときに、下記のように計算しますよね?

$$ 2^3 + 2^2 + 2^0 = 13 $$

2進数の各桁は2の冪乗(第 k 桁は2の k 乗)で表されており、数字が1の桁の重みを足し合わせる事で10進数に変換する事ができます。

この13を用いた掛け算について考えてみましょう。「a * 13」の掛け算は 13を2の冪乗の和で表現すれば下記のように式変形する事ができます。

$$ a * (2^3 + 2^2 + 2^0) $$

さらに上式は次のように式変形する事ができます。

$$ a * 2^3 + a * 2^2 + a * 2^0 $$

「2の冪乗の掛け算」はシフト演算により実行可能ですので、掛け算の乗数もしくは被乗数のどちらかを「2の冪乗の和」に表現すれば、「*」の算術演算子を用いる事なく掛け算を実現する事が可能です。

(a << 3) + (a << 2) + (a << 0)

またここまでは「13」の実例を用いて説明してきましたが、どんな整数でも2の冪乗の和で表現する事が可能ですので、どんな整数同士の掛け算でも、シフト演算と足し算で掛け算を実行する事ができるということになります。

具体的には、乗数もしくは被乗数の各ビットが1かどうかを調べ、1の場合のみ、そのビットの位置に応じた重みを掛けるために他方の数を左シフト演算すれば良いです。

ここまで説明してきたシフト演算を用いた掛け算を実行する関数は下記のようになります。

/* a * b を求める関数 */
int mul(int a, int b){
  int ans; /* 掛け算結果を格納 */
  int bit; /* 処理中のビット番号を格納 */
  unsigned int ua; /* aの符号なし変換結果を格納 */
  unsigned int ub; /* bの符号なし変換結果を格納 */
  char sa; /* aのプラスorマイナスの情報を格納 */
  char sb; /* bのプラスorマイナスの情報を格納 */
  unsigned int tmpb; 

  /* マイナスの値をプラスに変換
     プラスorマイナスの情報を格納 */
  if(a & (1 << 31)){
    ua = sub(0, a);
    sa = 1;
  } else {
    ua = a;
    sa = 0;
  }

  if(b & (1 << 31)){
    ub = sub(0, b);
    sb = 1;
  } else {
    ub = b;
    sb = 0;
  }

  /* ubの最上位ビットを取得 */
  tmpb = ub;
  bit = 0;
  while(tmpb > 0){
    bit = add(bit, 1);
    tmpb = tmpb >> 1;
  }  

  /* 掛け算結果を取得 */
  ans = 0;
  while(bit >= 0){
    /* 第bitビットが1かどうかを判断 */
    if(ub & (1 << bit)){
      /* 第bitビットが1の場合 */

      /* 乗数aをbitビット分右シフトした値を
         ansに足し合わせ */
      ans = add(ans, (ua << bit));
    }
    /* 次のビットに移動 */
    bit = sub(bit, 1);
  }
  
  /* 最初に取得したaとbのプラスorマイナスに基づいて
     掛け算結果の符号を変換 */
  if((sa == 1 && sb == 0) || (sa == 0 && sb == 1)){
    ans = sub(0, ans);
  }

  return ans;
}

マイナスの値があるとちょっとややこしいので、関数の最初で入力 a と b それぞれをプラスの値に変換し、関数の最後でそれぞれの符号に応じて掛け算結果に符号を付けています。

ちなみにですが、「a * b」であれば「a」を1つずつ足し合わせる処理を「b」回ループするだけでも掛け算は実行可能です。今回紹介したシフトを用いた方法は、「a」を1つずつではなく「a」の2の冪乗倍分一気に足し合わせる事で処理を効率化しています。

割り算

割り算も引き算を使用して実現する事が可能です。

割り算に関しては2進数の割り算を筆算で解くことを考えると分かりやすいと思います。

下記は2進数の割り算を筆算で行う様子になります。基本的に10進数と同じように演算する事ができます。

2進数の割り算を筆算で行う様子

つまり、割り算は下記の手順を k が 0 になるまで実行する事が可能です。

  1. 除数を k ビット左シフトした数を求める
  2. 1. で求めた数を被除数から引けるかどうかを判断する
  3. 引ける場合のみ下記の処理を行う
    • 割り算結果に2の k 乗を足す
    • 被除数から 1. で求めた数を引いた結果を新たな被除数にする
  4. k を 1 減らして 1. に戻る

これを関数化したものが下記になります。

/* a / b を求める関数 */
int div(int a, int b){
  int ans; /* 割り算結果を格納 */
  int bit; /* 処理中のビット番号を格納 */
  unsigned int ua; /* aをプラスに変換した結果を格納 */
  unsigned int ub; /* bをプラスに変換した結果を格納 */
  char sa; /* aのプラスorマイナスの情報を格納 */
  char sb; /* bのプラスorマイナスの情報を格納 */
  unsigned int tmpb;
  
  /* マイナスの値をプラスに変換
     プラスorマイナスの情報を格納 */
  if(a & (1 << 31)){
    ua = sub(0, a);
    sa = 1;
  } else {
    ua = a;
    sa = 0;
  }

  if(b & (1 << 31)){
    ub = sub(0, b);
    sb = 1;
  } else {
    ub = b;
    sb = 0;
  }
  
  /* 処理を開始するビット番号を取得 */
  tmpb = ub;
  bit = 0;
  while(tmpb > 0){
    bit = add(bit, 1);
    tmpb = tmpb >> 1;
  }
  bit = sub(31, bit);

  /* 割り算結果を取得 */
  ans = 0; 
  while(bit >= 0){
    if(ua >= ub << bit){
      ua = sub(ua, ub << bit);
      ans = add(ans, (1 << bit));
    }
    bit = sub(bit, 1);
  }

  /* aとbのプラスorマイナス情報に基づいて
     結果の符号を変換 */
  if((sa == 1 && sb == 0) || (sa == 0 && sb == 1)){
    ans = sub(0, ans);
  }

  return ans;
}

掛け算同様に入力値がマイナスの場合は処理が上手くいかないので、関数の最初でマイナスの値をプラスの値に変換し、関数の最後に割り算結果に符号を付け直しています。

ちなみにですが、「a / b」であれば「a」から「b」を1つずつ引く処理を何回ループできるか調べるだけでも割り算結果を求める事は可能です。今回紹介したシフトを用いた方法は、「b」を1つずつではなく「b」の2の冪乗倍分一気に引く事で処理を効率化しています。

スポンサーリンク

まとめ

今回は算術演算子「+」「-」「*」「/」を使わずに足し算・引き算・掛け算・割り算を実現する方法を解説しました。

安い CPU や古い CPU などでは乗算器や除算器がついていないものもあるそうです。なのでこれらの CPU では今回紹介したのと同様に論理演算を駆使して掛け算や割り算が実現されていると思われます(もっと効率化されていると思いますが)。

個人的には今回はプログラミングしていて結構楽しかったです。特に足し算に関しては論理回路がどのように動くかを実感できてよかったです。

論理演算・論理回路の勉強になりますので、是非この機会に皆さんもプログラミングしてみてください!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です