1. はじめに
この問題では、演算子 + と - を使わずに、2数の合計値を算出する。
問題文は次の通り。
Given two integers a and b, return the sum of the two integers without using the operators + and -.
2. 解法
演算子の使用が制限されているので、ビット演算で解くことを考える。
ビット演算は、ハードウェアの加算器の基本原理と同じ仕組みで、XOR（排他的論理和）とAND（論理積）を用いることで足し算を行うことができる。
2.1. XOR（排他的論理和）
XORは剰余2の加算で、繰り上がりを無視した和を表す。例えば、2 + 3 の場合は、2進数で $2 = (10)_2$、$3 = (11)_2$ なので、繰り上がりを無視して各ビットを XOR すると次のようになる。
(10)_{2} \oplus (11)_{2} = (01)_{2}
2.2. AND（論理積）
ANDは繰り上がりが発生する位置を表す。
各ビットを見たときに、1 + 1 の場合にのみ繰り上がりが生じるため、ビットごとの AND をとることで、どの桁で繰り上がりが起きるのかを求めることができる。
2進数で 2 = (10)_2、3 = (11)_2 のとき、AND の結果は次のようになる。
(10)_{2} \land (11)_{2} = (10)_{2}
ただし、この値自体は繰り上がりが発生した桁を示しているだけなので、実際の加算では1ビット左にシフトして次のけたに繰り上げる必要がある。
((10)_{2} \land (11)_{2}) \ll 1 = (100)_{2}
最後に、それぞれで求めた結果の排他的論理和（XOR）をとることで、求める結果を得ることができる。
(100)_{2} \oplus (01)_{2} = (101)_{2}
結果は $(101)_{2}$ となり、求めたい結果の 5 と一致する。
3. 実装
Rust で実装した結果を次に示す。
impl Solution {
pub fn get_sum(a: i32, mut b: i32) -> i32 {
let mut ans = a;
while b != 0 {
let carry = (ans & b) << 1;
ans ^= b;
b = carry;
}
ans
}
}
繰り上がり（=b）が 0 になるまでループを回し、計算を行っていく。
4. まとめ
演算子を使わずに、ビット演算で加算および減算を定義できることを確認した。同様の考え方は減算や乗算など、他の算術演算の実装にも応用可能である。