Pythonで2つの整数の合計を求める方法｜+と-を使わないビット演算テクニック

問題概要

2つの整数 a と b が与えられたとき、その合計を求めることを考えます。ただし、+ や - のような算術演算子は使用できません。例えば、a = 5、b = 7 の場合、答えは 12 になります。

解決のアプローチ：ビット演算を活用する

この問題は、ビット単位の論理演算子を組み合わせることで解決できます。ポイントは次の3つです。

• XOR（^：排他的論理和） … 桁上がりを考慮しない「部分和」を計算します。
• AND（&：論理積） … 桁上がりが発生する位置を検出します。
• 左シフト（<< 1） … 検出した桁上がりを1つ上の位へ移動させます。

アルゴリズムの手順

1. b が 0 であれば、a をそのまま返します（これが合計値です）。
2. そうでなければ、「a ^ b」と「(a & b) を左に1ビットシフトした値」を新しい引数として、sum 関数を再帰的に呼び出します。
3. b が 0 になるまでこの処理を繰り返し、最終的な a を結果として返します。

Pythonでの実装例

以下の実装を見ると、仕組みがより理解しやすくなります。

class Solution:
    def getSum(self, a: int, b: int) -> int:
        if b == 0:
            return a
        return self.getSum(a ^ b, (a & b) << 1)


ob = Solution()
print(ob.getSum(5, 7))

入力

a = 5
b = 7

出力

12

処理の流れを解説

a = 5（2進数で 0101）、b = 7（2進数で 0111）の場合を順に追ってみましょう。

• 1回目： a ^ b = 0010（部分和）、(a & b) << 1 = 1010（桁上がり）
• 2回目： 0010 ^ 1010 = 1000、(0010 & 1010) << 1 = 0100
• 3回目： 1000 ^ 0100 = 1100、桁上がりは 0 となり終了

最終的に得られる 1100 は、10進数で 12 です。期待どおりの結果が得られました。

負の数にも対応させるには

上記のシンプルな実装は正の整数では正しく動作しますが、Pythonの整数は任意精度であるため、負の数を扱うと無限ループになる可能性があります。実務では、32ビットのマスクを用いて次のように書くのが安全です。

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF   # 32ビットのマスク
        MAX_INT = 0x7FFFFFFF

        while b != 0:
            carry = ((a & b) << 1) & MASK  # 桁上がり
            a = (a ^ b) & MASK             # 部分和
            b = carry

        # 結果が負の数の場合は補数表現に戻す
        return a if a <= MAX_INT else ~(a ^ MASK)

このように、XORで「たしざん」、AND＋シフトで「くり上がり」を表現することで、算術演算子を使わずに足し算を実現できるのです。