題?鏈接： 371. 兩整數之和

題?描述：

給你兩個整數 a 和 b ，不使? 運算符 + 和 - ，計算并返回兩整數之和。
?例 1：
輸?：a = 1, b = 2
輸出：3
?例 2：
輸?：a = 2, b = 3
輸出：5
提?：
-1000 <= a, b <= 1000

解法（位運算）：

算法思路：
? 異或 ^ 運算本質是「?進位加法」；
? 按位與 & 操作能夠得到「進位」；
? 然后?直循環進?，直到「進位」變成 0 為?
可以發現，對于整數 a 和 b：
在不考慮進位的情況下，其無進位加法結果為 a⊕b。
而所有需要進位的位為 a & b，進位后的進位結果為 (a & b) << 1。
于是，我們可以將整數 a 和 b 的和，拆分為 a 和 b 的無進位加法結果與進位結果的和。因為每一次拆分都可以讓需要進位的最低位至少左移一位，又因為 a 和 b 可以取到負數，所以我們最多需要 log(max_int) 次拆分即可完成運算。
因為有符號整數用補碼來表示，所以以上算法也可以推廣到 0 和負數。

代碼

class Solution {public int getSum(int a, int b) {while (b != 0) {int carry = (a & b) << 1;// 計算進位a = a ^ b;// 先算出?進位相加的結果b = carry;}return a;}
}

復雜度分析

時間復雜度：O(log(max_int))，其中我們將執行位運算視作原子操作。
空間復雜度：O(1)。