萌新刷題（一）A + B 問題

題目

給出兩個整數a和b, 求他們的和, 但不能使用 + 等數學運算符。顯然你可以直接 return a + b，但是你是否可以挑戰一下不這樣做？

題目鏈接 A + B 問題

思路

做加法不用四則運算？那麼用什麼呢？只剩下位運算了。

基本思路是這樣的：

A&B //看哪幾位有進位

A^B //不帶進位加

考慮二進位加法的過程，

步驟一、A^B，能夠得到沒有進位的加法。

步驟二、A&B，能夠得到相加之後，能夠進位的位置的信息。向左移動一位，就是兩個二進位數相加之後的進位信息。所以，(A&B)<<1就是兩個二進位數相加得到的「進位結果」。

步驟三、將前兩步的結果相加。相加的過程就是步驟一和步驟二，直到不再產生進位為止。

代碼

Python版本：

class Solution:n """n @param a: The first integern @param b: The second integern @return: The sum of a and bn """n def aplusb(self, a, b):n # write your code here, try to do it without arithmetic operators.n carry = 1n while carry != 0:n s = a ^ bn carry = (a & b) << 1n a = sn b = carryn return an

提交發現出錯

你的代碼運行時間超過了限制，檢查你的時間複雜度。TLE通常是由死循環造成的，思考一下你的時間複雜度是否是最優的。

c++版本

加入遞歸

class Solution {npublic:n /*n * @param a: The first integern * @param b: The second integern * @return: The sum of a and bn */n int aplusb(int a,int b){n if(a==0) return b;n if(b==0) return a;n int x = a^b;n int y = (a&b)<<1;n return aplusb(x,y);n}n};n

100%通過測試，畢竟是c++，速度就是快。

總結

基本思路

int A, B;

A&B //看哪幾位有進位

A^B //不帶進位加

寫完文章發現知乎也有原題不使用「+」號實現加法操作？ - 知乎

同時給出Python陷入死循環的原因A + B without arithmetic operators, Python vs C++

一個人刷題是痛苦的，有人一起交流最好了，你也想一起來嗎？