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

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

SHARE

このページにはプロモーションが含まれています

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

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

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

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

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

条件

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

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

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

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

足し算

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

スポンサーリンク

２進数１桁の足し算

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

a b c s
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

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

c = a & b;

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

s = a ^ b;

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

半加算器の回路図

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

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

/* 半加算する関数 */
/* 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;
}

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

例えば２進数「１００１」と「００１１」の足し算を実際に計算してみましょう。

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

第０桁目：1 + 1 = 0 （1の桁上がり発生）
第１桁目：1 + 0 + 1 = 1 （１の桁上がり発生）
第２桁目：1 + 0 + 0 = 1
第３桁目：1 + 0 = 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;
}

２進数複数桁の足し算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

このページでは全加算器を８つ用いた８ビット分（つまり１バイト分）の足し算を行う関数を用意し、それを４回実行することで３２ビットの足し算を実現しています。

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

/* バイト単位で加算する関数 */
/* 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;
}

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

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;

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

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

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

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

  ans = ans | (s << bit);

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

  /* ４バイト目 */
  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 関数で４バイト分の足し算が行えますので、int 型同士の足し算が実現できたことになります。

引き算

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

ある数に対して、その数の「２の補数」は、その数の符号（＋・ー）を逆にした数になります。つまり「１００」の２の補数は「−１００」になります。

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

  1. b の２の補数を求める
  2. a + （b の２の補数）を求める

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

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

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

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

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

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

スポンサーリンク

掛け算

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

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

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

２進数の各桁は２の冪乗（第 k 桁は２の k 乗）で表されており、数字が１の桁の重みを足し合わせる事で１０進数に変換する事ができます。

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

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

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

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

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

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

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

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

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

/* 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」を１つずつ足し合わせる処理を「b」回ループするだけでも掛け算は実行可能です。今回紹介したシフトを用いた方法は、「a」を１つずつではなく「a」の２の冪乗倍分一気に足し合わせる事で処理を効率化しています。

割り算

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

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

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

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

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

  1. 除数を k ビット左シフトした数を求める
  2. 1. で求めた数を被除数から引けるかどうかを判断する
  3. 引ける場合のみ下記の処理を行う
    • 割り算結果に２の 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」を１つずつ引く処理を何回ループできるか調べるだけでも割り算結果を求める事は可能です。今回紹介したシフトを用いた方法は、「b」を１つずつではなく「b」の２の冪乗倍分一気に引く事で処理を効率化しています。

まとめ

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

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

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

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

オススメの参考書（PR）

C言語学習中だけど分からないことが多くて挫折しそう...という方には、下記の「スッキリわかるC言語入門」がオススメです！

スッキリわかるC言語入門 第2版
posted with ヨメレバ
中山 清喬/株式会社フレアリンク インプレス 2021年12月14日頃
楽天ブックス
Amazon
Kindle
 

まず学習を進める上で、参考書は２冊持っておくことをオススメします。この理由は下記の２つです。

  • 参考書によって、解説の仕方は異なる
  • 読み手によって、理解しやすい解説の仕方は異なる

ある人の説明聞いても理解できなかったけど、他の人からちょっと違った観点での説明を聞いて「あー、そういうことね！」って簡単に理解できた経験をお持ちの方も多いのではないでしょうか？

それと同じで、１冊の参考書を読んで理解できない事も、他の参考書とは異なる内容の解説を読むことで理解できる可能性があります。

なので、参考書は２冊持っておいた方が学習時に挫折しにくいというのが私の考えです。

特に上記の「スッキリわかるC言語入門」は、他の参考書とは違った切り口での解説が豊富で、他の参考書で理解できなかった内容に対して違った観点での解説を読むことができ、オススメです。題名の通り「なぜそうなるのか？」がスッキリ理解できるような解説内容にもなっており、C言語入門書としてもかなり分かりやすい参考書だと思います。

もちろんネット等でも色んな観点からの解説を読むことが出来ますので、分からない点は別の人・別の参考書の解説を読んで解決していきましょう！もちろん私のサイトも参考にしていただけると嬉しいです！

入門用のオススメ参考書は下記ページでも紹介していますので、こちらも是非参考にしていただければと思います。

https://daeudaeu.com/c_reference_book/

同じカテゴリのページ一覧を表示

前の記事

C言語オススメ書籍解説ページのアイキャッチ
C言語入門者向け！オススメ参考書籍７選を紹介

次の記事

static 関数と static グローバル変数の使い方・…
static解説ページのアイキャッチ