XOR と AND の繰り上がりで、+ を使わずに 2 つの整数を足す

ビット操作問題 156

+ と - を使わずに、2 つの整数の和を求めます。繰り上がりを無視した和は XOR、繰り上がりは AND を 1 ビット左へずらした値なので、繰り上がりが 0 になるまで 2 つを足し直す練習です。

海外で定番の問題リスト 4 本には入っていません

問題

足し算の回路を作る練習として、整数 a と b の和を返す関数を書いてください。ただし、+ と - の演算子 (+=、++ なども) は使わず、ビット演算で求めます。

a と b は -1000000000 以上 1000000000 以下です。和は 32 ビットの符号つき整数 (-2147483648 以上 2147483647 以下) に収まります
負の数は、32 ビットの 2 の補数として扱います

入力と出力の例

例 1

a = 13 b = 29

例 2

負の数と正の数の和です。

a = -8 b = 5

-3

例 3

負の数どうしの和です。

a = -6 b = -9

-15

面接での聞かれ方

面接では、計算機の中で足し算がどう行われているかを聞く問題として出されます。

「+ を使わずに 2 つの整数を足してください」
正の数で書けると、「負の数ではどうなりますか？」と続きます
Python で書くと、「整数に上の限りが無いと、ループが止まりますか？」と聞かれます

1 ビットの足し算を XOR と AND に分けられるか、そして言語ごとの整数の幅の違いを扱えるかが見られています。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

1 ビットどうしの足し算を考えます。0 + 0、0 + 1、1 + 0 は繰り上がりなし、1 + 1 は 0 で 1 つ上へ繰り上がります。その位に残る値は XOR (違えば 1) と同じで、繰り上がりが出るのは AND (両方 1) のときです。

段 2

全部のビットをまとめて考えると、a ^ b が繰り上がりを無視した和、(a & b) << 1 が繰り上がりを 1 つ上の位へ送った値です。本当の和は、この 2 つの和です。2 つをまた「足す」ので、a を a ^ b、b を繰り上がりに置き換えて、繰り上がりが 0 になるまで繰り返します。繰り上がりは毎回 1 ビット以上上へ動くので、32 ビットなら 32 回ほどで 0 になります。

段 3

負の数で困るのは、整数の幅が言語で違うところです。JavaScript のビット演算は 32 ビットの符号つき整数で計算するので、そのまま動きます。Go は int が 64 ビットなので、int32 に直してから回し、32 ビットではみ出した繰り上がりを捨てます。Python の整数には上の限りが無く、負の数の繰り上がりが上へいつまでも進むので、0xFFFFFFFF の mask で毎回 32 ビットに切ります。最後に、いちばん上のビットが 1 なら負の数として読み直します。

解答

Python

def add_without_plus(a, b):
    mask = 0xFFFFFFFF
    a &= mask
    b &= mask
    while b != 0:
        carry = ((a & b) << 1) & mask
        a ^= b
        b = carry
    if a > 0x7FFFFFFF:
        return ~(a ^ mask)
    return a

JavaScript

function addWithoutPlus(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1;
    a ^= b;
    b = carry;
  }
  return a;
}

Go

func addWithoutPlus(a, b int) int {
	x, y := int32(a), int32(b)
	for y != 0 {
		carry := (x & y) << 1
		x ^= y
		y = carry
	}
	return int(x)
}

Python の最後の ~(a ^ mask) は、32 ビットのまま読んだ a を負の数に直す書き方です。a ^ mask で 32 ビットの中を反転し、~ でもう一度全部を反転すると、上のビットがすべて 1 の Python の負の数になります。a - (1 << 32) と同じ値ですが、- を使っていません。

計算量

時間は O(1) です。繰り上がりは毎回 1 ビット以上上へ動くので、32 回ほどで終わります
使う記憶は O(1) です
幅を w ビットとすれば、時間は O(w) です

よくある間違い

Python で mask を付けない。 例 2 の -8 と 5 なら止まりますが、-1 と 1 のように繰り上がりが上へ進み続ける組では、Python の整数に上の限りが無いため、ループがいつまでも止まりません
Python で最後に負の数へ直さない。例 3 で、32 ビットの -15 を符号なしで読んだ 4294967281 を返してしまいます
Go で int のまま回す。 64 ビットのまま回しても答えは合うことが多いですが、32 ビットの符号つきとして扱うという条件から外れます。int32 に直すと、問題の約束どおり 32 ビットではみ出した分を捨てられます
繰り上がりを左へずらし忘れる。 a & b は、その位で繰り上がりが出る所です。足すのは 1 つ上の位なので、<< 1 を付けます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def add_without_plus(a: int, b: int) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(add_without_plus(13, 29))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します