C言語で2つの整数をビット演算で再帰的に加算する方法

この問題では、2つの整数が与えられ、ビット演算を用いた再帰的な加算を行うCプログラムを作成することが課題となります。

ビット演算で加算する仕組み

ビット演算で和を求める考え方は、幼い頃に学んだ「筆算のやり方」と本質的に同じです。各桁の数字を順番に足していき、繰り上がりが発生したら、その繰り上がりを次の桁に加算します。

今回のアプローチでもまったく同じことを行います。XOR（排他的論理和）演算子で和を計算し、AND（論理積）演算で繰り上がりの有無を確認します。繰り上がりが存在すれば、それを再度数値に加算し、なければそこで処理を完了します。

実はこれは、デジタル電子回路で学ぶ半加算器（Half-Adder）と同じ論理です。半加算器について詳しく知りたい方は、こちらを参照してください。

アルゴリズムの手順

和は a^b（a XOR b）によって計算されます。両者の最下位ビットがどちらも1である場合などには、追加の繰り上がりを伝播させる必要があります。つまり、余分に立ったビットを数値に加算していく必要があるのです。

具体的なアルゴリズムは以下の通りです。

• ステップ1 − a と b のXOR（a^b）を計算し、結果変数 result に格納します。
• ステップ2 − {(a & b) << 1} が 0 と等しいかどうかを判定します。
• ステップ2.1 − 0 に等しい場合、result を出力します。これが最終的な答えです。
• ステップ2.2 − 0 でない場合は、a = {(a & b) << 1}、b = result としてステップ1へ戻ります。

サンプルプログラム

アルゴリズムの動作を示すCプログラムは以下の通りです。

#include <stdio.h>
int addNumbers(int a, int b) {
   int carry = (a & b) << 1;
   int result = a^b;
   if (carry == 0)
      return result;
   else
      addNumbers(carry, result);
}
int main(){
   int a = 54, b = 897;
   printf("The sum of %d and %d using bitwise adding is %d", a, b, addNumbers(a, b));
   return 0;
}

実行結果

The sum of 54 and 897 using bitwise adding is 951’