# 0371. 兩整數之和 ## 題目地址(371. 兩整數之和) <https://leetcode-cn.com/problems/sum-of-two-integers/> ## 題目描述 ``` <pre class="calibre18">``` 不使用運算符 + 和 - ，計算兩整數 a 、b 之和。 示例 1: 輸入: a = 1, b = 2 輸出: 3 示例 2: 輸入: a = -2, b = 3 輸出: 1 ``` ``` ## 前置知識 - [位運算](https://github.com/azl397985856/leetcode/blob/master/thinkings/bit.md) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 不能使用加減法來求加法。 我們只能朝著位元算的角度來思考了。 由于`異或`是`相同則位0，不同則位1`，因此我們可以把異或看成是一種不進位的加減法。  由于`與`是`全部位1則位1，否則位0`，因此我們可以求與之后左移一位來表示進位。  然后我們對上述兩個元算結果遞歸求解即可。 遞歸的結束條件就是其中一個為0，我們直接返回另一個。 ## 關鍵點解析 - 位運算 - 異或是一種不進位的加減法 - 求與之后左移一位來可以表示進位 ## 代碼 代碼支持：JS，C++，Java，Python Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=371 lang=javascript * * [371] Sum of Two Integers */</span> <span class="hljs-title">/** * @param {number} a * @param {number} b * @return {number} */</span> <span class="hljs-keyword">var</span> getSum = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">a, b</span>) </span>{ <span class="hljs-keyword">if</span> (a === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> b; <span class="hljs-keyword">if</span> (b === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> a; <span class="hljs-keyword">return</span> getSum(a ^ b, (a & b) << <span class="hljs-params">1</span>); }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">getSum</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a, <span class="hljs-keyword">int</span> b)</span> </span>{ <span class="hljs-keyword">if</span>(a==<span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> b; <span class="hljs-keyword">if</span>(b==<span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> a; <span class="hljs-keyword">while</span>(b!=<span class="hljs-params">0</span>) { <span class="hljs-title">// 防止 AddressSanitizer 對有符號左移的溢出保護處理</span> <span class="hljs-keyword">auto</span> carry = ((<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">int</span> ) (a & b))<<<span class="hljs-params">1</span>; <span class="hljs-title">// 計算無進位的結果</span> a = a^b; <span class="hljs-title">//將存在進位的位置置1</span> b =carry; } <span class="hljs-keyword">return</span> a; } }; ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getSum</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a, <span class="hljs-keyword">int</span> b)</span> </span>{ <span class="hljs-keyword">if</span>(a==<span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> b; <span class="hljs-keyword">if</span>(b==<span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> a; <span class="hljs-keyword">while</span>(b!=<span class="hljs-params">0</span>) { <span class="hljs-keyword">int</span> carry = a&b; <span class="hljs-title">// 計算無進位的結果</span> a = a^b; <span class="hljs-title">//將存在進位的位置置1</span> b =carry<<<span class="hljs-params">1</span>; } <span class="hljs-keyword">return</span> a; } } ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-title"># python整數類型為Unifying Long Integers, 即無限長整數類型.</span> <span class="hljs-title"># 模擬 32bit 有符號整型加法</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">getSum</span><span class="hljs-params">(self, a: int, b: int)</span> -> int:</span> a &= <span class="hljs-params">0xFFFFFFFF</span> b &= <span class="hljs-params">0xFFFFFFFF</span> <span class="hljs-keyword">while</span> b: carry = a & b a ^= b b = ((carry) << <span class="hljs-params">1</span>) & <span class="hljs-params">0xFFFFFFFF</span> <span class="hljs-title"># print((a, b))</span> <span class="hljs-keyword">return</span> a <span class="hljs-keyword">if</span> a < <span class="hljs-params">0x80000000</span> <span class="hljs-keyword">else</span> ~(a^<span class="hljs-params">0xFFFFFFFF</span>) ``` ``` **復雜度分析** - 時間復雜度：O(1)O(1)O(1) - 空間復雜度：O(1)O(1)O(1) > 由于題目數據規模不會變化，因此其實復雜度分析是沒有意義的。 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。